461

[catwoman]

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

[Aasgeier]

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

[Roli]

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

[catwoman]

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

[Roli]

@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

[Roli]

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

[catwoman]

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