Ausschließung/Graph/Beispiel

Oft drückt eine Kante in einem Graphen eine gewisse Verbundenheit zwischen den an der Kante beteiligten Knotenpunkten aus, es kann aber auch genau umgekehrt sein, dass man mit einem Graphen Ausschließungen ausdrücken möche. Man spricht dann von einem Ausschließungsgraphen. Beispielsweise kann es um eine Menge von Personen gehen, und die mit dem Graphen zu modellierende Relation ist etwas wie „sie gehen sich aus dem Weg“, „sie können nicht zusammen in einem Team arbeiten“, „sie vertragen sich nicht“. Die Knotenmenge kann aber auch eine Menge von Aussagen sein, die mit einer Kante zu verbinden sind, wenn die Aussagen sich widersprechen. Oder Klamotten, die nicht zueinander passen.