450

[Ronnsn]

.... wo sind die Graphenspezialisten unter Euch?

[jethro]

Knoten V(G) verschiedene personen
Kanten E(G) sind miteinander bekannt
Grad d(x) eines Knotens Anzahl der Bekannten

wir nehmen ein Beispiel n Personen n=6

zeichen dies auf: 6 punkte und Verbindungen:

1 nach 4
2 nach 5
2 nach 6
3 keine verbindung

dann ist:

d(1)=1
d(2)=2
d(3)=0
d(4)=1
d(5)=1
d(6)=1

Knoten V(G) ={1,....,6}
Kanten E(G) = {(1,4),(2,6),(2,5)}

-> schlichter graph (keine Mehrfachkanten, keine Schlingen)
muß nicht zusammenhängend sein

grüße
jethro

[catwoman]

ein richtiger beweis oder so fällt mir nicht ein.
prof. kaiser hat heute gesagt, "die graphentheorie ist so super, weil keine formalen beweise notwendig sind" & hat danach aber gleich einen satz formal bewiesen. also ich kenne mich nicht aus.

jedenfalls. ich nehme 2 knoten her. wenn die keine verbindung haben, kennen die beiden personen sich nicht. sie haben also die gleiche anzahl an bekannten, nämlich 0. detto wenn es eine kante gibt: dann kennen beide 1 person.

dh. sobald ich bei n knoten 1 kante ziehe, ist es schon so, daß mindestens 2 die gleiche anzahl an bekannten haben. & das bleibt auch so, wenn mehr kanten dazukommen.

danke & grüße
ines

[Roli]

hi

es gibt schon nen "Beweis" (indirekter Beweis):

hat man n Knoten - so kann d(x) zwischen 0 und n-1 liegen und es gibt somit n Möglichkeiten für d(x)

-> das heißt, das jeder Grad prinzipiell einmal vorkommen kann

für x1 wählt man z.b. 0 so können alle anderen nur n-2 Leute kennen, weil sie sich selbst und auch x1 nicht kennen können

daraus folgt, daß x2 bis xn (n-1 knoten) mindestens 1 person und maximal n-2 Personen kennen können -> nur n-2 Grad -> keine injektive Abbildung möglich!

mfg
Roli

[steve]

Kann das nochmal wer langsam erklären?

und:
daraus folgt, daß x2 bis xn (n-1 knoten) mindestens 1 person und maximal n-2 Personen kennen können
können die anderen leute nicht auch 0 personen kennen?

[Roli]

Original geschrieben von steve
Kann das nochmal wer langsam erklären?

und:

können die anderen leute nicht auch 0 personen kennen?

hmm
werds noch mal versuchen:
Indirekter Beweis:
Wir versuchen zu beweisen, daß jede Person eine andere Anzahl von anderen Personen kennt.
zb. 1. Person kennt 0 Leute, 2.Person 1, 3.Person 2 usw.

Da eine Person sich selbst nicht kennen darf - kann man maximal n-1 Personen kennen.

-> eine Person kann zwischen 0 und n-1 Personen kennen.

Nun setzen wir an, daß die 1. Person keinen kennt: d(x1)=0

Da wir beweisen wollen, daß jede Person eine andere Anzahl von Personen kennt, dürfen die anderen Personen (x2 bis xn) nur mehr als 0 Leute kennen.

Das heißt, daß x2 bis xn 1 bis n-1 Leute kennen dürfen.

Man muß aber weiters beachten, daß x1 niemanden kennt und somit auch von niemanden (x2 bis xn) gekannt wird! Das heißt x2 bis xn können maximal n-2 Personen kennen (n minus sich selbst und x1 -> n-2)

x2 bis xn -> n-1 Personen
1 bis n-2 -> n-2 Kanten

hier haben wir einen wiederspruch, weil mindestens 2 Personen die geiche Anzahl von Bekannten haben müssen! Hier ist eine surjektive und keine injektive Abbildung von Personen zu Bekannten!

ich hoffe das erklärts besser

mfg
Roli

[steve]

supa, jetzt hab ichs verstanden. :thumb: vorher kleinen knoten im hirn ghabt.