最大1万円超分の電子書籍プレゼント♪

すべての辺には四本の辺が集まっている。
連結なグラフから辺を一本取り除いても連結であることを証明しなさい。

教えてください。

A 回答 (5件)

一辺取り除いて不連結になったグラフの両連結成分を考えると、


取り除いた辺が付いていた頂点だけが3辺点、他は4辺点のまま
となっている。で、そんなグラフが可能かというと、
連結グラフの各頂点の辺数の和はグラフの辺数×2と等しいから
偶数でなくてはならない。つまり、1個だけ3辺点は不可能。
よって、背理法により...
    • good
    • 1

頂点が無限個なら反例はすぐできる(数直線上の整数をノードとして、隣接点で2本、自分自身のループで2本なら条件を満たすが、0-1を切れば連結でなくなる)。



有限グラフなら、要するに一筆書きの応用。
    • good
    • 0

これたぶん真っ直ぐいくとどうにもならないんじゃないかな.



背理法, つまり「もとは連結なんだけど辺を 1本取り除いたら連結でなくなったよ」という仮定のもとで矛盾を導くんだろうねぇ.
    • good
    • 1

なにをどう考えて, どこまでいってどこでなにに困っている?

    • good
    • 0
この回答へのお礼

グラフのイメージはできてるが、どうやって証明したらいいのか全くわかりません。

お礼日時:2021/11/12 02:04

「すべての辺には四本の辺が集まっている。

」とはどういうことでしょうか.
    • good
    • 0
この回答へのお礼

すべての頂点の間違いです。すみません。

お礼日時:2021/11/12 00:30

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています


このQ&Aを見た人がよく見るQ&A

人気Q&Aランキング