グラフの最大固有値が任意のサブグラフの最大固有値よりも厳密に大きいことを示す

2
José 2019-04-04 13:09.

Gを連結グラフ、HをGの適切なサブグラフ(Gの少なくとも1つのエッジまたは少なくとも1つの頂点を削除して得られる)とします。A(G)の最大固有値がA(H)の大きい固有値よりも厳密に大きいことを示します。

問題の固有値は、隣接行列の固有値です。エッジ/頂点を削除することで、インデックスを次のように変換していると推論してみました$0$、しかしそれはどこにも通じていないようです。

1 answers

3
Misha Lavrov 2019-04-05 06:12.

対称行列の最大固有値を特定する1つの方法 $A$ 次の特性によるものです:それはの最大値です $\mathbf x^{\mathsf T}\!A\mathbf x$ 全体 $\mathbf x$$\|\mathbf x\|=1$、さらに、最大値を達成することができます $\mathbf x$対応する固有ベクトルになります。これを見るには、$\mathbf x = c_1 \mathbf v^{(1)} + \dots + c_n \mathbf v^{(n)}$ の正規直交固有ベクトルに基づいて $A$。次に$c_1^2 + \dots + c_n^2 = 1$ そして $\mathbf x^{\mathsf T}\!A\mathbf x = \lambda_1 c_1^2 + \dots + \lambda_n c_n^2$。場合$\lambda_n$ は最大の固有値であり、これは設定することで最大化されます $c_n = \pm1$ および他のすべて $c_i$$0$

また、 $A$ ここにあるように、非負です。 $\lambda_n$非負の固有ベクトルを持っています。これを確認するには、各コンポーネントを交換する場合に注意してください$x_i$$\mathbf x$ 沿って $|x_i|$、次にの値 $\mathbf x^{\mathsf T}\!A\mathbf x$ 増加することしかできません。


さて、グラフ理論に移りましょう。

私たちは常に仮定することができます $H$ と同じ数の頂点があります $G$; 頂点が少ないサブグラフの場合は、孤立した頂点をいくつか追加してパディングします(これにより、ゼロ行のみが提供されます)。しましょう$\lambda_n(G), \lambda_n(H)$ 隣接行列の最大の固有値である $A_G, A_H$、そして $\mathbf w$ の非負の単位固有ベクトルである $A_H$ 対応する $\lambda_n(H)$。次に$$ \lambda_n(H) = \sup_{\mathbf x \in \mathbb R^n : \|\mathbf x\|=1} \mathbf x^{\mathsf T}\!A_H\mathbf x = \mathbf w^{\mathsf T}\!A_H\mathbf w \le \mathbf w^{\mathsf T}\!A_G\mathbf w \le \sup_{\mathbf x \in \mathbb R^n : \|\mathbf x\|=1} \mathbf x^{\mathsf T}\!A_G\mathbf x = \lambda_n(G) $$ 中間の不等式が成り立つのは、 $(i,j)$-のエントリ $A_H$ から $0$$1$、それは非負の量で乗算されます $w_i w_j$

不平等の厳しさは、2つの場所のいずれかから生じる可能性があります。最初に注意してください$\mathbf w$ の固有ベクトルです $A_H$、その後 $\lambda_n(H)w_i$ の合計です $w_j$ すべての頂点にわたって $j$ に隣接 $i$。だからもし$w_i$ です $0$、その後 $w_j=0$ すべてのために $j$ に隣接 $i$、つまり $\mathbf w$ 接続されているコンポーネント全体で消える $i$。そう:

  • 場合 $H$ だけでなく接続されています $G$、次にのすべてのエントリ $\mathbf w$ ポジティブであるため、 $\mathbf w^{\mathsf T}\!A_H\mathbf w$$\mathbf w^{\mathsf T}\!A_G\mathbf w$。最初$\le$ です $<$
  • 場合 $H$ 接続されていない場合、 $\mathbf w$接続されているコンポーネントの1つを除くすべてで消えます。しかしその後$\mathbf w$ は間違いなくの固有ベクトルではありません $A_G$:から行く $G$$H$、接続されたコンポーネントからエッジを追加することになります。これにより、次のゼロ以外の値が伝播されます。 $A_G\mathbf w$ 頂点へ $\mathbf w$消えた。二番目$\le$ です $<$ (それは $=$ の固有ベクトルの場合 $\lambda_n(G)$)。

