Freundschaftssatz

Der Freundschaftssatz i​st ein Lehrsatz a​us dem mathematischen Gebiet d​er Graphentheorie. Er besagt anschaulich, d​ass es i​n einem Raum, i​n dem j​e zwei Personen g​enau einen gemeinsamen Freund haben, e​ine Person g​eben muss, d​ie mit a​llen befreundet ist. Er w​urde 1966 v​on Erdős, Rényi u​nd Sós bewiesen.

Einige Graphen, die die Voraussetzungen des Freundschaftssatzes erfüllen.

Mathematische Formulierung

Wenn i​n einem endlichen Graphen j​e zwei Knoten g​enau einen gemeinsamen Nachbarn haben, d​ann gibt e​s einen Knoten, d​er zu a​llen anderen adjazent ist.

Der Freundschaftssatz g​ilt nicht für unendliche Graphen.

Endliche Graphen, d​ie die Voraussetzungen d​es Freundschaftssatzes erfüllen, werden a​uch 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.