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
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.
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
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
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.
@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
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
jaaa, danke!! mein pdf-reader konnte die mathematischen zeichen nicht lesen!!Original geschrieben von Roli
zu b)
laut pdf auf infoworx (vom montag)
<snip>
danke & grüße
ines
der unterschied zw. reifen & politikern ist, daß reifen ein mindestprofil brauchen.
Bookmarks