„Freundschaftssatz“ – Versionsunterschied
aus Wikipedia, der freien Enzyklopädie
imported>Anonym~dewiki(31560) (''') |
(kein Unterschied)
|
Aktuelle Version vom 26. September 2017, 09:41 Uhr
Der Freundschaftssatz ist ein Lehrsatz aus dem mathematischen Gebiet der Graphentheorie. Er besagt anschaulich, dass es in einem Raum, in dem je zwei Personen genau einen gemeinsamen Freund haben, eine Person geben muss, die mit allen befreundet ist. Er wurde 1966 von Erdős, Rényi und Sós bewiesen.
Mathematische Formulierung
Wenn in einem endlichen Graphen je zwei Knoten genau einen gemeinsamen Nachbarn haben, dann gibt es einen Knoten, der zu allen anderen adjazent ist.
Der Freundschaftssatz gilt nicht für unendliche Graphen.
Endliche Graphen, die die Voraussetzungen des Freundschaftssatzes erfüllen, werden auch als Freundschaftsgraphen bezeichnet.
Literatur
- Erdős, Paul; Rényi, Alfréd; Sós, Vera T. (1966), "On a problem of graph theory", Studia Sci. Math. Hungar. 1: 215–235.
