450
Results 1 to 7 of 7

Thread: 450

  1. #1

    Title
    Principal
    Join Date
    Feb 2002
    Posts
    25
    Thanks
    0
    Thanked 0 Times in 0 Posts

    450

    .... wo sind die Graphenspezialisten unter Euch?

  2. #2

    Title
    Veteran
    Join Date
    Mar 2002
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    bsp450

    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

  3. #3
    catwoman's Avatar
    Title
    Hero
    Join Date
    Feb 2002
    Posts
    242
    Thanks
    0
    Thanked 0 Times in 0 Posts

    beweis

    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

  4. #4

    Title
    Principal
    Join Date
    Jan 2002
    Posts
    60
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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

  5. #5
    steve's Avatar
    Title
    Super Moderator
    Join Date
    Jan 2002
    Location
    planet earth
    Posts
    539
    Thanks
    14
    Thanked 2 Times in 2 Posts
    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?
    -----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------ .

  6. #6

    Title
    Principal
    Join Date
    Jan 2002
    Posts
    60
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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
    Last edited by Roli; 18-04-2002 at 02:25.

  7. #7
    steve's Avatar
    Title
    Super Moderator
    Join Date
    Jan 2002
    Location
    planet earth
    Posts
    539
    Thanks
    14
    Thanked 2 Times in 2 Posts
    supa, jetzt hab ichs verstanden. 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------ .

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •