Teilgraphen und Untergraphen

 Ein Graph kann in einem anderen enthalten sein:

Definition (Teilgraph)

Seien G = (E, K) und G′ = (E′, K′) Graphen. Dann heißt G′ ein Teilgraph von G, falls E′ ⊆ E und K′ ⊆ K.

 Ein Teilgraph eines Graphen entsteht, indem wir gewisse Ecken und Kanten des Graphen streichen. Damit durch diese Reduktion ein Graph entsteht, müssen wir, wenn wir eine Ecke entfernen, auch alle Kanten entfernen, die diese Ecke enthalten. Eine Kante können wir dagegen ohne Einschränkung hinauswerfen (dadurch entstehen möglicherweise isolierte Ecken, was nicht stört).

 Eine Verstärkung des Begriffs eines Teilgraphen ist:

Definition (Untergraph)

Sei G′ = (E′, K′) ein Teilgraph von G = (E, K). Dann heißt G′ ein Untergraph von G, falls gilt:

K′  =  { ab  ∈  K | a, b  ∈  E′ }.

 Ein Untergraph ist durch seine Eckenmenge E′ vollkommen bestimmt. Er entsteht aus G, indem wir bestimmte Ecken samt den zugehörigen Kanten streichen. Kanten, die zwei nicht entfernte Ecken verbinden, bleiben erhalten. Ein Untergraph ist in diesem Sinne eine minimale Verkleinerung: Wir streichen Ecken, behalten aber so viele Kanten wie möglich.

Beispiele

(1)

Jeder Graph ist ein Untergraph von sich selbst.

(2)

Sei n ≥ 1. Dann ist jeder Graph mit der Eckenmenge { 1, …, n } ein Teilgraph des vollständigen Graphen Kn. Allgemeiner gilt dies für jeden Graphen, dessen Eckenmenge eine Teilmenge von { 1, …, n } ist.

(3)

Ist m ≤ n, so ist der Graph Km ein Untergraph des Graphen Kn.

(4)

Sei n ≥ 3. Dann ist der Kreis Cn ein Teilgraph des Graphen Kn. Er ist genau dann ein Untergraph des Kn, wenn n = 3.

 Jede nichtleere Teilmenge E′ von E definiert genau einen Untergraphen von G, und jeder Untergraph von G ist durch seine Eckenmenge E′ ⊆ E bestimmt. Ist |E| = n, so gibt es also genau 2n − 1 Untergraphen von G. Denn es gibt genau 2n − 1 nichtleere Teilmengen einer n-elementigen Menge.

ema21-AbbID2-1-15

Ein Graph G (links) und zwei Untergraphen, die durch Streichen von zuerst 7 und dann 4 entstehen

ema21-AbbID2-1-16

Der Graph G und zwei Teilgraphen, die keine Untergraphen von G sind

 Teilgraphen eignen sich, um Graphentypen innerhalb eines Graphen zu untersuchen. Ein Beispiel ist:

Definition (enthaltener Kreis)

Ein Graph G = (E, K) enthält einen Kreis der Länge n ≥ 3, falls es einen Teilgraphen von G der Ordnung n gibt, der ein Kreis ist.

 Natürlich könnten wir auch direkt definieren: G enthält einen Kreis der Länge n ≥ 3, falls es paarweise verschiedene Ecken e1, …, en in E gibt mit eiei + 1  ∈  K für i = 1, …, n − 2 und ene1  ∈  K. Die Definition über Teilgraphen ist aber kompakter und für jeden Graphentyp einsetzbar. So sind zum Beispiel analog definiert:

G enthält einen vollständigen Graphen mit 5 Ecken.

G enthält einen bipartiten Graphen mit einer Bipartition des Typs 3−7.