Schnittpunktdiagramm - Intersection graph

Ein Beispiel dafür, wie sich schneidende Mengen einen Graphen definieren.

In der Graphentheorie ist ein Schnittgraph ein Graph , der das Schnittmuster einer Menge von Mengen darstellt . Jeder Graph kann als Schnittgraph dargestellt werden, aber einige wichtige spezielle Klassen von Graphen können durch die Typen von Mengen definiert werden, die verwendet werden, um eine Schnittdarstellung von ihnen zu bilden.

Formale Definition

Formal ist ein Schnittgraph G ein ungerichteter Graph, der aus einer Familie von Mengen gebildet wird

S _i , i = 0, 1, 2, ...

durch Erzeugen einer Ecke v _i für jede Menge S _i und Verbinden zweier Ecken v _i und v _j durch eine Kante immer dann, wenn die entsprechenden zwei Mengen einen nichtleeren Schnittpunkt haben, d.h.

E ( G ) = {{ v _i , v _j } | i ≠ j , S _i ∩ S _j ≠ ∅}.

Alle Graphen sind Schnittgraphen

Alle ungerichteten Graphen G kann als ein Schnittdiagramm dargestellt werden: für jeden Scheitelpunkt v _i von G , bilden einen Satz S _i aus den Kanten Vorfall v _i ; dann haben zwei solcher Mengen genau dann einen nichtleeren Schnittpunkt, wenn die entsprechenden Knoten eine Kante teilen. Erdős, Goodman & Pósa (1966) liefern eine effizientere Konstruktion (dh erfordert eine geringere Gesamtzahl von Elementen in allen Mengen S _i zusammen), bei der die Gesamtzahl der Mengenelemente höchstens n ² / 4 wobei n die Anzahl der Scheitelpunkte im Graphen ist. Sie schreiben die Beobachtung, dass alle Graphen Schnittgraphen sind, Szpilrajn-Marczewski (1945) zu , sagen aber auch Čulík (1964) zu sehen . Die Schnittpunktzahl eines Graphen ist die minimale Gesamtanzahl von Elementen in jeder Schnittpunktdarstellung des Graphen.

Klassen von Schnittdiagrammen

Viele wichtige Graphfamilien können als Schnittgraphen eingeschränkterer Typen von Mengenfamilien beschrieben werden, zum Beispiel Mengen, die aus einer Art geometrischer Konfiguration abgeleitet sind:

• Ein Intervallgraph ist definiert als Schnittgraph von Intervallen auf der reellen Linie oder von zusammenhängenden Teilgraphen eines Pfadgraphen .
• Ein Indifferenzgraph kann als Schnittgraph von Einheitsintervallen auf der reellen Geraden definiert werden
• Ein Kreisbogendiagramm ist als Schnittdiagramm von Bögen auf einem Kreis definiert .
• Ein Polygon-Kreis-Diagramm ist definiert als der Schnittpunkt von Polygonen mit Ecken auf einem Kreis.
• Eine Charakterisierung eines Chordalgraphen ist der Schnittgraph von zusammenhängenden Teilgraphen eines Baumes .
• Ein Trapezgraph ist definiert als der Schnittgraph von Trapezen, die aus zwei parallelen Geraden gebildet werden. Sie sind eine Verallgemeinerung des Begriffs des Permutationsgraphen , sie sind wiederum ein Spezialfall der Familie der Komplemente von Vergleichbarkeitsgraphen, die als Kovergleichbarkeitsgraphen bekannt sind.
• Ein Einheitsscheibengraph ist definiert als der Schnittgraph von Einheitsscheiben in der Ebene.
• Ein Kreisgraph ist der Schnittgraph einer Menge von Sehnen eines Kreises.
• Das Circle-Packing-Theorem besagt, dass planare Graphen genau die Schnittgraphen von Familien geschlossener Scheiben in der von nicht kreuzenden Kreisen begrenzten Ebene sind.
• Scheinermans Vermutung (jetzt ein Satz) besagt, dass jeder planare Graph auch als Schnittgraph von Liniensegmenten in der Ebene dargestellt werden kann. Schnittgraphen von Liniensegmenten können jedoch auch nichtplanar sein, und das Erkennen von Schnittgraphen von Liniensegmenten ist für die Existenztheorie der reellen Zahlen vollständig ( Schaefer 2010 ).
• Der Liniengraph eines Graphen G ist als Schnittgraph der Kanten von G definiert , wobei wir jede Kante als Menge ihrer beiden Endpunkte darstellen.
• Ein Stringgraph ist der Schnittgraph von Kurven auf einer Ebene .
• Ein Graph hat Boxizität k, wenn er der Schnittgraph von mehrdimensionalen Kästen der Dimension k ist , jedoch nicht kleinerer Dimension.
• Ein Cliquengraph ist der Schnittgraph maximaler Cliquen eines anderen Graphen
• Ein Blockgraph eines Cliquenbaums ist der Schnittgraph zweifach zusammenhängender Komponenten eines anderen Graphen

