Direkt zum Inhalt

Lexikon der Mathematik: Graphenhomomorphismus

Paar von Abbildungen zwischen zwei Graphen der folgenden Art.

Ein Graphenhomomorphismus von einem Graphen G in einen Graphen H besteht aus zwei Abbildungen f : E(G) → E(H) sowie F : K(G) → K(H), die für alle k = xyK(G) die folgende Bedingung erfüllen: \begin{eqnarray}k=xy\Rightarrow F(k)=f(x)f(y).\end{eqnarray}

Sind die Abbildungen f und F bijektiv, so nennt man die Graphen G und H isomorph, in Zeichen GH.

Isomorphe Graphen werden als im wesentlichen gleich angesehen. Trotz aller Anstrengungen hat man bisher keinen polynomialen Algorithmus gefunden, um festzustellen, ob zwei beliebig gegebene Graphen isomorph sind. Dieses sogenannte Graphenisomorphieproblem ist eines der bekanntesten Probleme, dessen Komplexitätsstatus noch immer ungeklärt ist.

Ein Graph G wird selbstkomplementär genannt, wenn \(G\cong \bar{G}\) gilt, wobei \(\bar{G}\) der Komplementärgraph von G ist. Der Weg der Länge 3 oder der Kreis der Länge 5 sind Beispiele für selbstkomplementäre Graphen. Da der vollständige Graph Kn aus n(n − 1)/2 Kanten besteht, gibt es in einem selbstkomplementären Graphen mit n Ecken genau n(n − 1)/4 Kanten. Daher gilt für die Ordnung n eines selbstkomplementären Graphen notwendig n = 4p oder n = 4p + 1. H. Sachs (1962) und G. Ringel (1963) zeigten, daß es für jede natürliche Zahl p tatsächlich selbstkomplementäre Graphen der Ordnung 4p und 4p + 1 gibt.

Graphenhomomorphismen und -isomorphismen lassen sich entsprechend auch für gerichtete Graphen erklären.

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