一筆書き

えっと、小学校ではですね、漢字の書き順を習うわけですよね。
書き順っていうのは、まあ昔の習字の影響もあると思うんですけども、非常にリーズナブルな書き方なわけです。やっぱり書き順と違う書き方をすると、何かおかしいわけですね。あるいは単にそれは、昔トレーニングされてておかしいと思うのかもしれないですけど。
で、これ、「口」なわけです。ちなみに「口」という字をこういう風に書くと、やっぱりおかしいとぼくらは思うように教育されているわけですが、まあ、そう書いてもいいわけです。まあ、これは、「口」っていうのは例えばこういう風なグラフだと思ってもいいわけです。
ここに要するに点があって、その間を枝で結ばれているグラフだと思ってもいいですね。
で、もう既にさっき僕が「口」を縦長に書いたのから、もう分かっている人もいるかも知れないけど、まあこれ、ロ(ろ)でもいいんですが、今度はですね、

(カキカキ 「日」)

もちろん、「日」の方の書き順っていうのは、ぼくらこういう書き順で習っているわけですが、まあこれもグラフだと思ってもいいわけですね。ここを点だと思って、それで点の間を結んでできるものだと思ってもいいわけです。もちろん、この点とこの点が結ばれ、この点とこの点、この点とこの点というのが結ばれている。
で、だから書き順では、あれなんですが、例えばこれ(口)は、こう一筆書きできるわけですね。で、これ(日)も実は一筆書きできますよね?書き順には完全に反しますけど。
ちなみに、これやっちゃいけないんですけど、左上からスタートすると、ドツボるわけで、こう行って、こう行って…、まあここを通過してしまうと、ここで止まっちゃいますよね。いいですか、ペンダウンをして例えば「日」をここから始めて、こう行ってこう行ってこう行って…、ここで迷っちゃいますよね。

[今井先生2] えっと、どっちに行こうが、例えば、こっちに行っちゃうと、ペンを上げないといけないですよね。もちろんみんなが、ものすごく鉛筆の達人で同じ所をきれいに戻れるのだったらいいですけど、普通やっぱりブレますよね。それは反則。だから、それはやっちゃいけない、同じ所は2度通っちゃいけないということ、ちょうど1度だけ書く。
もちろん、これは別に僕がいけないわけじゃなくって、左上からスタートしたらとにかく失敗するわけですね。例えば、ここでさっきこう回ってしまって、ここでこう行ってこう行ってこう行ってしまってもやっぱり駄目ですよね。同じ所をちょうど1回しか通っちゃいけないんだったら、どっかで、これ必ず行き止まりになるわけです。
でも一方、この点なりこの点(まんなかの横棒の両端点)からスタートすると、ちゃんとまともにやればできるわけですね。
ということで、これ、一筆書きできましたよね。納得できた? いいよね、これ。
で、もう次に何を書くかはお分かりですよね。

で、「目」っていうのは、こういう書き順だって一応習ったわけですが、まあ、書き順っていうのはほんとは絶対的なものじゃないのかも知れないけど、今はとにかくこれをグラフだと思いましょう。
うーん、ようするに例えば、これをプロッターで書くと思えばいい。プロッターで書く時に別にプロッターが書き順通りに書かなければいけないなんてことはないですよね。 [一筆書き] で、ちなみにこれ、どうやっても駄目でしょ?要するに、一筆書きっていう意味で、「口」も「日」もOKだったんだけど、「目」は駄目ですよね。
で、これを今、だから、プロッターで書くということで、書き順はどうのこうのっていうのじゃなくって、とにかくペンをいっぺん下ろしたら、そのままずっと書きたい、と。ほんとはプロッターだったら機械だから、じっと、こういったらこう戻ってもいいんだけど、2度書きすると濃く(?)なるでしょ。
そういうことで、ちょうどいっぺんずつ枝を通って、まあこういう言い方の時は「辺」といった方がいいんですけれども、まあ、枝を通って、書くことができるかどうかを考えてみると、「口」の字のグラフはいいですし、「日」の字のグラフもいいんだけど、「目」の字のグラフは駄目ですよね。


