グラフの行列について

質問

http://www.geocities.jp/ikuro_kotaro/koramu/307_mat3.htm
にある

「　固有値λはすべて実数でその和は０となる．
　　Σλi＝０
また，グラフが連結なとき，最大次数をΔとすると
　　｜λ｜≦Δ　　　　　　　　　　　　　　　　」

という二つのことがなぜ言えるのかがわかりません。
どなたか分かる方いましたら教えてください！

回答No.2

Tacosan · ベストアンサー

「絶対値最大の固有値」に限定する必要は全くありません. 実際, 証明中に「絶対値最大の固有値である」ことは出てきません.
固有ベクトル x の絶対値最大の成分を βi とします. A x = λi x の i行目は
ai1 β1 + ai2 β2 + ... + ain βn = λi βi
となりますが, 両辺の絶対値を取ってゴニョゴニョすると
ai1 |β1| + ai2 |β2| + ... + ain |βn| ≧ |λi| |βi|
が得られます. ここで両辺を |βi| で割ると「βi が絶対値最大」であることが使えて ai1 + ai2 + ... + ain ≧ |λi|
が得られます. 後は左辺の和と最大次数 Δ の関係を考えれば OK.

お礼

ありがとうございます！
結局ほとんど答え教えてもらったようで(^^;
多分また質問を載せることがあると思うので
もしよければまたお願いしますm(_ _)m

回答No.1

Tacosan

(自己ループを持たない) 単純グラフの隣接行列は
1. (すべての成分が 0 か 1 である) 実対称行列で
2. 対角成分はすべて 0 であり
3. 各行の成分の (絶対値の) 和は最大次数 Δ を超えない
という条件を満たします.
挙げられた性質は細かく見ると 3つにわかれて
1. 固有値はすべて実であり
2. その和は 0 であって
3. 固有値の絶対値は Δ を超えない
と書けますが, 実は条件の 1～3 がそれぞれ性質の 1～3 に対応します (それぞれの性質が対応する条件のみで証明できます).
1, 2 は調べたりよく考えたりすれば簡単. 3 はちょっと分かりにくいかもしれないけど, λ を隣接行列 A の固有値, それに対応する固有ベクトルを x = (x1, x2, ..., xn)^t とおきます. で, x の絶対値最大の成分を xi とおいて, Ax = λx の i行目を考えるとわりと単純.
ここまでをヒントに頑張ってみてください. 途中で詰まったら, 「どこまで処理できているのか」「どこで詰まったのか」を書いてくれればさらにフォローするかもしれません.

お礼

回答ありがとうございます！
色々とやってみたのですが、Ａｘ＝λｘのi行目を計算して、
（ｘi＝［β1,β2,...,βn］、λi・・・最大の固有値　として）
ａi1β1＋ａi2β2＋・・・＋ａinβn＝λiβi
という結果になったのですが、ここからの考え方が分かりません・・・

あと、ｘの絶対値最大の成分を考える理由は、
「絶対値最大の固有値に対応するから」ということでしょうか？
お時間許しましたら、あわせてよろしくお願いします。