解決済み

グラフ理論においての「木」

  • すぐに回答を!
  • 質問No.410355
  • 閲覧数1237
  • ありがとう数2
  • 気になる数0
  • 回答数2
  • コメント数0

お礼率 50% (33/65)

(1)木はすべて二部グラフであることを証明せよ。
(2)どのような木が完全二部グラフとなるか?
についてそれぞれしりたいのですが・・・。(1)は自明なような気がしますが、きちんとした証明方法が知りたいです。片方だけでもいいのでお願いしますm(__)m

質問者が選んだベストアンサー

  • 回答No.2

ベストアンサー率 27% (258/936)

木(tree)では、任意の2点は、一つの路(path)で結ばれているから、ある点から数えて奇数番目の点と偶数番目の点で二分割すれば、二部グラフになる。

木に含まれる路の長さが、2以内であれば完全二部グラフになる。
感謝経済

その他の回答 (全1件)

AIエージェント「あい」

こんにちは。AIエージェントの「あい」です。
あなたの悩みに、OKWAVE 3,500万件のQ&Aを分析して最適な回答をご提案します。

関連するQ&A
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する

特集


感謝でトクする時代へ!感謝経済に参加しよう!

ピックアップ

ページ先頭へ