• 締切済み

接続行列の問題です。

グラフGは連結である(1つの連結成分をもつ)とする。 (1)木はGの点を網羅することを証明せよ (2)規約接続行列の中の1つの非零要素について展開すると、その小行列の中に非零要素が1つだけあることを証明せよ 例を使わない証明は苦手なので困ってます。解答の協力お願いします!

みんなの回答

  • alice_44
  • ベストアンサー率44% (2109/4759)
回答No.2

(2) これは、更に判りにくい。 行列を成分について展開って、何でしょう? 行列式を行か列について余因子展開することでしょうか? だとすれば、小行列ってのは、その成分の 余因子をなす小行列のことかなあ。 行余因子展開でも、列余因子展開でも、 同じ成分に対する「小行列」は共通だし。 …と、考えると、 質問の命題は、証明以前に、成立していません。 頂点 3 個以上の完全グラフを考えてみれば、 その接続行列は「既約」ですが、 その成分は全て 1 で、小行列も成分は全て 1 です。 非零成分は「ただひとつ」ではありません。 他の解釈も思いつかないのですが、 さて、題意は何なのでしょう?

  • alice_44
  • ベストアンサー率44% (2109/4759)
回答No.1

題意がいまいち不明瞭な質問です。 自作ですか? (1) G の部分グラフの中に、G の全ての頂点を含む 木が在る …で ok でしょうか。 1 頂点の木(辺なし)から始めて、 頂点を順に(G の辺で)木に接続すればよいです。 頂点と共に、辺は 1 本だけ木に加えます。 加えた頂点は、部分グラフの中では 辺を 1 本しか持ちませんから、 新たに閉路ができることはなく、 頂点が 1 個多い木ができます。 この操作が途中で続けられなくなったとすると、 そのときできている木と残りの頂点たちは 非連結ということになり、G の連結に反します。 よって、全ての頂点を含む木を作ることができる。