Scheinerman (1985) charakterisierte die Schnittklassen von Graphen , Familien endlicher Graphen, die als Schnittgraphen von Mengen beschrieben werden können, die aus einer gegebenen Familie von Mengen gezogen wurden. Es ist notwendig und ausreichend, dass die Familie die folgenden Eigenschaften hat:

• Jeder induzierte Teilgraph eines Graphen in der Familie muss auch in der Familie sein.
• Jeder Graph, der aus einem Graphen der Familie gebildet wird, indem ein Knoten durch eine Clique ersetzt wird, muss ebenfalls zur Familie gehören.
• Es gibt eine unendliche Folge von Graphen in der Familie, von denen jeder ein induzierter Teilgraph des nächsten Graphen in der Folge ist, mit der Eigenschaft, dass jeder Graph in der Familie ein induzierter Teilgraph eines Graphen in der Folge ist.

Wenn die Schnittdiagrammdarstellungen die zusätzliche Anforderung haben, dass verschiedene Scheitelpunkte durch verschiedene Mengen dargestellt werden müssen, kann die Cliquenerweiterungseigenschaft weggelassen werden.

Verwandte konzepte

Ein ordnungstheoretisches Analogon zu den Schnittgraphen sind die Inklusionsordnungen . Auf die gleiche Weise wie eine Schnittdarstellung eines Graphen jeden Knoten mit einer Menge beschriftet, so dass Knoten genau dann benachbart sind, wenn ihre Mengen einen nichtleeren Schnitt haben, so kennzeichnet eine Inklusionsdarstellung f eines Poset jedes Element mit einer Menge, sodass für alle x und y in der poset, x  ≤  y , wenn und nur wenn f ( x ) ⊆  f ( y ).

Siehe auch

• Kontaktdiagramm

Verweise

• Čulík, K. (1964), "Anwendungen der Graphentheorie auf die mathematische Logik und Linguistik", Graphentheorie und ihre Anwendungen (Proc. Sympos. Smolenice, 1963) , Prag: Publ. Haus Tschechoslowakische Akad. Wissenschaft , S. 13–20, MR  0176940.
• Erdäs, Paul ; Goodman, AW; Pósa, Louis (1966), "Die Darstellung eines Graphen durch Mengenschnitte " (PDF) , Canadian Journal of Mathematics , 18 (1): 106–112, doi : 10.4153/CJM-1966-014-3 , MR  0186575.
• Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs , Academic Press, ISBN 0-12-289260-7.
• McKee, Terry A.; McMorris, FR (1999), Topics in Intersection Graph Theory , SIAM Monographies on Discrete Mathematics and Applications, 2 , Philadelphia: Society for Industrial and Applied Mathematics, ISBN 0-89871-430-3, HERR  1672910.
• Szpilrajn-Marczewski, E. (1945), "Sur deux propriétés des class d'ensembles", Fund. Mathematik. , 33 : 303–307, HERR  0015448.
• Schaefer, Marcus (2010), "Komplexität einiger geometrischer und topologischer Probleme" (PDF) , Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, USA, September 2009, Revised Papers , Lecture Notes in Computer Science, 5849 , Springer-Verlag, S. 334–344, doi : 10.1007/978-3-642-11805-0_32 , ISBN 978-3-642-11804-3.
• Scheinerman, Edward R. (1985), "Characterizing Kreuzungsklassen von Graphen", Discrete Mathematics , 55 (2): 185–193, doi : 10.1016/0012-365X(85)90047-0 , MR  0798535.

Weiterlesen

• Für einen Überblick sowohl über die Theorie der Schnittgraphen als auch über wichtige spezielle Klassen von Schnittgraphen siehe McKee & McMorris (1999) .

Externe Links

• Jan Kratochvíl, Ein Videovortrag über Schnittdiagramme (Juni 2007)
• E. Prisner, Eine Reise durch Intersection Graph County