Beweis Verständnis Graphen

Neue Frage »

götzinho Auf diesen Beitrag antworten »
Beweis Verständnis Graphen
Moin,
ich komm nicht ganz hinter den folgenden Beweis bzw. eigentlich nur das Ende. Vielleicht kann mir jemand von euch dabei behilflich sein? Wäre super! Eigentlich kanns nicht sooo schwer sein. verwirrt

Satz : If is a k-regular graph, then is an eigenvalue with multiplicity (Vielfachheit) equal to the number of connected components of .

Beweis:
We have already proved the first part (Also das mit dem Eigenwert =k (ist ok)).
Let be an eigenvector of A with eigenvalue k. Without loss of generality, suppose and . Then,



This means, that every j for which we must have . In particular, this is true for all which is adjacent to . (BIS HIER IST MIR ALLES KLAR, WAS JETZT KOMMT VERSTEH ICH NICHT MEHR). Repeating the argument with each of the neighbouring vertices, we deduce that if is connected to . As we may duplicate this argument for each component, the result is now clear.

Also den Großteil des Beweises kann ich nachvollziehen. Den vorletzten Satz versteh ich nicht mehr ganz. Wie kann man aus dem was da steht auf die Vielfachheit des Eigenwertes k schließen? Das will man ja hiermit zeigen. Wäre super, wenn mir damit jemand auf die Sprünge helfen könnte.


smile Danke schön.
götzinho Auf diesen Beitrag antworten »
RE: Beweis Verständnis Graphen
Mir ist da ein Fehler unterlaufen, es muss heißen anstatt .

Also das man das als max. annehmen kann kommt sicher daher, dass die Eigenvektoren nicht eindeutig ist und man daher einen wählen könnte, in dem maximal ist, oder?

Dann gehts weiter:

ist klar aufgrund der Eigenwert gleichung .
Hier ist ja der Eigenwert und die erste Komponente des Eigenvektor. Daher folgt einfach


da ja nur die erste Zeile von in der Summe steht. Allles klar!

Der Ausdruck ist eben kleiner als , da wir maximal angenommen haben.

Aber wieso ist das jetzt wieder gleich ? Das fällt mir jetzt erst auf. Machst das überhaupt Sinn? Ist da nicht irgendwas faul?
götzinho Auf diesen Beitrag antworten »
RE: Beweis Verständnis Graphen
Irgendwann machts dann einfach klick Augenzwinkern

Stimmt, es sind ja in jeder Spalte bzw. Zeile k Einsen und der Rest Nullen. Daher kommt das rechte Gleichzeichen nat. auch hin.

ok!

Das für alle dann gelten muss ist klar, da sonst eben keine Gleichheit gelten kann. Das gilt eben für alle adjazenten Ecken, da für diese Ecken i und j eben gilt. ok!

Wie gehts dann aber weiter? Warum kann man dann durch Wiederholen des Argumentes erhalten, dass dann auch für alle weiteren Ecken j, die mit x_1 verbunden sind gilt ? Und was soll das dann mit dem duplicate?
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »