Abbildung 1: Ein P₄ Die P₄-Struktur des Petersengraph")?>

Also folgende 4-Tupel gehören alle dazu. Falls ein Vergessener auffällt.... Bitte Bescheid sagen.

1234, 1235, 1237, 1238, 1245, 1246, 1249, 1267, 1269, 126A, 1278, 127A, 1345, 1356, 135A, 1368, 1369, 136A, 1378, 1389, 1469, 156A, 167A, 1689, 2345, 2378, 2457, 245A, 2469, 2478, 2479, 247A, 2489, 257A, 267A, 2789, 3458, 3459, 3489, 356A, 3578, 357A, 3589, 358A, 3689, 378A, 4569, 456A, 457A, 4589, 469A, 4789, 569A, 578A, 6789, 678A, 679A, 689A, 789A.

Was soll das?")?> Die P₄-Struktur eines Graphen spiegelt in gewissem Sinne die Komplexität eines Graphen wieder. Beim Petersengraph ist sie eher kompliziert, bei folgendem Graphen eher einfach:

Abbildung 2: Ein P₄-freier Graph G

Die Baumdarstellung
P₄-freier Graphen ")?> P₄-freie Graphen kann man eindeutig in einer Baumstruktur kodieren. Diese erlaubt es, viele kombinatorische Optimierungsprobleme, die auf allgemeinen Graphen schwer sind, effizient zu lösen.

Der Baum für den Graphen G in Abbildung 2 stellt Abbildung 3 dar. Der Leser möge kann sich davon überzeugen, daß in G zwei Knoten x,y verbunden sind, genau dann, wenn die Wege von x,y nach oben sich in einem mit (1) markierten Knoten treffen.

Abbildung 3: Die Baumdarstellung von G

Die P₄-Struktur
perfekter Graphen")?> Perfekte Graphen sind eine große Klasse von Graphen mit relativ einfacher Struktur. Auch hier kennt man für einige Probleme, die für allgemeine Graphen schwer sind, effiziente Algorithmen. 1987 konnte Bruce Reed zeigen, daß die P₄-Struktur eine Graphen schon festlegt, ob der Graph perfekt ist oder nicht, genauer: zwei Graphen mit gleicher P₄-Struktur sind entweder beide perfekt oder beide nicht-perfekt. Kontakt:")?> Tel.: 0221/470-6030
Fax: 0221/470-5160
contact@zpr.uni-koeln.de