で、オイラーグラフっていうのは、正確には「口」のタイプで、一番最初に下ろした所に最後また戻ってきて、しかも各枝を1回ずつ書いて戻ってくることができるグラフのことをオイラーグラフっていうわけです。
で、そういうものの特徴づけを今日やりたいわけです。で、今、これを話したのは何でかっていうと、これからもうちょっと退屈なグラフの定義をしますから、はっきりいうとそういうのをやっていると寝たくなってしまうわけですが、寝たくなったら、今のうちにですね、特徴づけを考えて下さい。
何かこう、グラフ的な意味で、これからパスっていうのを定義して、閉路っていうのを定義して、で、それは、一応基礎論では少しだけ話していると思うんですが、その後、基礎論でちゃんと定義をするのを忘れてパニックしてましたけど、次数っていうのを定義します。その後に、オイラーグラフっていう話と2部グラフっていう話しをします。
で、今のがとにかくヒントですから、「次数」っていうのをキーワードに、例えばこれ、ちゃんと特徴づけて欲しいわけです。
例えば、「口」の字タイプのやつ、「日」の字タイプ、「日」の字タイプはどの点からスタートしてもいいわけじゃなくって、ある特定の点からスタートすれば、成功するわけですよね。
ちょっとそういうのを考えて下さい。「目」の字だったら絶対に駄目だっていうのも。

で、まあ、実はもう答は分かっているとは思うんですが、一応、パスとか閉路とか次数とかの定義をして、この問題に挑戦することにします。


続グラフの定義

パスっていうのは、点と枝の列で、あ、今、無向グラフ(undirected graph)で 考えてみましょう。v1,e1,v2,e2,v3,…

(カキカキ)

ちなみに、答が分かったら、先に言っといてくれてもいいんだけど…

[パス] (カキカキ)

ek-1,vk。こういう点と枝の交互列(alternating sequence)ですね、実際には。
ただし、点で始まって点で終るわけです、両端は点。 でしかも、各eiっていうのは、これがパスなんですけれども、これはundirectedな意味でですけど、viとvi+1を結んでいる。これがパスなんですが、グラフで書くと、要するにv1っていうのがあって、v2っていうのがあって、ここに枝e1がある。で次にv3っていう所に行って、枝e2があって、…で、こっちも書きましょうか、viっていう点があって、枝eiがあって、vi+1があって、…枝ek-1があって、点vkがある。

で、えっと、すべての枝が異なるパスを、単純な(simple)パスといいます。ちなみに、またグラフの定義で並列枝(multiple edge)がないとかいろいろそういうことを言わなければならないんですけども、それはおいおいということにしましょう。

すべての点が異なるパスを、初等的な(elementary)パスというわけです。
だから単純なパスというのはですね、こういうのがあってもいいわけです。

[単純グラフ] (カキカキ)

えっと、このグラフのこのパス、ここから始まって、1,2,3,4,5,で、6番目の点は2番目の点と一致して、7番めの点にいくパス、っていうのは、これは単純なパスなんですけれども、elementaryではないわけですね。ここの点が一緒になっているから。
枝が一緒だったらば、つまり同じ枝を2度通ったら、必ず枝は絶対、両端点通るわけですから、初等的ならば必ず単純。

で、ほんとはdirectedなやつを定義した方がいいんだけど、閉路。これcycleと言われる時もあるし、あるいは、マトロイドとか従属とかの関係、あるいは電器回路との対照で出てくる時にはcircuitっていうんですけれども、閉路っていうのは両端点が、今の場合、v1とvkが等しい場合を言います。
で、単純、初等的っていうのは、同じように定義できます。
ただしもちろん、v1イコールvkという条件をつける。要するに、こういう、おなじ点を2回通ってしまったら、結局、1から7へ行くのはですね、こういうショートカットできるわけでしょ。
だからですね、elementaryなやつだけで考えておけば良いわけですね。

circuitの例は、例えば、

[閉路] (カキカキ)

まあいろいろあるんでしょうけれども、こう行ってこう行くなんて考えると、これは、v1とvkが等しいという意味ではいいんですけれども、途中でも等しいやつが出てくるから、これはelementaryではないわけですね。

で、グラフGはEulerianあるいはオイラーグラフ、っていうのの定義を、Gの各枝をちょうど1度ずつ通る閉路が存在する、だから、「口」型のグラフは、つまり「口」型の4点および4本の枝から成っているグラフは、オイラーグラフなんですね。
一方、「日」型のグラフは、オイラーグラフではないわけです、この意味では。
これ、閉路だって言っているからね。

で、そのためには、オイラーパスというものがあって、だから単に閉路の所をパスに変えただけですが、グラフの各枝をちょうど1度ずつ通るパスのことです。
「日」型の場合は、オイラーパスが存在するグラフなわけですね、オイラー閉路は存在しないけど。
で、目型は、オイラーパスもオイラー閉路も存在しないグラフになっている。

で、あと、次数ですね。点vの次数(degree)というのは、vに接続する枝の数というわけです。 [グラフの次数]

