- ベストアンサー
マッチングに関する問題 (グラフ理論)
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
たぶん, その証明はどちらも M1 と M2 の対称差を考えることに帰着できると思います. で, 「2つの完全マッチングの対称差をとると各頂点の次数は 0 か 2」ということに気付けば簡単です. 次数 2 の頂点のみからなる部分グラフの連結成分がどうなるか, 考えてみてください. もしくは, 帰納法を使ってもいいかな. 「全ての木は完全マッチングを高々 1つしか持たない」という命題と「全ての森は～」という命題は等価です. あえて後者を証明することにします. 木には必ず葉があり, 葉は次数が 1 なので完全マッチングでは葉に接続する辺を必ず選ぶ必要があります. これで 2個の頂点と それに接続する辺が消えて, あとにより小さな森が残ります.
その他の回答 (1)
- Tacosan
- ベストアンサー率23% (3656/15482)
とりあえず, 「うまい」かどうかは別にしてその直感を書いてみてください. 不安に感じる点があればそこも書いてくれると better.
補足
返信ありがとうございます。 証明ですが、 木Tが異なる2つの完全マッチングをもつとする。 1つの完全マッチングをM1とし、それと異なるマッチングM2を考える。 M1に含まれない、かつM2に含まれる枝eがある。 そのeから端点に向かって非マッチング枝とマッチング枝を交互に取っ ていくと、端点で非飽和になる点にがあり、その点を飽和点にするには 閉路ができて、木であることに反する。 という感じです。 交互に取っていくと、おそらく端点で非飽和になる点ができると思うん ですが、どうしてそうなるかわかりません。 また、Tの枝は交互にM1の枝、M2の枝となりそうなので、M1とM2の対称差を考えたんですが、うまく使えません。 「たぶん」とか「おそらく」ですみません。お願いします。
関連するQ&A
- グラフ理論の問題(木について)
次のことを証明せよ。 1.木の全ての最長路はその中心点を通過する。 2.木の最長路が1つ識別されると、木の中心が示される。 という問題です。 最長路の長さが偶数の場合と基数の場合に場合分けをしたとき 偶数の場合は両端の点から同じ距離にある点が中心点であり、 基数の場合は両端の点から同じ距離にあるような、隣接した2点が中心点になることを使うようなのですが、どのように使うのでしょうか。 また、なぜこうなるのでしょうか。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- グラフ理論においての「木」
（１）木はすべて二部グラフであることを証明せよ。 （２）どのような木が完全二部グラフとなるか？ についてそれぞれしりたいのですが・・・。（１）は自明なような気がしますが、きちんとした証明方法が知りたいです。片方だけでもいいのでお願いしますm(__)m
- ベストアンサー
- 数学・算数
- グラフ理論について
全然分からなくて困っています。誰か助けてください。 １．グラフKn,Kn￣、Km,n,Cn,Tn〔Ｔnは位数nの木〕の染色数をそれぞれ求めよ。 ２．グラフKn,Km,n,Cn,Tnの辺染色数をそれぞれ求めよ。 ３．オイラーの多面体公式を証明せよ。 ４．以下の問題を証明せよ。 〔１〕頂点数が３以上の平面グラフGが極大平面グラフであるための必要十分条件は、Gのすべての領域が三角形であることである。 〔２〕４頂点以上の極大平面グラフGにおいて、 △〔G〕 不等式 Σ 〔6-i〕Ni =12 〔Ni = {次数がiの頂点の数}〕が成立する。 〔３〕４頂点以上の平面的グラフには、次数５以下の頂点が存在する。 〔４〕K5,K3,3は非平面的グラフである。 〔５〕平面的グラフは５-彩色可能である。
- 締切済み
- 数学・算数
- グラフ理論の問題についての質問です
大学のグラフ理論の問題でわからないものがあったので質問させていただきます。 ****************** 問題： グラフGが位数|V(G)|=nでk個の連結成分を持つグラフの時、辺数|E(G)|が n-k≦|E(G)|≦1/2(n-k+1)(n-k) をみたすことを示しなさい。 ******************* 以上の問題を帰納法をつかって証明しようとしたのですが、詰まってしまいました。 よろしければこの問題の証明方法を教えてください。 よろしくお願いします。
- 締切済み
- 数学・算数
- グラフ理論の彩色問題
G を3 角形がない単純平面的グラフとする．このとき，G が4-彩色可能であることを示せ． この問題の証明が出来なくて困ってます。 誰かわかりやすく解説お願いします。
- 締切済み
- 数学・算数
- 【グラフ理論】証明問題が分かりません。【難問】
テストに向けてグラフ理論の勉強をしているのですが・・・ 下記の証明問題で行き詰まってしまいました。 『uv ∉ E(G) → uw ∉ E(G)というグラフは完全K部グラフしか存在しない事を証明せよ。』 当方、証明問題に滅法弱く、どう解けば良いのか方針すら分かりません。 方針や証明の過程など詳しくご教授して頂ければ幸いです。 何卒宜しくお願い致します。
- 締切済み
- 数学・算数
- グラフ理論の問題について
Gをn個の頂点とM本の辺を含む、以下の条件を満たすグラフとします。 このグラフの全ての辺をk通りの異なる色に彩色したとき、そのうち任意のm個の異なる色が選ばれたとしても残りのk-m色のみで塗られた辺によって出来た部分グラフが連結であるような彩色の仕方が存在する。 ここでk,n,mをパラメーターとした時、「最小の」Mの値を求めたいのですが、m=1の時の解しか得られませんでした。どのようなグラフ理論的なテクニックを用いてこの問題を解くべきなのでしょうか？この種の問題は一般的にグラフ彩色の問題として分類されるのでしょうか？なにか一般解を得るためのヒントや手助けとなりそうなアイディアや論文などありましたらお教え願いたいです。
- ベストアンサー
- 数学・算数
- エクセルでマッチングが上手く行きません
エクセル2007を使っています。 マッチングをしても「0」としか表示されません。 何が原因でしょうか？ マッチングに使うマスターは、同じブック内にあります。 他の作業でも使っているマッチング用の式を修正して使用しています。 マッチングは、全て数値です。
- ベストアンサー
- その他(業務ソフトウェア)
補足
理解できました。ありがとうございます。