imported>일성김: Aus unendlicher Knotenzahl folgt auch unendliche Kantenzahl, jedenfalls wenn man keine isolierten Knoten will. Die letzte Textänderung von 2A0A:A541:F43E:0:8DBC:DB98:463:C5C2 wurde verworfen und die Version 226169547 von Neuroxic wiederhergestellt.

2023-06-11T20:29:57Z

Aus unendlicher Knotenzahl folgt auch unendliche Kantenzahl, jedenfalls wenn man keine isolierten Knoten will. Die letzte Textänderung von 2A0A:A541:F43E:0:8DBC:DB98:463:C5C2 wurde verworfen und die Version 226169547 von Neuroxic wiederhergestellt.

Neue Seite

Als '''unendlichen Graph''' bezeichnet man in der [[Graphentheorie]] einen [[Graph (Graphentheorie)|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 (Graphentheorie)|Weg]] besitzt.

Aussagen über unendliche Graphen lassen sich häufig mittels eines [[Kompaktheitssatz (Logik)|Kompaktheitsarguments]] aus entsprechenden Aussagen über endliche Graphen ableiten. Beispielsweise ist jeder unendliche planare Graph [[Vier-Farben-Satz|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.
[[Datei:Cayley graph of F2.svg|right|thumb|Der Cayleygraph der [[Freie Gruppe|freien Gruppe]] mit zwei Erzeugern ''a'' und ''b'']]

== Beispiele==
[[Cayley-Graph]]en 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-Graph]]en von Bedeutung.

== Lokal endliche Graphen ==
Ein Graph heißt ''lokal endlich'', wenn jeder Knoten nur endlich viele Nachbarn hat.
[[Datei:Farey diagram circle packing 5.svg|thumb|[[Farey-Graph]]: Knoten entsprechen <math>\Q\cup\infty</math>, die Kante <math>(p/q, r/s)</math> existiert falls <math>|ps -rq|=1</math>]]

== Feine Graphen ==
Eine in der [[Geometrische Gruppentheorie|geometrischen Gruppentheorie]] wichtige Klasse von Graphen sind [[Feiner Graph|feine Graphen]], sie umfassen lokal endliche Graphen und zum Beispiel den [[Farey-Graph]].

== Anwendung ==
In der [[Funktionalanalysis]] treten unendliche Graphen als sogenannte [[Bratteli-Diagramm]]e bei der Untersuchung von [[AF-C*-Algebra|AF-C*-Algebren]] auf.

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

*der [[Heiratssatz]] von [[Philip Hall]], bewiesen von [[Ron Aharoni]], [[Crispin Nash-Williams]] und [[Saharon Shelah]].<ref>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</ref><ref>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.</ref><ref>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</ref> Ebenso auf den unendlichen Fall übertragbar sind die Verallgemeinerung des Heiratssatzes von Richard Rado und der [[Satz von Dilworth]].
*Der [[Satz von König (Graphentheorie)|Satz von König]], wie schon [[Paul Erdős]] vermutete und wie Aharoni bewies.<ref>Aharoni, König's duality theorem for infinite bipartite graphs, Journal of the London Mathematical Society, Band 2, 1984, S. 1–12</ref><ref>Aharoni, On a duality principle in infinite bipartite graphs, Journal of the London Mathematical Society, Band 2, 1983, S. 385–392</ref>
*der [[Satz von Menger]], bewiesen von Aharoni und [[Eli Berger]].<ref>R. Aharoni, E. Berger, Menger’s theorem for infinite graphs, Inventiones Mathematicae, Band 176, 2009, S. 1–62</ref>

== 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; [http://d-nb.info/1003136702/04 Inhaltsverzeichnis])
==Einzelnachweise==
<references />

[[Kategorie:Graphentheorie]]
[[Kategorie:Graphenklasse]]

Unendlicher Graph - Versionsgeschichte

imported>일성김: Aus unendlicher Knotenzahl folgt auch unendliche Kantenzahl, jedenfalls wenn man keine isolierten Knoten will. Die letzte Textänderung von 2A0A:A541:F43E:0:8DBC:DB98:463:C5C2 wurde verworfen und die Version 226169547 von Neuroxic wiederhergestellt.