• 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

  • 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

    :catwoman: der unterschied zw. reifen & politikern ist, daß reifen ein mindestprofil brauchen.

  • 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

    Sex (female) is: grep; touch; unzip; touch; gasp; finger; gasp; mount; fsck; more; yes; gasp; umount; make clean; make mrproper


    Sex (male) is: grep; touch; strip; unzip; head; mount /dev/girl -t wet; fsck; fsck; yes; yes; yes; umount /dev/girl; zip; sleep or good

  • Kann das nochmal wer langsam erklären?


    und:

    Zitat

    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?

    -----BEGIN GEEK CODE BLOCK-----
    Version: 3.12
    GAT d-(+) s++: a- C++$>+$ U++>+++ P++>+++ L+++ !E W++>$ !N K? w(--)@ !O !M V? PS+ PE++(-)> Y+ PGP(+) t---(-) !5 X R- tv-(--) b++>$ DI+ D+(++) G(+) e>++++* h-- r++ y++
    ------END GEEK CODE BLOCK------ .

  • Zitat

    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

    Sex (female) is: grep; touch; unzip; touch; gasp; finger; gasp; mount; fsck; more; yes; gasp; umount; make clean; make mrproper


    Sex (male) is: grep; touch; strip; unzip; head; mount /dev/girl -t wet; fsck; fsck; yes; yes; yes; umount /dev/girl; zip; sleep or good

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

    -----BEGIN GEEK CODE BLOCK-----
    Version: 3.12
    GAT d-(+) s++: a- C++$>+$ U++>+++ P++>+++ L+++ !E W++>$ !N K? w(--)@ !O !M V? PS+ PE++(-)> Y+ PGP(+) t---(-) !5 X R- tv-(--) b++>$ DI+ D+(++) G(+) e>++++* h-- r++ y++
    ------END GEEK CODE BLOCK------ .