Erstmal ein schönes neues Jahr an alle Informatiker!
Arbeite gerade ein wenig das Skript durch und bin bei Definition 5.5 (Seite 74)hängen geblieben. Es geht um die Vollständigkeit von Graphen:
(5.5) Ein Graph heißt vollständig wenn gilt:
((Allquantor)a€V) V/{a} (teilmenge) S(a)
(D.h.: Je zwei konnten sind miteinander verbunden).
Wobei S(a) wie folgt definiert ist:
S(a):= {b| b€V (und) {a,b}€E}
Gilt dann nicht eher:
((Allquantor)a€V) S(a) (teilmenge) V/{a}
!?
Denn S(a) enthält ja alle Knoten die aus V sind und mit a durch ein Kante verbunden sind. Das ist in meinen Augen richtig würde aber wohl in diesem Fall auch keinen Sinn machen.
Kann mir jemand helfen!? Wo liegt hier das Problem
S(a) < V\{a} gilt ja wohl in jedem beliebigen Graphen,
(wenn man von Schleifen an einem Knoten absieht, also (a,a)-Kanten)
egal ob ein Knoten mit einem, allen oder keinen anderen Knoten verbunden ist,
wird diese Bedingung immer gelten
(sonst bitte Gegenbeispiel was du meinst)
———
V\{a} < S(a) ist dagegen eine pfiffige und ausreichende Bedingung,
das bedeutet ja, dass jeder Knoten ausser a in S(a) drin sein muss,
also folgt direkt, dass a mit jedem anderen Knoten verbunden ist,
genau das möchte man doch haben
(gibt es keine a,a-Schleifen, dann gilt übrigens auch hier
wie in jedem Graphen die umgekehrte Bedingung V\{a} < S(a),
bringt aber keinen Erkenntnisgewinn)
S(a) < V\{a} gilt ja wohl in jedem beliebigen Graphen
Ja ok das mir Klar! Macht hier keinen Sinn
Mein Problem liegt dann wohl eher im richtigen Verständnis der Definition von S(a). Sind in S(a) nicht nur die Knoten enthalten die durch genau eine Kante mit a verbunden sind!?
Denn wenn b€S(a) so muss ja auch {a,b} € E sein!?
Wenn das so ist dann ist doch S(a) < V\{a} falsch!?
alles richtig, wenn b e S(a) dann {a,b} e E
für einen Graphen mit 4 Knoten a, b, c, d
ist bei Vollständigkeit
a mit b, c und d verbunden,
also b,c,d e S(a) und
{a,b},{a,c}, {a,d} e E
und S(a) = {b,c,d} < {b,c,d} = V \ {a}
(< heißt Teilmenge)
wo genau ist da ein Problem?
[img]
http://mokrates.de/cgi-bin/texstring?%5CGamma(a)[/img] ist immer eine Teilmenge von [img]
http://mokrates.de/cgi-bin/texstring?V%20%5Csetminus%20%5C%7Ba%5C%7D[/img], denn [img]
http://mokrates.de/cgi-bin/texstring?%5CGamma(a)[/img] ergibt einen Wert aus der Potenzmenge von V, wobei a selbst nicht in dieser Menge vorkommen kann, wenn es keine {a,a}-Kanten gibt.
wo genau ist da ein Problem?
Ich glaube mein Problem war das ich anschaulich an eine andere/falsche Vorstellung hatte. Also bedeutet vollständig, dass ein beliebiger knoten a durch genau ein Kante mit jedem anderen Knoten des Graphen verbunden ist?
Also bedeutet vollständig, dass ein beliebiger knoten a durch genau ein Kante mit jedem anderen Knoten des Graphen verbunden ist?
Ja, wobei beliebig hier jeder Knoten sein darf, also es muss nicht n ein Knoten mit allen verbunden sein, sondern jeder.
