461
Results 1 to 7 of 7

Thread: 461

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

    461

    a) weggrade:
    knoten - weggrad
    1 - 1
    2 - 1
    3 - 1
    4 - 2
    5 - 2
    6 - 2

    kreise:
    { (3,5), (5,4), (4,3) }
    { (2,3), (3,5), (5,2) }

    b) keine ahnung.

    danke & grüße
    ines
    der unterschied zw. reifen & politikern ist, daß reifen ein mindestprofil brauchen.

  2. #2

    Title
    Principal
    Join Date
    Feb 2002
    Posts
    34
    Thanks
    0
    Thanked 0 Times in 0 Posts
    zu a:

    ich glaube, da fehlt noch {(2,3)(3,5)(5,4)(4,2)}.

    zu b:

    das scheint logisch:
    wenn ich von einem knoten k1 zu einem knoten k2 gehe, von diesem weiter zu einem knoten k3 usw., dann muß ich irgenwann einen knoten besuchen, an dem ich schon war (sonst bräuchte ich unendlich viele knoten). und wenn das der fall ist, schließe ich auf jeden fall einen kreis

    ciao

  3. #3

    Title
    Principal
    Join Date
    Jan 2002
    Posts
    60
    Thanks
    0
    Thanked 0 Times in 0 Posts
    hi

    zu b)

    mit nem indirekten beweis könnte man es beweisen:
    Annahme es gibt mindestens einen Graphen, wobei jeder knoten positiven weggrad besitzt, ohne Kreise.

    1. Kein Kreis -> Baum -> n-1 Kanten
    2. positiver Weggrad -> d(x)>=1 für alle Knoten (Anzahl n) -> Summe aller Weggrade aller Knoten größer gleich n -> mindestens n Kanten

    Widerspruch - also stimmt die behauptung bei (b)

    Roli

  4. #4
    catwoman's Avatar
    Title
    Hero
    Join Date
    Feb 2002
    Posts
    242
    Thanks
    0
    Thanked 0 Times in 0 Posts
    zu a)
    ja, hatte einen kreis übersehen.

    zu b)
    das was auch bei der montag-übung, aber das mathe-file dazu ist noch nicht online. werde morgen nochmal nachschauen.

    hab's mit vollständiger induktion versucht, so wie in der VO bei der kantenfolge. versteh's aber nicht wirklich.

    danke & grüße
    ines
    der unterschied zw. reifen & politikern ist, daß reifen ein mindestprofil brauchen.

  5. #5

    Title
    Principal
    Join Date
    Jan 2002
    Posts
    60
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @ines

    habs mit vollständiger Ind. kurz probiert, bin aber auf keine grünen Zweig gekommen - das mit indirekter Beweis und Widerspruch dürft aber schon hinkommen

    mfg
    Roli

  6. #6

    Title
    Principal
    Join Date
    Jan 2002
    Posts
    60
    Thanks
    0
    Thanked 0 Times in 0 Posts
    zu b)

    laut pdf auf infoworx (vom montag)

    Annahme:
    kein gerichteteter Kreis -> azyklisch -> (laut skriptum) gibt es mindestens einen Knoten mit d-(x)=0 und einen Knoten mit d+(x)=0 -> Widerspruch -> gerichteter Kreis.

    mfg
    Roli

  7. #7
    catwoman's Avatar
    Title
    Hero
    Join Date
    Feb 2002
    Posts
    242
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Original geschrieben von Roli
    zu b)

    laut pdf auf infoworx (vom montag)
    <snip>
    jaaa, danke!! mein pdf-reader konnte die mathematischen zeichen nicht lesen!!

    danke & grüße
    ines
    der unterschied zw. reifen & politikern ist, daß reifen ein mindestprofil brauchen.

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
  •