Related questions

MORE COOL STUFF

ケイト・ブランシェットは3日間一緒に夫と一緒に寝て、25年経ってもまだ夫と結婚しています

ケイト・ブランシェットは3日間一緒に夫と一緒に寝て、25年経ってもまだ夫と結婚しています

ケイト・ブランシェットは、夫に会ったとき、典型的な交際のアドバイスに逆らいました。

マイケルシーンが非営利の俳優である理由

マイケルシーンが非営利の俳優である理由

マイケルシーンは非営利の俳優ですが、それは正確にはどういう意味ですか?

ホールマークスターのコリンエッグレスフィールドがRomaDramaLiveでスリル満点のファンと出会う![エクスクルーシブ]

ホールマークスターのコリンエッグレスフィールドがRomaDramaLiveでスリル満点のファンと出会う![エクスクルーシブ]

特徴的なスターのコリン・エッグレスフィールドは、RomaDrama Liveでのスリル満点のファンとの出会いについて料理しました!加えて、大会での彼のINSPIREプログラム。

「たどりつけば」をオンラインでストリーミングできない理由

「たどりつけば」をオンラインでストリーミングできない理由

ノーザンエクスポージャーが90年代の最も人気のある番組の1つになった理由を確認するには、Blu-rayまたはDVDプレーヤーをほこりで払う必要があります。

バイオニック読書はあなたをより速く読むことができますか?

バイオニック読書はあなたをより速く読むことができますか?

BionicReadingアプリの人気が爆発的に高まっています。しかし、それは本当にあなたを速読術にすることができますか?

ドミニカのボイリング湖:アクセスは簡単ではありませんが、ハイキングする価値があります

ドミニカのボイリング湖:アクセスは簡単ではありませんが、ハイキングする価値があります

ドミニカのボイリング湖は、世界で2番目に大きいボイリング湖です。そこにたどり着くまでのトレッキングは大変で長いですが、努力する価値は十分にあります。

私たちの水をきれいに保つのを助けるためにあなたの髪を寄付してください

私たちの水をきれいに保つのを助けるためにあなたの髪を寄付してください

サロンからのヘアトリミングや個人的な寄付は、油流出を吸収して環境を保護するのに役立つマットとして再利用できます。

ホワイトハウスの最も記憶に残る結婚式を見てください

ホワイトハウスの最も記憶に残る結婚式を見てください

過去200年以上の間にホワイトハウスで結婚したのはほんの数人です。彼らは誰でしたか、そしてそこで結婚式を獲得するために何が必要ですか?

驚くほど素晴らしいDropMixミュージックミキシングカードゲームは30ドルで驚くべき取引です

驚くほど素晴らしいDropMixミュージックミキシングカードゲームは30ドルで驚くべき取引です

DropMixはNFC対応のカードゲームで、基本的にはリミックスアーティストになります。現在、Amazonでは$ 30まで下がっており、これまでで最高の価格に匹敵します。ロックバンドで有名なHarmonixによって開発されたDropMixは、おそらく少し野心的すぎるように思われます。結局のところ、ほとんどの人は素晴らしいリズムを持っていませんが、ゲームは驚くほどうまく実行されます。

メアリーJ.ブライジがついにハリウッドウォークオブフェイムスターを獲得

メアリーJ.ブライジがついにハリウッドウォークオブフェイムスターを獲得

写真:APメアリーJ.ブライジは、間もなくハリウッドウォークオブフェイムのスターを獲得します。これは、メアリーJよりもハリウッドウォークオブフェイムのほうが正直なところ恩恵です。