このグラフでどうなっているかっていうと、この点のdegreeは、接続している枝が2つだから、2,2,2,2。これは、3,2,2,3,2,2。これは、2,2,3,3,3,3,2,2。

で、定理で、
[定理]
ます、グラフGがEulerianであるための必要かつ十分な条件は、すべての点の次数が偶数であることなんですね。ちなみにこれはすぐ言いますけど、Eulerianならばすべての点の次数が偶数であることは自明なわけです。

2つ目は、グラフGがオイラーパスを持つ、しかもこれが閉路でない場合の必要かつ十分な条件は、2点奇数次の点があって、他は偶数次数になっている場合です。

この証明なんですが、((1)の"→")えっと、これ、あんまり、ほんとは講義でも論文書く時もやっちゃいけないことなんですが、でもやっぱりこれは自明ですよね。自明っていうのは、そこで間違えるのが一番多いパターンですから。
いいですか、オイラー閉路だったら、グラフの各枝をちょうど1度ずつ通る閉路があるわけですよね。その閉路に関して、スタートの点から始めて、その点に戻ってくるまで、たどった枝の順に各点の次数を足し算していく、だから、まず、出ていった所は1になるわけですね。次に、入ってきた所に1足されるわけです。 [グラフの次数2] このグラフでいうと、ここからスタートしたら、ここはまず1になるわけです。
で、ここに来た時にこれが1になるわけですね。で、次に、ここをぐるーっと回ることによって、ここは、こう、こう、接続されていますから、2になるわけです、ここも、入ってきますから1になって、出ていくから2になって、ここも、入って出ていきますから2になって、ここで必ず最初の所に戻ってきますから、ここの所も2になるわけです。
要するに、入って出て、入って出てで、しかも一番最初のとこだけは「出る」から始まるんですが、一番最後には、その点に「入る」で終るわけでしょ。
つまり、どの点も偶数次数なんです。

で、逆方向なんですけれども、正確には帰納法を使うんですが、ここでは構成的な証明をやります。一応証明になってますけど、より正確にはもちろん帰納法を使うべきです。
で、何やるかっていうと、点vを一つ選んでそこから行ける所まで行く、そんなアルゴリズムを考えます。例えばですね、

このグラフは、条件を満たしていますよね。このグラフの次数は、2,2,4,2,4,2,4なわけです。
例えば、最初にこの点(左上)を点vと選んだとします。で、今言いたいのは、すべての点が偶数、今の場合は2か4なわけですね、そのときに、オイラー閉路があることを言いたいわけです。
実際の証明としては、そのオイラー閉路を1つ求めることによって、証明を構成したいわけです。
そこで、とにかくなんでもいいから点を選んで、猪突猛進しなさいというわけです。で、します。こう行って、こう行って、こう行って、まあこう行くことは有り得ますよね(黄色)、猪突猛進ですから。

[証明1]
で、猪突猛進して、どんづまりに来るわけです。で、どうしましょうか。 [証明2]
ここで、一つ着目することがあって、この時まだたどってない枝があるわけですね。今、黄色の矢印は猪突猛進して使ってしまって、もう2度と通っちゃいけないから、忘れてしまいます。だから、元々の白い枝だけからなるグラフを考えます。
そうすると、今仮定している条件が再びその部分に関して成り立つというわけです。
つまり、この絵で言いたいことは、白の枝からなっているグラフっていうのは、「各点の次数が偶数」っていう条件を満たしているでしょ。
この点(真中左の点)がキーポイントで、この点は、さっきまで次数が4だったのが今度は2になっている。どうして2に減ったかっていうと、黄色の矢印が入って出ているからなんですね。
で、黄色の閉路で使われている点に関しては、入って出て、入って出てだから、偶数次数ずつ減っていくわけです。(どんづまりになるのは点vで)

っていうことは、今度は残りのグラフで、残りの枝がまだ接続している点を今度また適当に選んで、その点をvとして同じことを行ない、かつ、元の閉路とマージする、このマージっていうのはメタな意味で言っていますけど。
例えばここの点(真中の点)を選んだことにしましょう。ここで再び猪突猛進をするわけです。

