WisFaq!

De digitale vraagbaak voor het wiskundeonderwijs

HOME

samengevat

\require{AMSmath}

Eigenwaarden en eigenvektoren van een k-regulier graaf

Beste wisfaq,

Ik heb een k-reguliere niet- gerichte graaf met n knooppunten. Ik wil graag de volgende drie punten aantonen voor deze graaf:

Voor een k-regulier graaf G met adjacency matrix A geldt dat:

(1) Als L een eigenwaarde is van A, dan |L|=Bewijs
Als G k-regulier is dan is Delta(G)=k. Nu geldt voor een eigenwaarde L van de adjacency matrix dat : |L|Vraag 1.Waarom is |L|
Vraag2. Waarom is L1=k ?

(2) k is een eigenwaarde van A.
Bewijs
Zij y=(1,1,..,1) een kolomvektor. Laat Ay=(b1, b2,...,bn). Dan:

b_i=SOM[(A(i,j))y_j]=SOM[A(i,j)]=deg(v_i)=k (som van j=1...n)

Dus Ay=(k,k,...,k)= (inwendig product).

Dus de vektor y=(1,1,...,1) is een eigenvektor van A met eigenwaarde k.

Als ik het goed begrijp is dus y=(1,1,...,1) de eigenvektor die hoort bij L1=k .
En z1=(1/wortel(n), 1/wortel(n),..., 1/wortel(n)) is dan de genormalizeerde eigenvektor?

3)Alle knooppunten vi in een k-regulier graaf hebben dezelfde eigenwaarde centraliteit.

De eigenwaarde centraliteit is Ax=L1*x met x=(x1, x2,...,xn).

En xi is de centraliteit van ieder knooppunt i:

xi=(1/L1)*SOM[A(i,j)*x_j] over alle j.

Ieder knooppunt heeft hetzelfde aantal buren, k buren. Dus de waarde van SOM[A(i,j)*x_j] is voor alle knooppunten hetzelfde, L1 is een vast getal dus de eigenwaarde centraliteit is hetzelfde voor alle knooppunten. Is dit correct?

Vriendelijke groeten, dank,

Viky
Viky
Iets anders - maandag 4 maart 2013

Antwoord

1. Kijk naar een eigenvector $\mathbf{x}$ bij eigenwaarde $\lambda$ en neem een coordinaat $x_i$ met maximale absolute waarde; dan geldt $\lambda x_i=\sum_{j \text{ buur van }i}x_j$. Pas de driehoeksongelijkheid toe en de ongelijkheden $|x_j|\le|x_i$, je vindt $|\lambda x_i|\le k|x_i$.
Hierboven is bewezen dat $|\lambda|\le\Delta(G)=k$; ik denk dat $\lambda<\Delta(G)$ in eerste instantie te sterk is.
2. Ik neem aan dat je met $L_1$ de eigenwaarde met grootste absolute waarde bedoelt; dan laat de vector $(1,1,\ldots,1)$ inderdaad zien dat $L_1=k$.
3. Klopt

kphart

Vragen naar aanleiding van dit antwoord? Klik rechts..!
donderdag 7 maart 2013