彼は二週間にわたって毎日夜遅くまで作業を続け、満足いく設計を完成させた。設計が完成すると、彼はあるコネクターを動かせばフィードスルーが削減され、基板の信頼性を向上できることに気が付いた。しかしコネクターを動かすには、設計を最初からやり直す必要があった。二回目の設計は二十時間で完成した。その後、彼は別のフィードスルーも除去できることに気が付き、設計をもう一度最初からやり直した。「最終的に完成した設計は素晴らしく、工学的にも美しいと多くのコンピューターエンジニアの間で認識された。Woz は後に "これはエンジニアでありながら PC 基板のレイアウトを考えられる人物だけが実現できることだ。芸術的なレイアウトで、フィードスルーは事実上存在しない。" と語っている。」
13.2 平面グラフの定義
目次
前節ではグラフの「平面描画」の概念を定義せずに使った。しかし平面グラフに関する事実を証明するには、正確な定義が必要になる。
定義 13.2.1
グラフの描画 (drawing) とは、グラフの各頂点を平面上の異なる点に割り当て、同時にグラフの各辺をその端点に対応する点を結ぶ滑らかな平面曲線に割り当てる規則を言う。グラフの平面描画 (planar drawing) とは任意の辺に対応する曲線が自身および他の辺に対応する曲線と交わらない (任意の二曲線の共通部分がそれらの端点以外に存在しない) 描画を言う。平面描画を持つグラフを平面グラフ (planar graph) と呼ぶ。
定義 13.2.1 は正確であるものの、今までに定義されていない概念を使っている: 「滑らかな平面曲線」と「曲線の共通部分」である。図 \(\text{13.4}\) で例は見せたものの、これらの言葉の正確な意味は定義していない。
図は新しい概念を理解する上で非常に有用である一方で、正確な数学的議論で図を使うのは望ましくない。ときには、図だけに頼った議論が大きな失敗 ── 誤った証明 ── につながることもある。平面グラフが絡む命題に対するミスリーディングな図を使った正しくない証明には長い歴史がある。
悪いニュースがある: 定義 13.2.1 を使って平面グラフに関する事実を証明していくには、議論で必要となる平面幾何学や点集合トポロジーの概念を定義するために一章をかけて連続数学を学ばなければならない。良いニュースもある: 離散数学の概念だけを使って平面グラフを定義する別の方法が存在する。具体的には、平面グラフは再帰的データ型として定義できる。この定義を理解するには、グラフの平面描画における面 (face) の概念をまず理解する必要がある。
Steve Wozniak と平面回路設計
回路基板やマイクロチップといった物体の表面上に導線を配置するとき、導線が交差していると厄介な三次元的構造が必要になってしまう。Steve Wozniak が初期の Apple II コンピューター向けのディスクドライブを設計したとき、彼は設計を平面に近づけるために多大な労力を費やした。次に示すのは www.apple2history.org からの抜粋であり、Freiberger と Swaine による書籍 Fire in the Valley を引用している:
13.2.1 面
平面描画に含まれる曲線は平面を連結領域に分割する。この分割された連結領域を、平面描画の連続面 (continuous face) と呼ぶ1。例えば図 \(\text{13.5}\) に示した平面描画は \(4\) 個の連続面を持つ。この図の面 \(\text{IV}\) のように全ての方向に無限に広がる面を外面 (outside face) と呼ぶ。
図 \(\text{13.5}\) に示された連続面の境界にある頂点からは閉路が得られる。図 \(\text{13.6}\) のように頂点にラベルを付けたとすれば、各連続面の境界上にある頂点が定義する閉路はそれぞれ次の頂点列で表される:
\[ abca \qquad abda \qquad bcdb \qquad acda \tag{13.1}\]
これら \(4\) 個の閉路は図 \(\text{13.6}\) にある \(4\) 個の連続面にちょうど対応する ── 図 \(\text{13.6}\) の連続面は閉路から特定できる。これらの閉路は図 \(\text{13.6}\) の平面描画の離散面 (discrete face) と呼ばれる。閉路という離散的なデータ型を使って表されるので「離散」面である ── 平面上の領域のように「連続」ではない。
残念ながら、平面描画における連続面の境界が閉路を定義しない場合がある ── もっと複雑な状況があり得る。例えば図 \(\text{13.7}\) のグラフではカット辺 \(\langle c\>\text{---}\>e \rangle\) が橋 (bridge) なので、外面の境界上にある頂点を順番に並べると
\[ a\,b\,c\,e\,f\,g\,e\,c\,d\,a \]
となる。これは閉歩道を定義するものの、橋 \(\langle c\>\text{---}\>e \rangle\) が二回使われているので閉路は定義しない。
これとは異なる厄介な状況を図 \(\text{13.8}\) に示す。この平面描画は本書がドングル (dongle) と呼ぶ部分を持っている。具体的には頂点 \(v\), \(x\), \(y\), \(w\) とこれらを結ぶ辺からなる部分グラフがドングルである。内側の領域の境界上にある頂点を並べると
\[ r\,s\,t\,v\,x\,y\,x\,v\,w\,v\,t\,u\,r \]
であり、この頂点列が定義する歩道は閉歩道であるものの閉路ではない ── 歩道がドングルを「往復」するためにドングルに含まれる頂点が二回ずつ含まれる。
しかし連結グラフだけを考えるとき、特別扱いが必要な状況はここに示した橋とドングルだけとなる。特に、任意のグラフのあらゆる平面描画における連続面は閉歩道に対応する。次項で見るように、この閉歩道が平面描画の離散面 (discrete face) である。
13.2.2 平面埋め込みの再帰的定義
平面描画の連続面と閉歩道の関係を利用すると、連続面の代わりに利用できる離散的なデータ型を定義できる。これから連結グラフの平面埋め込み (planar embedding) を面の境界を構成する閉歩道の集合として定義する。グラフ理論で重要なのは頂点間の関係であってグラフの描画における点と曲線の位置関係ではないので、平面埋め込みはちょうど私たちが必要とする概念と言える。
では、どうすれば「連続な」概念を使わずに平面埋め込みを定義できるだろうか？ 利用されるのは次の観察である: これまで見てきた「連続的な」平面描画は、次の操作を繰り返すことで構築される:
-
頂点を表す点を平面上に新しく書き足す。
-
または、既存の二点を既存の曲線と交わらない新しい曲線で結ぶ。
「新しい曲線が他の曲線と交わらない」は「新しい曲線が一つの連続面に収まる」に等しい。つまり、同じ連続面の境界上にある二点の間には曲線を引くことができる。また、二つの独立した平面描画の外面の境界上にある二点の間にも曲線を引くことができる。曲線を書き足すと面が変化するので、そのたびに面の境界を更新しなければならない。この観察を利用すると、次の再帰的定義が得られる:
定義 13.2.2
連結グラフの平面埋め込み (planar embedding) とは、次の規則で再帰的に定義されるグラフの閉歩道の非空集合を言う。また、平面埋め込みの要素を離散面 (discrete face) と呼ぶ。
ベースケース: \(G\) が単一の頂点 \(v\) だけからなるとき、\(G\) の平面埋め込みは単元集合であり、その唯一の離散面は \(v\) で始まって \(v\) で終わる長さ \(0\) の閉歩道である。
構築ケース: [面の分割] \(G\) が連結グラフで、平面埋め込み \(\mathcal{E}\) を持つと仮定する。\(\mathcal{E}\) の何らかの離散面 \(\gamma\) に含まれる隣接しない異なる二頂点を \(a\), \(b\) とする。つまり、\(\gamma\) は \(a\) から \(b\) への歩道 \(\alpha\) と \(b\) から \(a\) への歩道 \(\beta\) を使って次のように表される:
\[ \gamma = \alpha \;\widehat{\,\phantom{\text{\small l}}\,}\, \beta \]
このとき、\(G\) の辺集合に辺 \(\langle a\>\text{---}\>b \rangle\) を追加したグラフは、\(\mathcal{E}\) の \(\gamma\) を次の二つの離散面2に置き換えた 平面埋め込み3を持つ:
\[ \alpha \;\widehat{\,\phantom{\text{\small l}}\,}\, \langle b\>\text{---}\>a \rangle, \qquad \langle a\>\text{---}\>b \rangle \;\widehat{\,\phantom{\text{\small l}}\,}\, \beta \tag{13.2}\]
構築ケース: [橋の追加] \(G\) と \(H\) が連結グラフで、頂点集合が共通部分を持たず、平面埋め込みを持つと仮定する。\(\gamma\) を \(G\) の平面埋め込みの離散面、\(a\) を \(\gamma\) の始点かつ終点とする。同様に、\(\delta\) を \(H\) の平面埋め込みの離散面、\(b\) を \(\delta\) の始点かつ終点とする。
このとき、\(G\) と \(H\) を新しい辺 \(\langle a\>\text{---}\>b \rangle\) で結んで得られるグラフは平面埋め込みを持つ。その平面埋め込みは、\(G\) と \(H\) の平面埋め込みの和集合から \(\gamma\) と \(\delta\) を除去し、次の離散面を加えた集合である:
\[ \gamma \;\widehat{\,\phantom{\text{\small l}}\,}\, \langle a\>\text{---}\>b \rangle \;\widehat{\,\phantom{\text{\small l}}\,}\, \delta \;\widehat{\,\phantom{\text{\small l}}\,}\, \langle b\>\text{---}\>a \rangle \]
一つ目の「面の分割」ケースの例を図 \(\text{13.9}\) に示す。
二つ目の「橋の追加」ケースの例を図 \(\text{13.10}\) に示す。
ここで \(G\) と \(H\) はそれぞれ次の平面埋め込みを持つ:
\[ G: \left\{ axyza,\ axya,\ ayza \right\} \qquad H: \left\{ btuvwb,\ btvwb,\ tuvt \right\} \]
橋 \(\langle a\>\text{---}\>b \rangle\) を加えて一つにしたグラフは、次の平面埋め込みを持つ:
\[ \left\{ axyz\underline{ab}tuvw\underline{ba},\ axya,\ ayza,\ btvwb,\ tuvt \right\} \]
橋はカット辺の別名に過ぎない。しかし平面埋め込みの文脈では、橋は同じ離散面に二度含まれる辺にちょうど等しくなる ── 橋でない辺は異なる二つの離散面に一度ずつ含まれる。また、ドングルは橋からなる木である: この用語は図示した平面埋め込みに対して使うだけなので、さらに正確に定義する必要はない。
13.2.3 この定義は本当に正しいのか？
正しい！ つまり、一般のグラフが定義 13.2.1 の意味で平面なのは、全ての連結成分が定義 13.2.2 の意味で平面埋め込みを持つとき、かつそのときに限ると示せる。もちろん証明には数学的に厳密な「連続」の概念が必要なので本書では省略する。しかし、平面グラフの再帰的な定義さえあれば後は離散的な概念だけを使って議論を進められる。これは良いニュースである。
ただ、悪いニュースもある。「辺が交差しない平面描画」という直感的で単純な概念と比べると、定義 13.2.2 は数学的な厳密さのために扱いやすさを犠牲にしている。多くの場合で、平面描画の概念だけを使って議論を進めて証明を書いた方が簡単になる。例えば、「平面グラフから辺を一つ削除したグラフは平面グラフか？」という単純な (真の) 命題さえ真偽と証明はそれほど明らかでない (参照: 問題 13.9)。
専門家の手にかかれば、そしておそらく読者も少し練習すれば、平面グラフに関する事実の説得力と信頼性のある証明を図に頼って書くことは難しくない。しかし、そういった証明に誤りが見つかった事件には長い歴史があるので、平面埋め込みの正確な定義から示した方が安全と言える。さらに広い視点で言えば、平面にグラフを描画したときの抽象的な性質を離散的データ型で問題なくモデル化できる事実を見ておくことは重要である。
13.2.4 外面はどこに？
全ての平面描画は外面を持ち、それは一目で認識できる ── 全ての方向に無限に広がる「外側の面」が外面である。しかし、平面埋め込みで外面はどこに行ったのだろうか？
平面埋め込みに外面は存在しない！ 正確に言えば、平面埋め込みに含まれる離散面を区別する理由が存在しない。そもそも、平面埋め込みを図にしたときの外面は一意に定まらない。直感的には、平面埋め込みは平面上ではなく球面上に存在するものと考えればこの事実に納得できるだろう。この球面のどこかに穴を開け、その穴を球自体より大きく広げ、そうした球面全体を平面に張り付けたものが平面埋め込みを表す (平面の) 図となる。そのため穴を開ける位置によって図における外面は異なる。
言い換えれば、「外面」の境界が異なる図が同じ平面埋め込みを表すケースがあり得る。例えば図 \(\text{13.11}\) に示された二つの図は同じ平面埋め込みを表す ── 離散面の境界を表す閉歩道が同じことを確認してみるとよい。
これは定義 13.2.2 の「橋の追加」ケースを正当化する事実でもある: 頂点集合が共通部分を持たない二つの平面グラフのそれぞれからどんな離散面を選んだとしても、その二つの離散面を結ぶ橋を他の曲線と交差させずに書くことができる。なぜなら、その二つの橋が結ぶのは必ず「外面」だと考えて構わないからである。
-
多くの文献は連続面を単に「面」と呼ぶものの、本章では以降で定義する離散面と区別するために「連続」の形容詞が必要になる。 ↩︎
-
この構築ケースには非本質的な例外が一つある: \(G\) が \(a\) で始まって \(b\) で終わる線グラフのとき、\(\gamma\) を分割して得られる二つの離散面が同じになる。なぜなら、辺 \(\langle a\>\text{---}\>b \rangle\) を追加したときに生まれる「外側」の連続面と「内側」の連続面の両方が新しい閉路を境界に持つためである。連続面と離散面の対応関係を保つために、この場合に得られる平面埋め込みは同じ閉路を二つ持ち、それぞれ異なる離散面を表すと定める。 ↩︎
-
形式的には、連結が可能なのは二つの歩道であって歩道と辺ではない。そのため、式 \(\text{(13.2)}\) は
\[ \alpha \;\widehat{\,\phantom{\text{\small l}}\,}\, (b,\ \langle b\>\text{---}\>a \rangle,\ a), \quad (a,\ \langle a\>\text{---}\>b \rangle,\ b) \;\widehat{\,\phantom{\text{\small l}}\,}\, \beta \]と表記した方が正確である。 ↩︎