Graphklassen

Graphklassen bezeichnet man in der Graphentheorie als Mengen von Graphen, die durch gemeinsame Merkmale oder durch operationale Beschränkungen definiert sind. Typischerweise ist eine Graphklasse isomorphieinvariant: Graphen, die zueinander isomorph sind, gehören gemeinsam zur Klasse. Oft werden Klassen durch Abschlüsse beschrieben, etwa durch den Untergraphenabschluss oder durch das Entfernen von Knoten oder Kanten.

Wichtige Beispiele sind planare Graphen, die sich zeichnen lassen, ohne dass sich Kanten kreuzen; Bäume, die zusammenhängend und acyclisch sind; vollständige Graphen K_n, die jede mögliche Kante besitzen; bipartite Graphen, die keine ungeraden Zyklen enthalten; sowie Zykelgraphen C_n, die aus einem einzelnen Kreis bestehen.

Charakterisierung: Viele Klassen lassen sich durch verbotene Untergraphen oder Minoren charakterisieren. Planarität lässt sich durch den Kuratowski-Satz ausdrücken: Ein Graph ist planar genau dann, wenn er keine Untergraphen enthält, die eine Subdivision von K_5 oder K_{3,3} enthalten. Bei minor-geschlossenen Klassen gilt das Robertson-Seymour-Theorem: Jede minor-geschlossene Klasse lässt sich durch eine endliche Menge verbotener Minoren charakterisieren.

Bedeutung: Graphklassen dienen der systematischen Strukturierungs- und Algorithmusforschung. Viele Probleme, wie Färbung, Kürzeste Wege oder Matching, lassen sich auf bestimmten Klassen effizient lösen, was die Praxisrelevanz der Theorie betont.

---