Direkt zum Inhalt

Lexikon der Mathematik: Teilgraph

Subgraph oder Untergraph H eines Graphen G, ein Graph, der aus einer Eckenmenge E(H) ⊆ E(G) und einer Kantenmenge K(H) ⊆ K(G) besteht. Man sagt dann auch, daß G ein Obergraph oder Supergraph von H sei. Gilt zusätzlich E(H) = E(G), so ist H ein Faktor, erzeugender oder aufspannender Untergraph von G.

Es sei G ein Graph und AE(G). Derjenige Teilgraph von G, der aus der Eckenmenge A und allen Kanten von G besteht, die nur mit Ecken aus A inzidieren, heißt der von A induzierte Teilgraph, in Zeichen G[A].

Es seien G ein Graph, E′ ⊂ E(G) und K′ ⊆ K(G). Derjenige Teilgraph von G, der aus K′ und allen Ecken von G besteht, die mit Kanten aus K′ inzidieren, heißt der von K′ induzierte Teilgraph, in Zeichen G[K′ ]. Für den induzierten Teilgraphen G[E(G) \ E′ ] schreibt man kurz GE′, und der Faktor GK′ besitzt die Eckenmenge E(G) und die Kantenmenge K(G) − K′. Besteht E′ nur aus einer einzigen Ecke v oder K′ nur aus einer einzigen Kante k, so schreibt man auch Gv für G − {v} und Gk für G − {k}. Anschaulich gesprochen ist GE′ durch das Entfernen von Ecken bzw. GK′ durch das Entfernen von Kanten entstanden.

Auch das Hinzufügen von Kanten ist eine wichtige Operation in der Graphentheorie. Es seien x und y zwei nicht adjazente Ecken eines Graphen G. Fügt man zu G eine neue Kante k = xy hinzu, so schreibt man dafür G + k oder G + xy.

Einen vollständigen Teilgraphen H eines Graphen G nennt man Clique von G. Die Ordnung einer größten Clique in G heißt Cliquenzahl von G, in Zeichen ω(G).

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos