Schnittgraph ⇐ Artikelentwürfe

[Anonymous]

In der Graphentheorie ist ein '''Schnittgraph''' ein Graph (Graphentheorie)|Graph der die Schnittmenge|Schnitte einer Familie von Menge (Mathematik)|Mengen als Kanten darstellt. Jede Menge entspricht hierbei einem Knoten im Schnittgraphen. Für jedes Paar zweier Mangen in der Familie, die sich schneiden, hat der Schnittgraph eine Kante, umgekehrt besteht keine Kante zwischen zwei Mengen die sich nicht schneiden.

== Formale Definition ==
Formal ist ein Schnittgraph G ein Graph (Graphentheorie)|ungerichteter Graph der die Familie von Mengen

: S_i, \,\,\, i = 0, 1, 2, \dots

darstellt indem jede Menge S_i mittels eines Knoten v_i repräsentiert wird, und zwei Knoten v_i und v_j genau dann verbunden sind, wenn die Mengen, die sie repräsentieren einen Leere Menge|nicht-leeren Schnitt bilden, also

: E(G) = \{ \{ v_i, v_j \} \mid i \neq j, S_i \cap S_j \neq \empty \}.

== Literatur ==

*
== Weitergehende Literatur ==

* Eine Übersicht der Theorie für Schnittgraphen findet sich in McKee & McMorris (1999).

McKee, Terry A.; McMorris, F. R. (1999), Topics in Intersection Graph Theory, SIAM Monographs on Discrete Mathematics and Applications, vol. 2, Philadelphia: Society for Industrial and Applied Mathematics, ISBN 0-89871-430-3, MR 1672910.

== Externe Links ==

* Jan Kratochvíl, [http://videolectures.net/sicgt07_kratochvil_gig/ A video lecture on intersection graphs (June 2007)]
* E. Prisner, [http://www.eprisner.de/Journey/Rahmen.html A Journey through Intersection Graph County]
Kategorie:Graphentheorie