ZAIK - Gruppe Faigle/Schrader: Forschung/Diskrete Strukturen/P4-Struktur von Graphen

P4-Struktur von Graphen	Auf dem Gebiet der Algorithmischen Graphentheorie beschäftigen wir uns unter anderem mit der P4-Struktur von Graphen. Ein induzierter P4 eines Graphen G=(V,E) ist ein induzierter Minor, der ein Pfad der Länge vier ist, d.h. es gibt vier Knoten 1, 2, 3, 4 in V, wobei (1,2), (2,3), (3,4) Kanten von G sind, aber (1,3), (1,4) und (2,4) keine Kanten sind. Abbildung 1: Ein P4
Die P4-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 P4-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 P4-freier Graph G
Die Baumdarstellung P4-freier Graphen	P4-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 P4-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 P4-Struktur eine Graphen schon festlegt, ob der Graph perfekt ist oder nicht, genauer: zwei Graphen mit gleicher P4-Struktur sind entweder beide perfekt oder beide nicht-perfekt.
Kontakt:	Tel.: 0221/470-6030 Fax: 0221/470-5160 contact@zpr.uni-koeln.de