ケー二スバルグの橋の問題（一筆書き）

質問

以前、他の方が、聞いてましたが、もっと具体的にケー二スバルグの橋の問題（一筆書き）を。
(1)
連結な平面グラフの各頂点が偶数個の辺に隣接している⇒
連結な平面グラフは、同一の始点・終点を持つように一筆書き可能である。
(2)
連結な平面グラフのちょうど２つの頂点が奇数個の辺に隣接し、残りのすべての頂点は、偶数個の辺に隣接している⇒連結な平面グラフは異なる始点・終点をもつように一筆書き可能

(1)、(2)をそれぞれ、数学的帰納法を用いて、証明したいんです。自分でやってみたんですが、うまくいかないんです。

力を貸して頂けないでしょうか？

どなたか教えていただけないでしょうか？

回答No.5

graphaffine

既に解答は出ていますが、何故かまだ締め切られていないので追加説明です。

証明では、平面グラフの条件は何も使っていませんよね。
要するに、問題の条件に平面性は不要です。
逆に、この条件を削る事により、この問題が幾何学の
範疇でなく組合せ理論の問題である事がはっきりしますね。
あと、証明の本質は連結性の扱いなのでそこがきちんと
処理されていないと証明としては不十分ですね。

回答No.4

kony0

http://oshiete1.goo.ne.jp/kotaeru.php3?q=525286
で言っていたことで、概ねあってると思っています。

命題１（ｎ）：枝数がｎ本であり、どの節点も偶節点である連結な平面グラフ⇒任意の１点を始点・終点に持つように一筆書き可能
命題２（ｎ）；枝数がｎ本であり、ちょうど２つの節点が奇節点であり、残りがすべて偶節点である連結な平面グラフ⇒奇節点の一方を始点、他方を終点に持つように一筆書き可能

と定義します。

1. 命題１（１）、命題２（１）とも真なのは自明。

2. ｎ≦ｋのとき、命題１（ｎ）、命題２（ｎ）が真であると仮定。
このとき、命題１（ｋ＋１）、命題２（ｋ＋１）が真であることを示します。

（2-1. 命題１（ｋ＋１）が成立する証明）
「枝数がｋ＋１本であり、どの節点も偶節点である連結な平面グラフ」を考え、その任意の枝を１本取り除くと、
「枝数がｋ本であり、ちょうど２つの節点が奇節点であり、残りがすべて偶節点である連結な平面グラフ」になります。
（連結性は、奇点定理から言えると思います。）
→命題２（ｋ）が真であることから、命題１（ｋ＋１）が真であるといえます。

（2-2. 命題２（ｋ＋１）が成立する証明）
「枝数がｋ＋１本であり、ちょうど２つの節点が奇節点であり、残りがすべて偶節点である連結な平面グラフG」を考え、２つあるうちのいずれかの奇節点vと接続する任意の枝eを取り除きます。
2-2-1. 枝eの他端v'が偶節点で、G-eが連結の場合
→vが偶節点、v'が奇節点となり、命題２（ｋ）の仮定に収まるのでOK。
2-2-2. 枝eの他端v'が奇節点で、G-eが連結の場合
→vが偶節点、v'が偶節点となり、命題１（ｋ）の仮定に収まるのでOK。
2-2-3. 枝eの他端v'が偶節点で、G-eが連結でない場合
→vが偶節点、v'が奇節点となり、グラフは２つにカットされます。ここで、Gのv以外の奇節点v''はv'と同じ側にあるようです。（奇点定理）
そうすれば、vを含む側は命題１よりvを始点、終点とする一筆書きができ、v''を含む側は命題２よりv'を始点、v''を終点とする一筆書きが可能であることから、証明できます。
2-2-4. 枝eの他端v'が奇節点で、G-eが連結でない場合
→vが偶節点、v'が偶節点となり、グラフは２つにカットされます。
命題１より、vを含む側はvを始点・終点とする一筆書き可能、v'を含む側はv'を始点・終点とする一筆書き可能であることから、証明できます。

3. ということで、証明終わり。

奇点定理については、こちら。http://plaza16.mbn.or.jp/~graph_puzzle/1no1.htm

・・・といいながら、結構適当な思いつきなので、詳細自信なしです。考え方は汲み取っていただければ・・・

回答No.3

fushigichan

＃２です。ちょっとタイプミス発見しました。

＞ak+1→ai+1→ak+1→ai+2→ak+1→・・・
と繰り返していくと、（ai+1とak+1の間はti+2往復、
ai+2とak+1の間は、ti+2往復する、という風に考えるとよい）

aiとak+1との間は、ti+1往復でした。

