以前、他の方が、聞いてましたが、もっと具体的にケー二スバルグの橋の問題(一筆書き)を。
(1)
連結な平面グラフの各頂点が偶数個の辺に隣接している⇒
連結な平面グラフは、同一の始点・終点を持つように一筆書き可能である。
(2)
連結な平面グラフのちょうど2つの頂点が奇数個の辺に隣接し、残りのすべての頂点は、偶数個の辺に隣接している⇒連結な平面グラフは異なる始点・終点をもつように一筆書き可能
(1)、(2)をそれぞれ、数学的帰納法を用いて、証明したいんです。自分でやってみたんですが、うまくいかないんです。
力を貸して頂けないでしょうか?
どなたか教えていただけないでしょうか?
A 回答 (5件)
- 最新から表示
- 回答順に表示
No.5
- 回答日時:
既に解答は出ていますが、何故かまだ締め切られていないので追加説明です。
証明では、平面グラフの条件は何も使っていませんよね。
要するに、問題の条件に平面性は不要です。
逆に、この条件を削る事により、この問題が幾何学の
範疇でなく組合せ理論の問題である事がはっきりしますね。
あと、証明の本質は連結性の扱いなのでそこがきちんと
処理されていないと証明としては不十分ですね。
No.4
- 回答日時:
で言っていたことで、概ねあってると思っています。
命題1(n):枝数がn本であり、どの節点も偶節点である連結な平面グラフ⇒任意の1点を始点・終点に持つように一筆書き可能
命題2(n);枝数がn本であり、ちょうど2つの節点が奇節点であり、残りがすべて偶節点である連結な平面グラフ⇒奇節点の一方を始点、他方を終点に持つように一筆書き可能
と定義します。
1. 命題1(1)、命題2(1)とも真なのは自明。
2. n≦kのとき、命題1(n)、命題2(n)が真であると仮定。
このとき、命題1(k+1)、命題2(k+1)が真であることを示します。
(2-1. 命題1(k+1)が成立する証明)
「枝数がk+1本であり、どの節点も偶節点である連結な平面グラフ」を考え、その任意の枝を1本取り除くと、
「枝数がk本であり、ちょうど2つの節点が奇節点であり、残りがすべて偶節点である連結な平面グラフ」になります。
(連結性は、奇点定理から言えると思います。)
→命題2(k)が真であることから、命題1(k+1)が真であるといえます。
(2-2. 命題2(k+1)が成立する証明)
「枝数がk+1本であり、ちょうど2つの節点が奇節点であり、残りがすべて偶節点である連結な平面グラフG」を考え、2つあるうちのいずれかの奇節点vと接続する任意の枝eを取り除きます。
2-2-1. 枝eの他端v'が偶節点で、G-eが連結の場合
→vが偶節点、v'が奇節点となり、命題2(k)の仮定に収まるのでOK。
2-2-2. 枝eの他端v'が奇節点で、G-eが連結の場合
→vが偶節点、v'が偶節点となり、命題1(k)の仮定に収まるのでOK。
2-2-3. 枝eの他端v'が偶節点で、G-eが連結でない場合
→vが偶節点、v'が奇節点となり、グラフは2つにカットされます。ここで、Gのv以外の奇節点v''はv'と同じ側にあるようです。(奇点定理)
そうすれば、vを含む側は命題1よりvを始点、終点とする一筆書きができ、v''を含む側は命題2よりv'を始点、v''を終点とする一筆書きが可能であることから、証明できます。
2-2-4. 枝eの他端v'が奇節点で、G-eが連結でない場合
→vが偶節点、v'が偶節点となり、グラフは2つにカットされます。
命題1より、vを含む側はvを始点・終点とする一筆書き可能、v'を含む側はv'を始点・終点とする一筆書き可能であることから、証明できます。
3. ということで、証明終わり。
奇点定理については、こちら。http://plaza16.mbn.or.jp/~graph_puzzle/1no1.htm
・・・といいながら、結構適当な思いつきなので、詳細自信なしです。考え方は汲み取っていただければ・・・
No.3
- 回答日時:
#2です。
ちょっとタイプミス発見しました。>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のほうも((2) 連結な平面グラフのちょうど2つの頂点が奇数個の辺に隣接し、残りのすべての頂点は、偶数個の辺に隣接している⇒連結な平面グラフは異なる始点・終点をもつように一筆書き可能)掲載していただけないでしょうか?
おねがいします。
No.2
- 回答日時:
pirpiro1さん、こんにちは。
ケーニヒスブルグの橋の問題は有名ですね。
この問題を「解けない」と最初に解明したのは、
18世紀ドイツの数学者、オイラーでした。
さて、
(1)
連結な平面グラフの各頂点が偶数個の辺に隣接している⇒
連結な平面グラフは、同一の始点・終点を持つように一筆書き可能である。
この証明は、かなり難しそうですが、やってみます。
1)
まず、1点では一筆書きとは言わないので、最低2点が必要です。
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)
今、上の一筆書き可能な点k個の集合
Hk={a1,a2,・・・,ak}
と、さらにもう1点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(k個の、それぞれ偶数本の線が出ている点の集合)
は、一筆書き可能であったから、その中の点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個の点(それぞれ偶数本の線が出ている)は一筆書き可能であることが証明された。
のように証明できるのではないかなあ・・・と思います。
かなり、やっかいですね。
(2)は奇数点がありますので、ちょっと難しいですね。
しかし、奇数点はただ2つしかないと、一筆書きできませんから
それぞれの奇数点が、始点、終点となっていることは、予想がつくと思います。
このことから、証明を考えていけばいいと思います。
ご参考になればうれしいです。頑張ってください。
参考URL:http://www.wakayama-nct.ac.jp/gakka/ippan/fujita …
No.1
- 回答日時:
グラフ理論ですね。
検索エンジンで、検索を掛けてみますと、結構、ヒットします。・点と線の部屋
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
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 グラフ理論の数学の問題です。このタイプの問題は初めて見たので、どうやって解けばいいかわからないです。 1 2023/05/27 19:09
- 数学 『◯と●の帰納法』 2 2023/04/19 20:57
- 高校受験 高校受験まで2週間/未だに理社が平均点以下 理社の点数が未だに平均点以下から上がらず困っています… 1 2023/01/29 18:24
- 数学 【平方完成の問題です。 次の2次関数のグラフを書き、頂点と軸を求めよ。】 という問題ですが、やり方が 4 2022/07/28 00:36
- 数学 『数学的帰納法のトリセツ』 4 2022/06/06 07:34
- 会社・職場 先日面接でかなり脈ありだと思ってたんですが、1週間まるまる空いてから電話で連絡来て落とされました。面 17 2023/06/30 23:28
- 中学校 中1数学 比例のグラフの座標の読み取り 4 2023/03/28 12:26
- 国家公務員・地方公務員 昇任試験について 1 2022/12/04 12:57
- 数学 『4色問題⓵』 9 2022/10/24 06:54
- 転職 転職活動の面接について 3 2022/10/22 02:12
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
数学の問題です! 教えてくださ...
-
命題「PならばQ」でPが偽ならば...
-
高校数学、論理
-
a.bが定数で任意のε>0に対してa...
-
数学の背理法について質問です...
-
数学 x,yは実数とする。「xy+1=...
-
反対称的な2項関係の個数
-
この問題の逆 裏 対偶と真偽と...
-
背理法と対偶証明の違いについて
-
a>0、b>0⇔a+b>0、ab>0
-
強い仮定、弱い仮定、とは
-
命題を証明せよとはどういう意...
-
必要・十分条件
-
虚数単位i について「i =√-1<=>...
-
命題の証明の解き方を教えてく...
-
アキレスは亀を追い越せること...
-
命題論理に関する英単語
-
有理数+無理数=無理数 の証明
-
平方根の連分数展開の周期
-
ウェイソン選択課題について悩...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
数学での背理法について
-
命題「PならばQ」でPが偽ならば...
-
命題の真偽の問題で 命題〇〇に...
-
「逆もまた真なり」について
-
a>0、b>0⇔a+b>0、ab>0
-
強い仮定、弱い仮定、とは
-
n=3の倍数ならば、n=6の倍数で...
-
カントールの対角線論法につい...
-
対偶法による無理数の証明につ...
-
数学の論理学的な質問なんです...
-
数学の背理法について質問です...
-
証明問題です
-
数学で出てくる十分性と必要性...
-
命題を証明せよとはどういう意...
-
数学 x,yは実数とする。「xy+1=...
-
ドモルガンの法則、対偶、三段論法
-
有理数を文字置き→互いに素な整...
-
命題の証明で・・・
-
共分散の符号と相関係数の符号...
-
有界でないについて
おすすめ情報