MeltdownとSpectreの脆弱性についてこれまでに知っていることはすべて、簡単な方法で説明されています

MeltdownとSpectreの脆弱性についてこれまでに知っていることはすべて、簡単な方法で説明されています

画像:グラズ工科大学/ NataschaEiblがデザインしたロゴ。MeltdownとSpectreは、攻撃者がシステムメモリに保存されているあらゆる種類の情報にアクセスできるようにする2つの脆弱性に付けられた名前です。

彼のニューヨークの家から追い出されようとしている97歳の第二次世界大戦の獣医。メリーエフィングクリスマス

彼のニューヨークの家から追い出されようとしている97歳の第二次世界大戦の獣医。メリーエフィングクリスマス

日本人に襲われたときに真珠湾にいた97歳の第二次世界大戦のベテランが、ニューヨークのブルックリンから追い出されています。

Zendaya Wishes Boyfriend Tom Holland Happy Birthday with Cuddly Photo: He 'Makes Me the Happiest'

Zendaya Wishes Boyfriend Tom Holland Happy Birthday with Cuddly Photo: He 'Makes Me the Happiest'

Zendaya shared a sweet photo in honor of boyfriend Tom Holland's 26th birthday Wednesday

小さな女性:脳卒中を患った後に病院から解放されたアトランタのジューシーな赤ちゃん:「まだ癒し」

小さな女性:脳卒中を患った後に病院から解放されたアトランタのジューシーな赤ちゃん:「まだ癒し」

シーレン「Ms.JuicyBaby」ピアソンは、先月脳卒中で入院した後、「もう一度たくさんのことをする方法を学ばなければならない」ため、言語療法を受けていることを明らかにしました。

エマストーンは彼女のクリフサイドマリブビーチハウスを420万ドルでリストアップしています—中を見てください!

エマストーンは彼女のクリフサイドマリブビーチハウスを420万ドルでリストアップしています—中を見てください!

オスカー受賞者の世紀半ばの家には、3つのベッドルーム、2つのバス、オーシャンフロントの景色があります。

ジーニー・メイ・ジェンキンスは、母乳育児の経験の中で、彼女は「本当に、本当に落ち込んでいる」と言います

ジーニー・メイ・ジェンキンスは、母乳育児の経験の中で、彼女は「本当に、本当に落ち込んでいる」と言います

ジーニー・メイ・ジェンキンスは、生後4か月の娘、モナコに母乳育児をしていると語った。

投資ノート:Bioscout AU$300万シード

投資ノート:Bioscout AU$300万シード

Bioscoutは、農家を運転席に置くという使命を負っています。Artesian(GrainInnovate)やUniseedと並んで、最新のシードラウンドでチームを支援できることをうれしく思います。問題真菌症による重大な作物の損失は、農民にとって試練であることが証明されています。

リトルマーケットリサーチ1| 2022年のクイックグリンプス遠隔医療市場

リトルマーケットリサーチ1| 2022年のクイックグリンプス遠隔医療市場

遠隔医療は、パンデミック後の時代では新しいものではなく、時代遅れの分野でもありません。しかし、業界を詳しく見ると、需要と供給の強力な持続可能性と、米国で絶え間ない革命となる強力な潜在的成長曲線を示しています。

スタートアップ資金調達環境:タイのスタートアップエコシステムの次は何ですか?

スタートアップ資金調達環境:タイのスタートアップエコシステムの次は何ですか?

2021年は、世界的なベンチャーキャピタル(VC)の資金調達にとって記録的な年でした。DealStreetAsiaによると、東南アジアも例外ではなく、この地域では年間で記録的な25の新しいユニコーンが採掘されました。

ムーアの法則を超えて

ムーアの法則を超えて

計算に対する私たちの欲求とムーアの法則が提供できるものとの間には、指数関数的に増大するギャップがあります。私たちの文明は計算に基づいています—建築と想像力の現在の限界を超える技術を見つけなければなりません。

Language