Teoria grafów geometrycznych - Geometric graph theory

Nauka o sieci
Internet_map_1024.jpg
Typy sieci
Wykresy
funkcje
Rodzaje
Modele
Topologia
Dynamika
  • Listy
  • Kategorie

Teoria grafów geometrycznych w szerszym sensie jest dużą i amorficzną poddziedziną teorii grafów , dotyczącą grafów definiowanych za pomocą środków geometrycznych. W ściślejszym sensie teoria grafów geometrycznych bada kombinatoryczne i geometryczne właściwości grafów geometrycznych, czyli grafów rysowanych w płaszczyźnie euklidesowej z możliwymi przecinającymi się krawędziami prostoliniowymi oraz grafów topologicznych , w których krawędzie mogą być dowolnymi krzywymi ciągłymi łączącymi wierzchołki, jest więc „teorią grafów geometrycznych i topologicznych” (Pach 2013). Grafy geometryczne nazywane są również sieciami przestrzennymi .

Różne rodzaje wykresów geometrycznych

Wykres płaska liniowa jest wykres, w którym wierzchołki są osadzone w punktach euklidesowej płaszczyźnie , a krawędzie są osadzone w nie przekraczania odcinków . Twierdzenie Fáry'ego mówi, że każdy graf planarny może być reprezentowany jako płaski graf liniowy. Triangulacji jest płaska prosto wykresu liniowego, do którego mogą być dodawane żadne dalsze krawędzie tak nazywane, ponieważ każda ściana jest koniecznie trójkąt; szczególnym przypadkiem jest triangulacja Delaunaya , wykres zdefiniowany ze zbioru punktów na płaszczyźnie przez połączenie dwóch punktów z krawędzią, gdy istnieje okrąg zawierający tylko te dwa punkty.

1- szkielet z bryły lub Polytope jest zbiór wierzchołków i krawędzi wspomnianej bryły lub Polytope. Szkielet dowolnego wielościanu wypukłego jest grafem planarnym, a szkielet dowolnego k- wymiarowego wielościanu wypukłego jest grafem k- spójnym . I odwrotnie, twierdzenie Steinitza mówi, że każdy 3-spójny graf planarny jest szkieletem wielościanu wypukłego; z tego powodu ta klasa grafów jest również znana jako grafy wielościenne .

Euklidesowa wykres przedstawia wykres, w którym wierzchołki stanowią punkty na płaszczyźnie, a krawędzie są przypisane długość równą odległość euklidesowa pomiędzy tymi punktami. Euklidesowa drzewo obejmujących minimum jest drzewo obejmujących minimum z euklidesowej graf pełny . Możliwe jest również zdefiniowanie wykresów według warunków na odległościach; w szczególności wykres odległości jednostkowej jest tworzony przez połączenie par punktów, które są oddalone od siebie o jednostkę odległości na płaszczyźnie. Problem Hadwigera-Nelsona dotyczy liczby chromatycznej tych grafów.

Wykres przecięcia jest wykres, w którym każdy wierzchołek jest powiązany z zestawem, w których wierzchołki są połączone krawędziami, gdy odpowiednie zestawy posiadają niepusty skrzyżowanie. Gdy zbiory są obiektami geometrycznymi, wynikiem jest wykres geometryczny. Na przykład wykres przecięcia odcinków linii w jednym wymiarze jest wykresem interwałowym ; wykres przecięcia dysków jednostkowych w płaszczyźnie jest wykresem dysków jednostkowych . Koło pakowania twierdzenie stwierdza, że wykresy przecięcia okręgów zakaz przejściach są dokładnie płaskie wykresy. Przypuszczenie Scheinermana (sprawdzone w 2009 r.) mówi, że każdy wykres planarny może być reprezentowany jako wykres przecięcia odcinków linii w płaszczyźnie.

Wykres Levi rodziny punktów i linii ma wierzchołek dla każdego z tych przedmiotów oraz krawędź dla każdej pary punkt padającego linii. Wykresy Levi'ego konfiguracji rzutowych prowadzą do wielu ważnych symetrycznych wykresów i klatek .

Wykres widoczność zamkniętego wieloboku łączy każdą parę wierzchołków, przez krawędź, gdy segment linia łącząca wierzchołki leży całkowicie w wieloboku. Nie wiadomo, jak skutecznie przetestować, czy graf nieskierowany może być reprezentowany jako graf widoczności.

Częściowy kostka jest wykres, dla którego wierzchołki mogą być związane z wierzchołków hipersześcianu w taki sposób, że odległość na wykresie równa odległość Hamminga pomiędzy odpowiednich wierzchołków HyperCube. Wiele ważnych rodzin struktur kombinatorycznych, takich jak acykliczne orientacje grafu lub sąsiedztwo między regionami w układzie hiperpłaszczyznowym , można przedstawić jako częściowe grafy sześcienne. Ważnym szczególnym przypadkiem częściowego sześcianu jest szkielet permutościanu , graf, w którym wierzchołki reprezentują permutacje zbioru uporządkowanych obiektów, a krawędzie reprezentują zamiany obiektów sąsiadujących w kolejności. Kilka innych ważnych klas grafów, w tym grafy mediany, ma powiązane definicje obejmujące osadzania metryczne (Bandelt i Chepoi 2008).

Klapki wykres wykres utworzony z triangulacyjnych o wartości zadanej, w którym każdy wierzchołek stanowi triangulacji oraz dwa triangulacje są połączone krawędzią jeżeli różnią się one przez zastąpienie jednej krawędzi do drugiej. Możliwe jest również zdefiniowanie powiązanych wykresów przerzucania dla podziałów na czworokąty lub pseudotrójkąty oraz dla triangulacji o wyższych wymiarach. Flipgraph triangulacji wielokąta wypukłego tworzy szkielet asocjaścianu lub wielościanu Stasheffa . Flipgraph regularnych triangulacji zbioru punktów (rzuty wypukłych kadłubów o wyższych wymiarach) może być również reprezentowany jako szkielet, tzw. polytope wtórny .

Zobacz też

Bibliografia

  • Bandelt, Hans-Jürgen; Chepoi, Wiktor (2008). „Teoria grafów metrycznych i geometria: ankieta” (PDF) . Badania geometrii dyskretnej i obliczeniowej — dwadzieścia lat później . Matematyka współczesna. 453 . Amerykańskie Towarzystwo Matematyczne. s. 49-86.
  • Pach, János , wyd. (2004). W kierunku teorii grafów geometrycznych . Matematyka współczesna. 342 . Amerykańskie Towarzystwo Matematyczne.
  • Pach, Janos (2013). „Początki teorii grafów geometrycznych”. Erdös stulecie . Bolyai Soc. Matematyka. Stadnina. 25 . Budapeszt: János Bolyai Matematyka. Soc. s. 465-484. doi : 10.1007/978-3-642-39286-3_17 . MR  3203608 .
  • Pisański, Tomasz ; Randić, Mediolan (2000). „Mosty między geometrią a teorią grafów” . W Gorini, Kalifornia (red.). Geometria w pracy: artykuły z geometrii stosowanej . Waszyngton, DC: Matematyczne Stowarzyszenie Ameryki. s. 174-194. Zarchiwizowane od oryginału 27.09.2007.

Linki zewnętrzne