Schnittgraph
aus Wikipedia, der freien encyclopedia
In der Graphentheorie ist ein Schnittgraph ein Graph, der die nicht-leeren Schnitte einer Familie von Mengen als Kanten darstellt. Jede Menge entspricht hierbei einem Knoten im Schnittgraphen. Für jedes Paar zweier Mengen in der Familie, die sich schneiden, hat der Schnittgraph eine Kante, umgekehrt besteht keine Kante zwischen zwei Mengen, wenn deren Schnitt die leere Menge ist.