Unendlicher Graph

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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.

Der Cayleygraph der freien Gruppe mit zwei Erzeugern a und b

Cayley-Graphen unendlicher Gruppen sind Beispiele unendlicher Graphen mit sehr hoher Symmetrie. (Alle Elemente der Gruppe sind Symmetrien des Graphen.)

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

Lokal endliche Graphen

[Bearbeiten | Quelltext bearbeiten]

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

Farey-Graph: Knoten entsprechen , die Kante existiert falls

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

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

Zu den Sätzen über endliche Graphen, die Erweiterungen auf unendliche Graphen haben, gehören:

  • 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)

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. R. Aharoni, C. S. J. A. Nash-Williams, S. Shelah,. Marriage in infinite societies, in: Progress in Graph Theory (Waterloo, Ontario, 1982), Academic Press, Toronto, 1984, S. 71–79
  2. R. Aharoni, C. S. J. A. Nash-Williams, S. Shelah, A general criterion for the existence of transversals, Proceedings of the London Mathematical Society, Band 3, 1983, S. 43–68.
  3. R. Aharoni, C. S. J. A. Nash-Williams, S. Shelah, Another Form of a Criterion for the Existence of Transversals, Journal of the London Mathematical Society, Band 2, 1984, S. 193–203
  4. Aharoni, König's duality theorem for infinite bipartite graphs, Journal of the London Mathematical Society, Band 2, 1984, S. 1–12
  5. Aharoni, On a duality principle in infinite bipartite graphs, Journal of the London Mathematical Society, Band 2, 1983, S. 385–392
  6. R. Aharoni, E. Berger, Menger’s theorem for infinite graphs, Inventiones Mathematicae, Band 176, 2009, S. 1–62