Marriage Theorem 新居

jun0 2010/08/08 06:02 はじめまして。ちょっと古い記事に失礼します。白の頂点から作れる事と黒の頂点から作れる事が排反であるというのは一応成り立ちます。私がやった限りでは死ぬほど長い、とても「簡単」とは言えない証明になってしまいましたが、興味がおありでしたら私のブログに書きましたのでどうぞ。

楓流 2011/03/23 20:00 はじめまして。かなり古い記事ですが失礼します。
興味深い内容でしたので、自分なりに別回答を考えてみました。お手すきの際、楽しんでいただけると幸いです。

nは1以上の整数とする。
この棒状グラフに限り、当該操作を下記のように簡略化することができる。
f(n-1)：(n-1)個目の右に白点を追加し、隣接点の色を反転させる操作。
　　　　ｆ(0)は、左端に白点を追加し、隣接点の色を反転させる操作。
この操作の逆関数として、下記も成立する。
F(n-1)：(n-1)個目の右の白点を削除し、隣接点の色を反転させる操作。
　　　　F(0)は、左端の白点を削除し、隣接点の色を反転させる操作。
f(n-1)とF(n-1)が逆関数であることは、2個の点の色パターン(○○、○●、●○、●●)に対

して、[左端に白点追加の場合]f(0)⇔F(0)、[中間に白点を追加した場合]f(1)⇔F(1)、[右端

に白点を追加した場合]f(2)⇔F(2)の操作パターンで確認できる(総計12パターン)。

n個の白点のグラフをG(n)とする。
グラフG(n)に操作f(n)→f(n)→f(n+2)を順に実施すると、G(n+3)になる。
これを下記のように示す。
　f(n+2)f(n)f(n)[G(n)]=G(n+3)
一方、逆関数により下記も成立する。
　F(n)F(n)F(n+2)[G(n+3)]=G(n)

これにより、G(n)は下記３グループに分類される。
そして、同じグループに所属するグラフは、操作f(n)とF(n)によって全て変換可能である。
iは0以上の整数とする。
　グループ1．n=1+3i　　：　G(1)、G(4)、G(7)等
　グループ2．n=2+3i　　：　G(2)、G(5)、G(8)等
　グループ3．n=3+3i　　：　G(3)、G(6)、G(9)等
また、グループ3について、
　F(1)F(0)[G(3)]　または　F(0)F(2)[G(3)]　により、G(1)に帰着させることができる。
グループ2については、
　F(0)[G(2)]、F(1)[G(2)]の双方を実施してもG(1)にならない。

以上のことにより、G(n)が可能グラフとなるためには、
　n=1+3i、3+3i　(iは0以上の整数)
が条件である。

laika00 2011/04/17 11:07 古い記事ですが、自分なりの解答を書かせていただきます
文字数の関係上、いくつかの証明については明らかとします

操作１と２を組み合わせれば白玉を３つ増やせるので、「３で割って０か１」が可能であることの証明は省略します
ある操作パターンがあったとき、操作の順番を入れ替えても、各操作が可能であれば最終形は同じになる
最終形が直線なので、線分を消すことは出来ない つまり、各状態において線分はダブらない
よって、はじめに操作１を全て行った後、操作２のみを行っても、最終形は変わらない
操作１が終わったとき、真ん中が黒で、両端のいずれか、もしくは両端＋１コが白
白地に黒の状態において操作２は、黒２つを消すか作る、あるいは黒を移動させる
つまり、ある閉じた系の黒集団を白集団に変えるためには、黒は偶数個でなくてはならない
偶数個の黒集団を白集団に変えるとき、黒集団を２つづつで分けたときの、それぞれの２つ玉の間には必ず操作２が来る
黒奇数の場合条件を満たさないので、黒集団の２つ玉づつに操作を加えると、白が３の倍数＋０か１になる
白黒の状態のとき、黒の行き来をすると、増える玉数は３の倍数
また、白地から黒２個をつくったとき、その間に１コ玉が入ることから、白地において、黒を作って消す操作を行っても、３の倍数分しか玉数は増えない

以上より証明された

M.T 2011/04/22 21:27 以下の方法であれば受験生でも比較的楽に解くことが出来るのではないでしょうか。

〜〜〜〜〜〜〜
点から出ている辺の数が減らないことから「直線グラフだけ考えれば良いことは明らか。

直線のグラフＧに対して、次の整数の非順序対を考え、特性数と呼ぶ。

A(G) = 端から黒丸を二つずつ組にしていき、組の中の距離の和
・1.G の黒丸の数が偶数の場合
{A(G), A(G の両端に黒丸を付け加えたもの)}
・2.G の黒丸の数が奇数の場合
{A(G の右端に黒丸を付け加えたもの), A(G の左端に黒丸を付け加えたもの)}

たとえば、
白丸が n 個つづいている場合、
{0, n+1} が特性数である。

特に白丸が 1つならば、{0,2}

