岐阜工業(yè)高等専門學(xué)校

~第3回ゲームで學(xué)ぶグラフ理論グラフというと関數(shù)のグラフを思い浮かべるであろうが、數(shù)學(xué)にはもう１つのグラフがある。それは點(diǎn)と線からなる図形のことである。感謝閱讀ただし、線の長さ等は無視する。鉄道の路線図や電子回路などは一種のグラフと考えることもできる。地味ではあるが、広くつかわれているものである。精品文檔放心下載昔からよく知られているものに一筆書きというものがある。謝謝閱讀一筆書きとはグラフから筆をはなさずに、同じ線を２回通ることなく書くことである。謝謝閱讀オイラーにより、一筆書き可能なグラフは判明していて、次の條件を充たす連結(jié)したグラフが一筆書き可能となる。感謝閱讀點(diǎn)から出ている線の本數(shù)をその點(diǎn)の次數(shù)と云う事にする。謝謝閱讀奇數(shù)次の點(diǎn)が無いか、2個(gè)だけであるときに一筆書き可能となる。謝謝閱讀奇數(shù)次の點(diǎn)が無いときにはどこからはじめても一筆書き可能で、最後には始點(diǎn)にもどってきて終る。精品文檔放心下載奇數(shù)次の點(diǎn)が二個(gè)あるときには奇數(shù)次の點(diǎn)の一方から始まり、もう１つの奇數(shù)次の點(diǎn)で終る。謝謝閱讀たとえば、上のグラフではAからはじまりBで終るように一筆書きが出來る次の図形を一筆描きしてみよう。精品文檔放心下載~全ての次數(shù)が偶數(shù)の時(shí)にオイラーグラフと呼ぶこととする。感謝閱讀このオイラーグラフの上で、次のようなゲームを考えることが出來る。感謝閱讀オイラーへの挑戦ゲームオイラーグラフ上の一點(diǎn)を２人で始點(diǎn)に決める。２人で交互に線を繋げるように引き、最初にスタート地點(diǎn)まで辿り著いた方が勝となるゲームである。謝謝閱讀このゲームには必ず勝敗が著くことを証明しよう。もし、どこかの點(diǎn)で行き詰まってゲームが続けられなくなったとしよう。このとき、その點(diǎn)には最後に線がはいって來た狀態(tài)で、その點(diǎn)に繋がっている辺全てに線が引かれたことになる。ところが各頂點(diǎn)は偶數(shù)次であるから、はいって來た線と出ていく線が対になるはずである。つまり、はいって來た線には出ていく線が対応しているはずであり、始點(diǎn)以外の點(diǎn)では矛盾することになる。精品文檔放心下載よってゲームが途中で続行不可能になることはない。三角形を積みあげたグラフ(三角格子とよぶことにする)のときには面白いことが解る。感謝閱讀k段積んだ三角格子をk次の三角格子と呼ぶことにする。精品文檔放心下載三角格子で一番上の頂點(diǎn)から始めるオイラーへの挑戦ゲームをピラミッドパワーゲームと呼ぶこととする。精品文檔放心下載4次または5次の三角格子でピラミッドパワーゲームをしてみよう。謝謝閱讀じつは4次のピラミッドパワーは簡単な必勝法がある。感謝閱讀必勝法を捜しだしてみよう。図のようなグラフを考えてみよう。太い線からなるグラフから外にでないように線を引いていけば、後手必勝となる。感謝閱讀このような図形を必勝グラフということにしよう。必勝グラフは次の條件を充たしたグラフである。1.必勝グラフは必勝點(diǎn)と線と必勝點(diǎn)以外の點(diǎn)からなる。始點(diǎn)は必勝點(diǎn)である。謝謝閱讀2.必勝點(diǎn)から出ている線はすべて必勝グラフに含まれている。必勝グラフに含まれる線はすべて必勝點(diǎn)とその他の點(diǎn)をつないだものである。精品文檔放心下載この條件を充たしていると、後手は必勝點(diǎn)へ線を引いていけば必ず勝てる。このことを証明しよう。先手はまず必勝點(diǎn)である始點(diǎn)から決勝點(diǎn)でない點(diǎn)へ線を引く。條件より、後手は決勝點(diǎn)でない點(diǎn)から必勝點(diǎn)へ線を引く。必勝點(diǎn)から出ている線は全て必勝グラフに含まれているから、先手は必勝グラフから外に線を引くことはできない。また、後手は必ず必勝點(diǎn)以外の點(diǎn)から必勝點(diǎn)へ線を引くことができる。よって後手はいつかは必勝點(diǎn)である始點(diǎn)に線を引くことができる。謝謝閱讀4次以外でも必勝グラフを持っているものがある。次は３次の必勝グラフの１つである。感謝閱讀~必勝グラフは１つだけではなく、複數(shù)個(gè)存在することもある。謝謝閱讀6次の必勝グラフは2種類ある。それを描いてみよう。感謝閱讀実は2n3次以外のピラミッドパワーゲームでは必勝グラフがあり、従って後手必勝である。謝謝閱讀一方、先手必勝であるのは1次と5次のときのみが虱潰しに調(diào)べて判明している。感謝閱讀2n3次は先手必勝であろうと予想されているが未解決である。感謝閱讀123の三角形ゲーム123の三角形については根上生也著グラフ理論3段階(遊星社)を元にしています。精品文檔放心下載三角形の頂點(diǎn)に1、2、3の番號をひとつづつ付ける。精品文檔放心下載また、三角形の內(nèi)部にいくつかの點(diǎn)を打って、三角形に分割しておく。感謝閱讀２人が交互に三角形の內(nèi)部の點(diǎn)に1か2か3の番號を付ける。精品文檔放心下載その結(jié)果、外側(cè)の三角形以外に頂點(diǎn)に1、2、3の番號が附いている三角形ができた人の敗けである。この三謝謝閱讀~角形を123の三角形と言うことにしよう。このゲームは必ず勝敗が著く。つまり123の三角形は必ずできる。どうしてなのか考えてみよう。感謝閱讀グラフには雙対グラフというものを考えると便利なことがある。精品文檔放心下載これはグラフの線でかこまれた部分に點(diǎn)をとり、線で接しているもの同士を線で結(jié)んだものである。精品文檔放心下載上の図のようになる。この雙対グラフの一部分を使って、123の三角形ができることを照明しよう。感謝閱讀各點(diǎn)に123の數(shù)字が書かれていたとする。雙対グラフの線のうち、「元のグラフの線が異った數(shù)字を繋いでいる線」と交わったものだけを殘して消してしまったものを考える。各三角形と交わる線は次の様になる。謝謝閱讀~全て同じ數(shù)字二つが同じで 三つとも違うとき１つ違うとき小さな１つの三角形からでてい線の本數(shù)は上の図を見てわかるように0本、２本、3本の三種類のみです。感謝閱讀背理法で照明します。もし123の三角形がなければ、各點(diǎn)の次數(shù)は0か2です。精品文檔放心下載三角形の外に次數(shù)が3の點(diǎn)がありますから、各點(diǎn)での次數(shù)の和は奇數(shù)となります。感謝閱讀ところが、各點(diǎn)の次數(shù)の和は線の個(gè)數(shù)を二重に數(shù)えていることになりますから、線の個(gè)數(shù)の2倍つまり偶數(shù)になるはずなので矛盾しています。謝謝閱讀よって123の三角形はあることが証明できました。感謝閱讀課題１ピラミッドパワーゲームで7次と11次のときの必勝グラフを求めよ感謝閱讀２四角形の頂點(diǎn)に1234の數(shù)字を書き、內(nèi)部を三角形に分解する。精品文檔放心下載內(nèi)部の三角形の頂點(diǎn)に1234のどれかの數(shù)字を描いていくと、必ず各