Геометриялық графтар теориясы

Кіріспе

Геометриялық граф теориясы – геометриялық тәсілдермен анықталатын графтарды зерттейтін граф теориясының кең және беймәлім саласы. Нақтырақ айтқанда, геометриялық граф теориясы геометриялық графтардың комбинаторлық және геометриялық қасиеттерін зерттейді, яғни Евклид жазықтығында салынған, мүмкін қиылысатын түзу сызық қабырғалары бар графтарды, сондай-ақ топологиялық графтарды, онда қабырғалар төбелерді қосатын кез келген үздіріссіз қисықтар болуы мүмкін; осылайша, оны "геометриялық және топологиялық графтар теориясы" деп сипаттауға болады (Pach 2013). Геометриялық графтар кеңістіктік желілер деп те аталады.

Геометриялық графиктердің түрлі түрлері

Жазық түзу сызықтық графигі — бұл шығдары Евклид жазықтығындағы нүктелер ретінде, ал қабырғалары қиылыспайтын сызық кесінділері ретінде орналасқан график. Фари теоремасы кез келген жазық графикті жазық түзу сызықтық график ретінде бейнелеуге болады дейді. Триангуляция — жазық түзу сызықтық график, оған қосымша қабырғалар қосу мүмкін емес, себебі әрбір жағы міндетті түрде үшбұрыш болады; Делоне триангуляциясы — бұл жазықтықтағы нүктелер жиынынан анықталатын график, егер тек осы екі нүктеден тұратын шеңбер болса, екі нүктені қабырғамен байланыстырады. Полиэдр немесе политоптың 1-қаңқасы — аталған полиэдр немесе политоптың төбелері мен қабырғаларының жиынтығы. Кез келген дөңес полиэдрдің қаңқасы жазық график болып табылады, ал кез келген k-өлшемді дөңес политоптың қаңқасы k-байланысқан график болып табылады. Керісінше, Штайниц теоремасы кез келген 3-байланысқан жазық граф дөңес полиэдрдің қаңқасы екенін айтады; осы себепті, графтардың бұл класы полиэдрлік графтар деп те аталады. Евклидтік график — шығдары жазықтықтағы нүктелерді көрсететін график, әр қабырғасының ұзындығы оның соңғы нүктелері арасындағы Евклидтік қашықтығына тең. Евклидтік ең төменгі жабатын ағаш — Евклидтік толық графтың ең төменгі жабатын ағашы. Графиктерді қашықтықтар бойынша да анықтауға болады; атап айтқанда, бірлік қашықтықтағы график жазықтықта бірлік қашықтықта орналасқан нүктелерді біріктіру арқылы құралады. Хадвигер-Нельсон мәселесі осы графиктердің хроматикалық санына қатысты. Кесісу графигі — әр шығдары жиынмен байланысты және тиісті жиындардың бос емес кесісуі болғанда шығдарлар қабырғалармен байланыстырылған график. Жиындар геометриялық нысандар болғанда, нәтиже геометриялық график болады. Мысалы, бірөлшемді сызық кесінділерінің кесісу графигі интервалдық график, ал жазықтықтағы бірлік дискілердің кесісу графигі — бірлік дискі графигі. Дөңгелектердің түйісу теоремасы қиылыспайтын дөңгелектердің кесісу графиктері дәл жазық графиктер екенін айтады. Шейнерманның болжамы (2009 жылы дәлелденген) кез келген жазық графикті жазықтықтағы сызық кесінділерінің кесісу графигі ретінде бейнелеуге болады. Нүктелер мен түзулер отбасының Леви графигінде осы нысандардың әрқайсысы үшін шығдар бар және әрбір нүкте-түзу жұбы үшін қабырға бар. Левидің проективтік конфигурациялардың графиктері көптеген маңызды симметриялық графиктер мен камераларға әкеледі. Жабық көпбұрышқа арналған көру графигі, егер шығдарларды жалғастыратын сызық кесіндісі толықтай көпбұрыш ішінде жатса, әрбір шығдарларды бір қабырғамен байланыстырады. Бағытталмаған графикті көру графигі ретінде бейнелеуге болатынын қалай тиімді тексеруге болатыны белгісіз. Ішінара куб — бұл шығдарлары гиперкубтың шығдарларымен байланыстырылған график, сондықтан графиктегі қашықтық сәйкес гиперкубтың шығдарлары арасындағы Хэмминг қашықтығына тең. Комбинаторлық құрылымдардың көптеген маңызды отбасылары, мысалы, графтың ациклді бағыттары немесе гипержазылымдық орналасудағы аймақтар арасындағы жақындықтар, ішінара кубтық графиктер ретінде бейнеленуі мүмкін. Ішінара кубтардың маңызды ерекше жағдайы — пермутоэдрдің қаңқасы, шығдары реттелген нысандар жиынының пермутацияларын, ал қабырғалары ретпен жақын нысандардың алмасуын көрсететін график. Графтардың бірнеше маңызды кластары, соның ішінде медиандық графтар, метрикалық кіріктірулерді қамтитын байланысты анықтамалар бар. Флип графигі — нүктелер жиынының триангуляциясынан құрылған график, онда әр шығдар триангуляцияны көрсетеді және екі триангуляция қабырғаны екіншісімен алмастыру арқылы ерекшеленсе, қабырғамен байланыстырылады. Сондай-ақ, төртбұрыштарға немесе псевдоүшбұрыштарға бөлу үшін және жоғары өлшемді триангуляциялар үшін байланысты флип-графиктерді анықтауға болады. Дөңес көпбұрыштың триангуляциясының флип графигі ассоциаэдрдің немесе Сташефф политопының қаңқасын құрайды. Нүктелер жиынының тұрақты триангуляциясының (жоғары өлшемді дөңес қабықшалардың проекциялары) флип графигін екіншілік политоп деп аталатын қаңқа ретінде де бейнелеуге болады.