ところで、与えられた操作は、すべて特性数の差を3で割った余りを保存する。
よって、特性数が{0,3n}とあらわされる白丸が3n-1つながっているグラフは
白丸が1つのグラフから上述の操作では生成できない。


〜〜〜〜〜〜〜

保存する部分の補足


〜〜〜〜〜〜〜

白丸をA、黒丸をBとして、端を意味する[　]もつける。また、丸同士の連結を−と〜で表す。ここで丸と端も連結すると考えて、連結は一番左が−で、以後はBが出るごとに交互に変わるとする。例えば[−A−],[−B〜],[−A−B〜A〜B−A−]など

変換ルールは（連結を無視して） A]→BA], B]→AA], [A→[AB, [B→[AA, AA→BAB, AB→BAA, BA→AAB, BB→AAA となる。このとき、−の数と〜の数との差を3で割った余りは一定。例えば−A−]→−B〜A〜]では−が1減、〜が2増。

−と〜は補数の関係にある。枠もつけて、さらに点ではなくその連結を考える。

もっと素直に 2011/04/28 18:38 G(n) → 操作1,1,2 → G(n+3)
ができるんですから
G(n)が可能グラフ ⇒ G(n+3)が可能グラフ … (1)
ですよね。操作を逆に追うと
G(n+3)が可能グラフ ⇒ G(n)が可能グラフ
もすぐ気づきます。さらに対偶をとって
G(n)が可能グラフでない ⇒ G(n+3)が可能グラフでない … (2)
ことも分かります。
G(1)とG(3)が可能でG(2)は不可能。
あとは(1)と(2)より答えが出ます。

momordica 2012/03/03 01:45 某Q＆Aコミュニティから流れてきました。
相当古い記事のようですが、興味があったので自分なりに考えてみました。
私はグラフ理論などというものは名前しか知らないので、こんなのでいいのかさっぱり
なのですが…

とりあえず、「操作１」を行うのは両端にある頂点のみとして、その結果できる
枝別れのない棒状グラフだけ考えることにします。
また、少々ルールを変えます。

・頂点だけに色をつけるのはつまらないので、辺も白か黒で塗ることにします。
・問題では最初は白頂点１つだけからですが、それでは寂しいので、頂点の両側に
　白辺を１つずつつけた状態から始めることにします　[−○−]
・その後、以下のような操作を繰り返します。

　＊任意の辺を１つ外して、その部分を、間に一つの頂点を挟んだ２つの辺に付け替える。
　　　ただし、２つの新しい辺の色は付け替える前の辺と逆(白→黒、黒→白)にする。
　　　　[ …−… ] → [ …＝○＝… ]　　（−は白辺、＝は黒辺）

　＊その操作の結果、頂点の両側の辺が同じ色になった頂点は白に、両側が違う色に
　　　なった頂点は黒に塗り直す
　　　　[ …−○−… ]　 [ …−●＝… ]

以上のようにすると、各頂点の変化は、一番端の辺を入れ替える操作では問題中の
「操作１」に、中間の辺を入れ替える操作では「操作２」と全く同じになります。
これにより、２種類の操作が「任意の辺１本を反対の色の辺２本と入れ替える」という
１種類の操作として扱えることになります。
　＜例＞
　　[−○−]
　　　→(操作１：右側の辺を入れ替え)→　[−●＝○＝]
　　　→(操作２：真ん中の辺を入れ替え）→　[−○−○−●＝]
　　　→(操作１：左端の辺を入れ替え)→　[＝○＝●−○−●＝]

ここで、最初の状態から
　「白辺を黒辺２本に入れ替える」という操作をs回、
　「黒辺を白辺２本に入れ替える」という操作をt回繰り返したとすると、
白辺、黒辺の数はそれぞれ (2-s+2t)個、(2s-t)個 となります。
また頂点の数nは操作１回ごとに１つずつ増えるので、(s+t+1)個になっています。

その時、もしすべての頂点が白になったとすると、すべての頂点についてその両側の
辺が同じ色である、すなわち、すべての辺が同じ色ということになります。

もしすべての辺が白ならば、黒の辺は一つもないということなので、
　2s-t=0
　∴　s=2t
　∴　n=s+t+1
　　　　 =s+2s+1
　　　　 =3s+1
したがって、頂点の数nは、３で割ると１余る数になります。

同様に、すべての辺が黒ならば、白の辺は一つもないということなので、
　2-s+2t=0
　∴　s=2t+2
　∴　n=s+t+1
　　　　 =(2t+2)+t+1
　　　　 =3(t+1)
したがって、頂点の数nは、３で割り切れる数になります。

以上より、棒状グラフで頂点がすべて白になるための必要条件は、頂点の数nを
３で割った余りが１または０であることだということが分かります。
また、それらが十分条件であることは容易に示されるので、これらが必要十分条件
であることが分かります。

スパム対策のためのダミーです。もし見えても何も入力しないでください

コメントを書くには、なぞなぞ認証に回答する必要があります。