Unendlicher Graph - LinkFang.de





Unendlicher Graph


Als unendlichen Graph bezeichnet man in der Graphentheorie einen Graphen, dessen Knoten- oder Kantenzahl unendlich ist. Spricht man hingegen von einem Graphen so wird oft angenommen, dass Knoten- und Kantenzahl endlich sind. Ein Graph wird als wegendlich bezeichnet, falls er, trotz möglicherweise unendlich vieler Knoten, keinen unendlich langen Weg besitzt.

Aussagen über unendliche Graphen lassen sich häufig mittels eines Kompaktheitsarguments aus entsprechenden Aussagen über endliche Graphen ableiten. Beispielsweise ist jeder unendliche planare Graph vierfärbbar, weil dies für jeden endlichen planaren Graphen gilt. Dies beruht auf dem Lemma von König.

Andere Aussagen sind nicht zwangsläufig auf unendliche Graphen übertragbar.

Beispiele

Cayley-Graphen unendlicher Gruppen [math]\Gamma[/math] sind Beispiele unendlicher Graphen mit sehr hoher Symmetrie. (Alle Elemente der Gruppe [math]\Gamma[/math] sind Symmetrien des Graphen.)

In vielen inner- und außermathematischen Anwendungen sind Expander-Graphen von Bedeutung.

Lokal endliche Graphen

Ein Graph heißt lokal endlich, wenn jeder Knoten nur endlich viele Nachbarn hat.

Feine Graphen

Eine in der Geometrischen Gruppentheorie wichtige Klasse von Graphen sind feine Graphen, sie umfassen lokal endliche Graphen und zum Beispiel den Farey-Graph.

Anwendung

In der Funktionalanalysis treten unendliche Graphen als sogenannte Bratteli-Diagramme bei der Untersuchung von AF-C*-Algebren auf.

Literatur

  • Dénes Kőnig: Theorie der endlichen und unendlichen Graphen. Kombinatorische Topologie der Streckenkomplexe, Akademische Verlagsgesellschaft, Leipzig 1936
  • Reinhard Diestel: Infinite graphs, Kapitel 8 in Reinhard Diestel: Graph theory. 4th [electronic] edition 2010. Corrected reprint 2012, Springer, 2012, ISBN 978-3-642-14278-9, S. 203–268 (englisch; Inhaltsverzeichnis )

Kategorien: Graphentheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Unendlicher Graph (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.