ak+1から、線が出ている頂点まで、それぞれ往復して
最終的には、aiへ戻るという経路が考えられますよね。
ak+1から、ai+1,ai+2,・・・ai+jへは
偶数本の線が出ているので、順番は問いません。
ai→ak+1のあとは、
ak+1→ai+j→ak+1→・・・
のように往復していってもいいですね。

補足

すいません。２のほうも（(2) 連結な平面グラフのちょうど２つの頂点が奇数個の辺に隣接し、残りのすべての頂点は、偶数個の辺に隣接している⇒連結な平面グラフは異なる始点・終点をもつように一筆書き可能）掲載していただけないでしょうか？
おねがいします。

回答No.2

fushigichan

pirpiro1さん、こんにちは。
ケーニヒスブルグの橋の問題は有名ですね。
この問題を「解けない」と最初に解明したのは、
１８世紀ドイツの数学者、オイラーでした。

さて、
(1)
連結な平面グラフの各頂点が偶数個の辺に隣接している⇒
連結な平面グラフは、同一の始点・終点を持つように一筆書き可能である。

この証明は、かなり難しそうですが、やってみます。

1)
まず、１点では一筆書きとは言わないので、最低２点が必要です。
n=2のとき、頂点a1,a2があるとする。
それぞれの頂点から、偶数本の線が出ているとする。
a1から出ている線の数をp(a1)
a2から出ている線の数をp(a2)とすると、
p(a1)=p(a2)=2m（偶数）であるはずである。
このとき、a1を始点とすると、a1→a2→a1というのを
m回繰り返すと、始点a1に戻り、一筆書き完了。

2)
異なる頂点
a1,a2,a3,・・・ak
があって、それぞれ偶数本の線
p(a1),p(a2),・・・,p(ak)本の線が出ているとする。
さらに、{a1,a2,a3,・・・,ak}=Hkとすると、
図形Hkは一筆書き可能だと仮定する。

3)
今、上の一筆書き可能な点ｋ個の集合
Hk={a1,a2,・・・,ak}
と、さらにもう１点ak+1をとり、
ak+1からは、それぞれの点に対して、偶数本の線が引かれているものとする。
このとき、
Hk+1={a1,a2,・・・,ak,ak+1}
が一筆書き可能であることを言えればよい。

さて、今、ak+1から、線が出ている先の頂点を
ai,ai+1,・・・ai+j
とおくことができる。
仮定より、
p(ak+1)=2m[k+1]←ある偶数　であって、
p(ai)+p(ai+1)+・・・+p(ai+j)=p(ak+1)=2m[k+1]
となっているはずである。
aiからak+1に出ている線の本数を2ti本とする。
ai+1からak+1に出ている線の本数を2ti+1とする。
・・・
ai+jからak+1に出ている線の本数を2ti+j本とすると、
2ti+2ti+1+・・+2ti+j=2m[k+1]

さて、図形Hk（ｋ個の、それぞれ偶数本の線が出ている点の集合）
は、一筆書き可能であったから、その中の点aiを始点として、一筆書き可能である。
このとき、1)2)より、終点もまたaiとなっている。

さらに、そこから
ai→ak+1と行って、そこからは、
ak+1→ai+1→ak+1→ai+2→ak+1→・・・
と繰り返していくと、（ai+1とak+1の間はti+2往復、
ai+2とak+1の間は、ti+2往復する、という風に考えるとよい）
最終的に
→ak+1→ai
となって、aiが終点で終わることは、想像できる。

よって、n=k+1のときも、
集合Hk+1={a1,a2,・・・ak,ak+1}
は一筆書き可能である。

1)2)3)より、全てのn≧2の自然数nについて、
n個の点（それぞれ偶数本の線が出ている）は一筆書き可能であることが証明された。

のように証明できるのではないかなあ・・・と思います。
かなり、やっかいですね。
（２）は奇数点がありますので、ちょっと難しいですね。
しかし、奇数点はただ２つしかないと、一筆書きできませんから
それぞれの奇数点が、始点、終点となっていることは、予想がつくと思います。
このことから、証明を考えていけばいいと思います。
ご参考になればうれしいです。頑張ってください。

参考URL：

http://www.wakayama-nct.ac.jp/gakka/ippan/fujita/kika1page.htm

回答No.1

Mell-Lily

グラフ理論ですね。検索エンジンで、検索を掛けてみますと、結構、ヒットします。

・点と線の部屋
http://plaza16.mbn.or.jp/~graph_puzzle/index.html

・グラフ理論の探求　一部第五章
http://plaza16.mbn.or.jp/~graph_puzzle/1no5.htm

参考URL：

http://plaza16.mbn.or.jp/~graph_puzzle/1no5.htm