Direkt zum Inhalt

Lexikon der Mathematik: Geschlecht eines Graphen

das minimale Geschlecht h einer orientierbaren Fläche Sh derart, daß der Graph eine kreuzungsfreie Einbettung in Sh besitzt (Einbettung eines Graphen).

Das Geschlecht des vollständigen Graphen Kn beträgt \begin{eqnarray}\lceil (n-3)(n-4)/12\rceil \end{eqnarray} für n ≥ 3, und das Geschlecht des vollständig bipartiten Graphen Kn, m ist \begin{eqnarray}\lceil (n-2)(m-2)/4\rceil \end{eqnarray} für n, m ≥ 2.

Die Bestimmung des Geschlechts eines Graphen ist ein NP-schweres Problem.

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