今度はですね、例えばこう行ってこう行って、でまあ、ここへ戻ったらもういっぺんまた同じことをやるんですけど、もうそろそろ退屈してきたから、今度はちゃんと賢くですね、こっちへ行ったとしましょう(青色)。
また再びここで、点vに戻ってますから、残りの枝で構成されるグラフの各点は偶数次になっているわけです。
[証明3]
そうしたらですね、こうマージすればいいんですね。
[証明4]
だから、ほんとはこれ…、あ、ちゃんとした定義を書き忘れていますが、連結性をもちろん仮定しないといけないわけで、連結性は暗黙のうちに仮定してるんですけれども、連結だったらこういう点(vとして選んだ点)がありますから、黄色の方の閉路の道筋を変えて、青の閉路のスタートの方に入って、で、戻ってきた時に、黄色の閉路に戻ることによって、閉路が伸ばせますよね。
ということで、後はこれを繰り返していけばよい、と。最後の所は、構成的な方法でやっていると、言葉で書く証明としては、若干尻切れとんぼになっているけど、何回も言うように、帰納法で逆の方向からやっていくのがいい。
でも、みんながアルゴリズムでプログラムを組むのにはこれでいいんですね。

(2)の場合は、奇数次の点を最初にvとして選びます。それで、そこからスタートするとですね、そこから出た瞬間に今着目した点のdegreeは偶数になりますよね。
ということは、あとは入って出て入って出てってやっていくんだから、どんづまりになる点は、もう片方の奇数次の点なんです。
あ、だからちょっとだけ書いとくと、(2)の場合は、最初の点を奇数次の点のどちらかにする。どんづまりになるのは、他方の奇数次の点になるというのがキーポイントですね。
で、後は全く一緒。

で、ちなみに注意ですけど、summationの各点の次数というのは、だからこれ、全ての点に対して各点vの次数を足すと、これは2倍の枝数になりますから、これは偶数なんですね。
あの、バカみたいな簡単なcountingで、各点の次数を足し合わせるとそれは、要するに枝っていうのは両側の点から1、1、ってcountされてますから枝の2倍になります。
いいですか、各点の次数ってのはこう、点の方から見て、この枝つながってこの枝つながってこの枝つながってこの枝つながってって書くと得られるわけですよね。そうすると、各枝に関してこちらの点から見られて、こちらの点から見られて、2倍のEになります。
ですから、これ全部足すと偶数になりますから、奇数次の点が一つだけあるなんでことは無いわけですね。で、今度奇数次の点が4つある場合はだから、もうeuler閉路はできません。だからそれはもう…

であと、言いたいのはえと、有向の場合、で、このためだけにこれを残してたんですけど、有向のパスってのは今度はちゃんとdirectionまで付いて、このカッコもちゃんと順番が付いてこういう風に枝の向きの方向にたどっていくというのが有向のパス。
でこれは… 自分で考えましょう。有向がeuler閉路があるための条件というのはもちろん今度は次数を、in-degreeとout-degreeに分けるわけですね。
入次数とout-degree、あの、出次数、入ってくる枝の数、出ていく枝の数に着目すれば、この定理と同じ定理がほぼ成立するでしょ。ま、答えを、まあそれでほとんど言ったことになるでしょ。
入次数と出次数ってのに着目すれば、directedな場合も考えられるわけです。

で、今日は2部グラフの話はもうこれでしないのですが、ただ2部グラフの話をするとですね、2部グラフってなんかダンス…ダンパのメーキングの仕方だってなんか情報基礎論のI(現在の「情報数学」)で言ったよね。
言ったと思うんだけど、ま、その話はもう一回、くどいかも知んないけど来週の授業でしますけれども、で2部グラフとオイラーグラフ全然関係ないように思えるでしょ?
でも実はそれが、実は双対なグラフになってるわけですね。で双対っていう概念が結構この離散構造の中で非常に大切な概念になっているんですね。

なんか今日の話は別に非常に簡単な話で実はこれがグラグ理論の一番最初の、えーと、ちゃんとした年を覚えてないかも知れませんが、18世紀から19世紀に数学者のeulerが自分の周りの町に川があって島があって橋があって、どの橋もちょうど一度づつたどって元に戻って来ることができるかっていうことで、考えたのがこういうグラフ理論の一番起源ていうことになっていて、だからこれeulerって名前が付いてるんですけども、ま、非常に簡単な、わかってみれば簡単な話なわけですね。で、しかもこれ、linear timeでcomputerで解けるわけです。

で、実はそれがその2部グラフっていう、なんか男の子の集合がいて女の子の集合がいて、ダンスしてもいいよっていうような、なんか枝の関係を書いてってなんていう話が、実は双対な構造を持っているなんていうのが、例えばこういうグラフの、みんな一見こういうのバカみたいに思うかも知れないけれども、この離散構造のすごい所なわけですね。
で、実際これから段々段々双対の話をしていきます。


Prev Next

 

〔トップページへ〕 〔離散数学の仮想講義のindexページへ〕
<vu@is.s.u-tokyo.ac.jp>

Last updated on 6 May, 1999