A planar straight line graph is a graph in which the vertices are embedded as points in the Euclidean plane, and the edges are embedded as non crossing line segments. Fáry's theorem states that any planar graph may be represented as a planar straight line graph. A triangulation is a planar straight line graph to which no more edges may be added, so called because every face is necessarily a triangle; a special case of this is the Delaunay triangulation, a graph defined from a set of points in the plane by connecting two points with an edge whenever there exists a circle containing only those two points. The 1 skeleton of a polyhedron or polytope is the set of vertices and edges of said polyhedron or polytope. The skeleton of any convex polyhedron is a planar graph, and the skeleton of any k dimensional convex polytope is a k connected graph. Conversely, Steinitz's theorem states that any 3 connected planar graph is the skeleton of a convex polyhedron; for this reason, this class of graphs is also known as the polyhedral graphs. A Euclidean graph is a graph in which the vertices represent points in the plane, and each edge is assigned the length equal to the Euclidean distance between its endpoints. The Euclidean minimum spanning tree is the minimum spanning tree of a Euclidean complete graph. It is also possible to define graphs by conditions on the distances; in particular, a unit distance graph is formed by connecting pairs of points that are a unit distance apart in the plane. The Hadwiger–Nelson problem concerns the chromatic number of these graphs. An intersection graph is a graph in which each vertex is associated with a set and in which vertices are connected by edges whenever the corresponding sets have a nonempty intersection. When the sets are geometric objects, the result is a geometric graph. For instance, the intersection graph of line segments in one dimension is an interval graph; the intersection graph of unit disks in the plane is a unit disk graph. The Circle packing theorem states that the intersection graphs of non crossing circles are exactly the planar graphs. Scheinerman's conjecture (proven in 2009) states that every planar graph can be represented as the intersection graph of line segments in the plane. A Levi graph of a family of points and lines has a vertex for each of these objects and an edge for every incident point line pair. The Levi graphs of projective configurations lead to many important symmetric graphs and cages. The visibility graph of a closed polygon connects each pair of vertices by an edge whenever the line segment connecting the vertices lies entirely in the polygon. It is not known how to test efficiently whether an undirected graph can be represented as a visibility graph. A partial cube is a graph for which the vertices can be associated with the vertices of a hypercube, in such a way that distance in the graph equals Hamming distance between the corresponding hypercube vertices. Many important families of combinatorial structures, such as the acyclic orientations of a graph or the adjacencies between regions in a hyperplane arrangement, can be represented as partial cube graphs. An important special case of a partial cube is the skeleton of the permutohedron, a graph in which vertices represent permutations of a set of ordered objects and edges represent swaps of objects adjacent in the order. Several other important classes of graphs including median graphs have related definitions involving metric embeddings
A flip graph is a graph formed from the triangulations of a point set, in which each vertex represents a triangulation and two triangulations are connected by an edge if they differ by the replacement of one edge for another. It is also possible to define related flip graphs for partitions into quadrilaterals or pseudotriangles, and for higher dimensional triangulations. The flip graph of triangulations of a convex polygon forms the skeleton of the associahedron or Stasheff polytope. The flip graph of the regular triangulations of a point set (projections of higher dimensional convex hulls) can also be represented as a skeleton, of the so called secondary polytope.