Grin logo
en de es fr
Shop
GRIN Website
Publish your texts - enjoy our full service for authors
Go to shop › Mathematics - Miscellaneous

Graphentheorie. Zum Beweis von Hadwigers Vermutung für Kantengraphen

Title: Graphentheorie. Zum Beweis von Hadwigers Vermutung für Kantengraphen

Bachelor Thesis , 2017 , 17 Pages , Grade: 1,7

Autor:in: Anonym (Author)

Mathematics - Miscellaneous
Excerpt & Details   Look inside the ebook
Summary Excerpt Details

Eines der größten Probleme der Graphentheorie ist das (Ecken)-Färbungsproblem. Mathematiker haben großes Interesse daran, Erkenntnisse für die sogenannte chromatische Zahl (G) eines Graphen zu erzielen. Eine der wohl bekanntesten und plausibelsten Abschätzungen besagt, dass wir mindestens die gleiche Anzahl an Farben benötigen, wie wir Knoten in der größtmöglichen Clique des zu färbenden Graphen haben. Nehmen wir nun einmal an, dass uns die chromatische Zahl eines Graphen bereits vorliegt. Die Frage, die sich nun stellt ist: In wie weit kann man dadurch Aussagen über die im Graphen enthaltenen Cliquen machen? Diese und andere Fragen stellte sich der Mathematiker Hugo Hadwiger Mitte des 20. Jahrhunderts und präsentierte sie in Form einer Vermutung der mathematischen Öffentlichkeit. Bis heute gibt es keinen vollständig erbrachten Beweis für die allgemeine Gültigkeit der Vermutung. Dennoch gibt es bis heute eine hohe Zahl an Resultaten bezüglich der Vermutung, die bewiesen werden konnten. Eines dieser Ergebnisse wollen wir in dieser Arbeit behandeln: den Beweis von Hadwigers Vermutung für Kantengraphen.

Excerpt


Inhaltsverzeichnis

  • Einleitung
    • Grundlagen
    • Die Vermutung
  • Vorbereitungen
    • Mengers Satz
    • Vizings Adjazenz-Lemma
  • Der Beweis für Kantengraphen

Zielsetzung und Themenschwerpunkte

Diese Arbeit beschäftigt sich mit Hadwigers Vermutung in der Graphentheorie. Die Vermutung besagt, dass für jeden einfachen, endlichen Graphen G die chromatische Zahl X(G) größer oder gleich der Anzahl der Knoten im kleinsten vollständigen Graphen Kn ist, der als Minor in G enthalten ist.

  • Die chromatische Zahl und ihre Beziehung zur Clique-Zahl
  • Hadwigers Vermutung und ihre verschiedenen Beweise
  • Die Bedeutung von Kantengraphen und ihre Rolle bei der Verifizierung der Vermutung
  • Die verschiedenen Ansätze zur Beweisfindung und die Herausforderungen bei der allgemeinen Gültigkeit
  • Wichtige Resultate und Erweiterungen der Vermutung für verschiedene Graphenklassen

Zusammenfassung der Kapitel

Einleitung

Die Arbeit beginnt mit einer Einführung in die grundlegenden Konzepte der Graphentheorie, insbesondere die chromatische Zahl und die Clique-Zahl. Es wird erläutert, wie die Vermutung von Hadwiger entstanden ist und welche Bedeutung sie für die Graphentheorie hat.

Vorbereitungen

Dieses Kapitel führt wichtige Sätze und Lemmata ein, die für den Beweis von Hadwigers Vermutung für Kantengraphen relevant sind. Hierzu gehören Mengers Satz und Vizings Adjazenz-Lemma.

Schlüsselwörter

Die Arbeit konzentriert sich auf die zentralen Themen der Graphentheorie, insbesondere die chromatische Zahl, Clique-Zahl, Hadwigers Vermutung, Kantengraphen, Minor, Kantenkontraktion und relevante Sätze und Lemmata wie Mengers Satz und Vizings Adjazenz-Lemma.

Excerpt out of 17 pages  - scroll top

Details

Title
Graphentheorie. Zum Beweis von Hadwigers Vermutung für Kantengraphen
College
LMU Munich
Grade
1,7
Author
Anonym (Author)
Publication Year
2017
Pages
17
Catalog Number
V916377
ISBN (eBook)
9783346233882
ISBN (Book)
9783346233899
Language
German
Tags
graphentheorie beweis hadwigers vermutung kantengraphen
Product Safety
GRIN Publishing GmbH
Quote paper
Anonym (Author), 2017, Graphentheorie. Zum Beweis von Hadwigers Vermutung für Kantengraphen, Munich, GRIN Verlag, https://www.grin.com/document/916377
Look inside the ebook
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
Excerpt from  17  pages
Grin logo
  • Grin.com
  • Payment & Shipping
  • Contact
  • Privacy
  • Terms
  • Imprint