閉曲面におけるグラフの最小彩色数について
59
0
0
全文
(2) の次数や同型、連結などの基本的な事項について 述べる。. 果たす。. 3．3節では、本論文のテーマである閉曲面の最. 1．2節では、グラフの頂点の彩色の定義を述べ. 小彩色数について考察する。閉曲面の最小彩色数. る。また、彩色する具体的な方法や、彩色数の評. は閉曲面に埋め込み可能なグラフの最小彩色数の. 価を述べる。. うちの最大値と定義する。そして、閉曲面の最小. 1．3節では、グラフの重要な性質の1つである 臨界について述べる。グラフが臨界的であるとき におこる、彩色数のよい評価を一般的なグラフに も応用できるよう定理を紹介していく。. 2章では閉曲面の分類を行う。. 彩色数が上からおさえられることを示すHeawood の不等式を証明する。. 4章では、前章で絞り込んだ、閉曲面の最小彩色 数を下からも絞り込み、最小彩色数の決定を行う。. 4。1節では、グラフのローテーションについて. 2．！節では組合せ多面体についての考察を行う。. 述べる。ローテーションを作ることによって、グ. 多角形を定義し、多角形を同一視して多面体を構. ラフが埋め込み可能な閉曲面を見つけ、閉曲面の. 成していく。また、こうしてできた多面体の記号. 最小彩色数の下からの絞り込みをする準備を行う。. 表現を作り、その性質を探り、多面体の向きも定. ローテーションの一つであるトライアンギュラー. 義していく。. ローテーションについて定義し、このようなロー. 2．2節では記号表現に初等的操作といわれる操. テーションの特徴から、あたえられた完全グラフ. 作を行う。初等的操作を行っても多面体が同相で、. を埋め込むことができる閉曲面の特定を行う。ま. 向き付けやオイラー数が変わらないことを証明し、. たローテーションのルールムを定義し下節で行う、. 多面体を分類する準備をする。. 最小彩色数の決定の準備をする。. 2．3節では、まず回数を定義し1行化や正規化、. 4．2節では、ローテーションとルールムを使っ. ハンドル正規化、クロスキャップ正規化、2クロス. て、完全グラフを埋め込むことのできる閉曲面を. キャップ正規化という操作で記号表現の特徴から. 構成していく。. 多面体の分類を行う。そして閉曲面と同相な多面. 完全グラフの最小彩色数は自明であるからこれ. 体が存在することから、閉曲面の分類とオイラー. により最小彩色数が既知のグラフの閉曲面への埋. 数を定義する。. め込みが構成でき、閉曲面の最小彩色数として最. 3章では、閉曲面の最小彩色数を上から絞り込 む。. 低限必要な色分がわかる。実はすべての閉曲面に ついて最小彩色数を決定できるような下からの評. 3．1節では閉曲面の最小彩色数を決定する際必要. 価がこの方法により構成できることがわかって. となる境界つき多面体について考察する。境界つ. いるが、本論文では4．3節でそのうち比較的簡単. き多面体を貼り合わせによって構成し、その境界. に構成できるものについて最小彩色数を決定する。. 擬iグラフや頂点の特徴を述べる。また、オイラー 数についても定義しその特徴を述べる。. 3．2節では、グラフの閉曲面への埋め込みにつ いて述べる。グラフを位相空間と考え、閉曲面に 埋め込むための必要条件について述べる。すなわ ち、グラフが閉曲面に埋め込まれるとき、グラフ の頂点数と丁数、閉曲面のオイラー数に関してあ る不等式が成り立つことを示す。この不等式が次. 節での閉曲面の最小彩色数の評価に重要な役割を. 主任指導教官 矢吹 治一. 指導教官濱：中 裕明.
(3) 平成11年度 修士論文. 閉曲面におけるグラフの 最小彩色数について. 兵庫教育大学大学院 教科・領域教育専攻 M 9 8 5 6 7 1. 学校教育研究科. 自然系コース 渡辺 一功.
(4) 序. 四色問題とは、「平面上に描かれた地図を、境界線で区切られた隣国同士は異なる色となるよ. うに塗り分けるとき、どんな地図も四色あれば塗り分けることができるか？」という問題で ある。事の起こりは19世紀、当時学生であったフランシス・ガスリーがイギリスの州別の 地図を塗り分けようとして、これが4色で塗り分けられることに気づいたことにはじまる。 彼はどんな地図に対しても4色で十分だろうかと疑問を持ち、当時講義を受けていたド・モ ルガン教授にこの問題について話した。ド・モルガンは大変興味を持ち、機会ある毎に数学 者仲間に話していくうちにこの「四色問題」は広まっていった。その後ケンペが証明を発表. し、10年以上正しいと信じられていたが、1890年Heawoodが証明の誤りを発見、しかし ケンペの証明は5色で塗り分けられることの証明にはなっていることを指摘し四色問題が難 問であることを再認識させた。1976年にアッペルとハーケンが、電子計算機による膨大な計 算とそのチェックによってついに証明を発表し、実に100年以上の年月を要して「四色問題」 は、「四色定理」となった。「四色問題」の証明への挑戦で生み出されたいくつもの発見が、 グラフ理論の発展に、大きく貢献してきたのは間違いない事実だと言われている。. 四色問題における地図の国、境界線をグラフの頂点、辺におきかえることにより、四色 問題は 「平面上に書かれたグラフの各頂点に色を、隣接する頂点は異なる色となるように 対応させるとき、どんなグラフでも4色あれば十分か？」という問題と本質的に等価になる ことが知られている。本論文ではこの問題を拡張して主として閉曲面上にかかれたグラフ について頂点の色付けを考え、そのために最低限必要かつ十分な年数を考察する。そして、 この閉曲面にかかれたグラフの頂点の色付けは、最も単純な閉曲面である球面にかかれたグ ラフの色づけが最も難しい。. 本論文の概要は、次の通りである。 1章では、グラフの定義とその基本的な性質について述べる。. L1節では、グラフの定義を行う。単純グラフと擬グラフの区別、完全グラフの定義、 また頂点の次数や同型、連結などの基本的な事項について述べる。 L2節では、グラフの頂点の彩色の定義を述べる。また、彩色する具体的な方法や、彩 色数の評価を述べる。. L3節では、グラフの重要な性質の1つである、臨界について述べる。グラフが臨界的 であるときにおこる、彩色数のよい評価を一般的なグラフにも応用できるよう定理を紹介し ていく。. 1.
(5) 2章では閉曲面の分類を行う。. 2．1節では組合せ多面体についての考察を行う。多角形を定義し、多角形を同一視して 多面体を構成していく。また、こうしてできた多面体の記号表現を作り、その性質を探り多 面体の向きも定義していく。. 2．2節では、記号表現に初等的操作といわれる操作を行う。多面体に初等的操作を行っ ても同相で向き付けやオイラー数が変わらないことを証明し、多面体を分類する準備をする。 2．3節では、まず種数を定義し1行化や正規化、ハンドル正規化、クロスキャップ正規 化、2クロスキャップ正規化という操作で記号表現の特徴から多面体の分類を行う。そして 閉曲面と同相な多面体が存在することから、閉曲面の分類とオイラー数を定義する。 3章では、閉曲面の最小彩色数を上から絞り込む。. 3．1節では、閉曲面の最小彩色数を決定する際必要となる境界つき多面体について考察 する。境界つき多面体を貼り合わせによって構成し、その境界擬グラフや頂点の特徴を述べ る。また、オイラー数についても定義しその特徴を述べる。 3。2節では、グラフの閉曲面への埋め込みについて述べる。グラフを位相空間と考え、 閉曲面に埋め込むための必要条件について述べる。すなわち、グラフが閉曲面に埋め込まれ るとき、グラフの頂点数と辺数、閉曲面のオイラー数に関してある不等式が成り立つことを 示す。この不等式が次節での閉曲面の最小彩色数の評価に重要な役割を果たす。. 3．3節では、本論文のテーマである閉曲面の最小彩色数について考察する。閉曲面の最 小彩色数は閉曲面に埋め込み可能なグラフの最小彩色数のうちの最大値と定義する。すなわ ち、閉曲面に埋め込むことのできるあらゆるグラフを彩色することのできる置数のうち、最 小のものを閉曲面の最小彩色数とするわけである。そして、閉曲面の最小彩色数が上からお さえられる事を示すHeawoodの不等式を証明する。 4章では、前章で絞り込んだ、閉曲面の最小彩色数を下からも絞り込み、最小彩色数の 決定を行う。. 4．1節では、グラフのローテーションについて述べる。ローテーションを作ることによっ て、グラフが埋め込み可能な閉曲面を見つけ、閉曲面の最小彩色数の下からの絞り込みをす る準備を行う。ローテーションの一つであるトライアンギュラーローテーションにを定義し、 このようなローテーションの特徴から、あたえられた完全グラフを埋め込むことができる閉 曲面の特定を行う。またローテーションのルールムを定義し次節で行う、最小彩色数の決定 の準備をする。. 4．2節では、ローテーションとルールムを使って、完全グラフを埋め込むことのできる 閉曲面を構成していく。. 完全グラフの最小彩色数は自明であるからこれにより最小彩色数が既知のグラフの閉 曲面への埋め込みが構成でき、閉曲面の最小彩色数として最低限必要な色数がわかる。 実はすべての閉曲面について最小彩色数を決定できるような下からの評価がこの方法 により構成できることがわかっているが、本論文では4．3節でそのうち比較的簡単に構成 できるものについて最：小彩色数を決定する。. 2.
(6) 最後に、この論文の作成にあたり、ひとかたならぬご指導を賜りました濱中裕明先生に 心より感謝の意を表します。. そして、兵庫教育大学における貴重な研究の機会を与えてくださいました兵庫県教育委員 会、芦屋市教育委員会、ならびに芦屋市立山手中学校の校長先生をはじめ教職員の方々に感 謝申し上げます。. 平成11年12月20日. 3.
(7) 目次 第1章. 5. グラフとグラフの彩色数. 1．1. グラフの定義＿．6．．．．＿．．. 1．2. n色彩色可．．．．．．．．．．．．．．．．．．．．．. 1．3. 臨界的なグラフとその性質．＿．．. 第2章 2．1. ．. ．. 9. 11. ，．． ．. 13 13 13 14 19 24. 曲面の分類 多面体． 2．1．1 多角形．．．．. 2．L2 多面体の構成．．．．＿．．，．＿．．。 ． 2．2. 初等的操作 ．．．．．．．．．．．．．．．．．．．．. 2．3. 曲面の分類 ．．．．．．．．．＿．．. 第3章. ．. グラフの閉曲面への埋め込みと曲面の彩色下. 3．1. 山面つき多面体．．．．．．．．．．．．．＿．．．. 3．2. グラフの閉曲面への埋め込み. 3．3. 閉曲面の最小彩色数と、Heawoodの不等式．．． ．. 第4章. グラフのローテーションと閉曲面への埋め込み. 4．1. グラフのローテーション．．．．．．．．．．．. 4．2. 向き付け可な閉曲面の最小彩色数の決定．．．．. 4．3. トライアンギュラ一点ーテーションの存在＿． ．. 4. 5. ．. 34 34 36 38 41 41 43 48.
(8) 第1章グラフとグラフの彩色数 1．1 グラフの定義 グラフとは一般に図1∼4のような頂点と辺から構成される図形であるが、抽象的に以 下のように定義する。. 図2. 図1. 定義1．12つの集合y、Eの組σ＝（γE，）において、 E⊂｛孟⊂yll刈＝2｝が成り立つ時 Gを単純グラフと言う. γの元を頂点、Eの元を辺と呼ぶ。 e∈E、α∈yに対して、θ∋αのとき、辺eは頂 点αに隣接しているといい、e卜αで表わす。 e∈El、α，6∈y（α≠6）に対して、 eトαかつ. eト6のとき、頂点α，6は隣接している、といい、α→eト6もしくはα＋6で表わす。また グラフGの頂点集合、辺集合という意味でyをV（G）、EをE（G）と表わすこともある。 厳密に定義するために上記のようにしたが、イメージとしては図のような頂点と辺からなる 図形と考えて差し支えない。. 単純グラフにおいては、定義から次のような性質が成り立つ。 1．すべての辺は必ず2つの頂点と隣接している。 2．頂点α，う∈y（α≠6）および辺θ，∫∈一Eについて、αヨeト6、α→∫ト6ならば、ε＝∫. となる。. 性質2から単純グラフにおいては、異なる2頂点を結ぶ辺は高々1本しかないので αHθトゐ（α≠6）のとき、eを辺訪と書くこともある。. 5.
(9) 定義1．2 グラフ∬とGにおいて、y（G）⊃y（∬）、 E（σ）⊃E（∬）のとき、∬をGの部. 分グラフと言い、π⊂Gと表わす。特にEとGが等しくないとき、丑をGの真部分グラ フと言う。Gの部分グラフEでγ（∬）に含まれる頂点のうち、 Gで互いに隣接している頂点 の組すべてが∬でも互いに隣接しているとき、丑をσの誘導部分グラフという。 定義1．32つの集合y、Eの組σ＝（鷲E）において、写像∫：一E→｛且⊂y11・41＝10r 2｝. が与えられているとする。このときσを擬グラフと言う。擬グラフの場合もe∈Eα∈y に対して八ε）∋αのときにeトαとすることにより、隣接を定義できる。ただし、擬グラフ. においては、単純グラフで見られた上記の性質1、2は成立しない。 単純グラフσ＝（鷲E）は、包含写像E・→｛．4⊂Vll川＝2｝を考えることにより、擬グ ラフの特別な場合と考えることができる。今後特に断りのない場合、グラフといえば、単純 グラフをさすものとする。. 定義1．4グラフθ＝（鷲E）において、yとEの元の個数が、ともに有限のときGを有限グ ラフという。今後本論文では、グラフといえば有限グラフをさすものとし、元の個数が無限 のグラフは扱わない。 定義1．5擬グラフにおいて、辺がただ一つの頂点に隣接しているとき、その辺を輪という。. 定義1．6擬グラフにおいて、2つの辺が同じ組の頂点、または同じただ1つの頂点に隣接し ているとき、これら2つの辺は平行という。 図3は平行な辺をもつ擬グラフの例、また図4は輪をもつ擬グラフの例である。. 図4. 図3. 定義1．7グラフσ＝（V；E）においてε1，ε2…％∈E1、ηo，”1…隔∈y「に対して Uo，e1，り1，e2，”2＿％”πという頂点と辺の交互の列を考える。すべてのe言に対して. 妬1→qト競が成り立つとき、この列を歩道という。この列に含まれる辺の総数ηをこの歩 道の長さという。”oを歩道の始点、煽を歩道の終点という。単純グラフにおいては、歩道 を表わす場合、辺を省いて、”0，”1，”2…ηπのように頂点だけの列で表わすこともある。 定義1．8歩道”o，ε1，η1，ε2，”2…e。，りηにおいてeI≠eゴσ≠の、陽≠ηゴ（2≠ブ）が成り立つと. き、これを道という。”o＝ひ．かっ”涙娠0≦￠≠ゴ≦η一1）のとき、これを閉じた道また はサイクルという。. 6.
(10) 定理1．9グラフσの頂点”o、η。に対して、この2点をそれぞれ始点、終点とする歩道が存 在すれば、この2点をそれぞれ始点、終点とする道が存在する。 証明 り。，り1…砺という歩道があるとする。これをwとする。. 1．Wに物コηゴσ〈のとなる頂点が存在しなければ、このWは道である。 2．W’＝Uo，η1…u言…％”ゴ＋1…ηηとし、りFuゴとなる頂点があったとする。”ゴ＋むゴ＋1. であるから、賜＋”ゴ＋1である。UO，η1…隔Uゴ＋1…むπという列を考えても、これは歩. 道になっている。これを瑚とする。瑠に、”ド物となる頂点がなければこれは道で ある。砺＝物となる頂点があれば、同様の操作を繰り返す。同じ頂点が出てこなくな るまでこの操作を行ったとき、それは道となる。よって定理は成り立つ。 嘱. 定義1．10単純グラフや擬グラフにおいて、どの2つの頂点をとっても、その2つの頂点を 始点と終点とする道が存在するとき、そのグラフは連結であるという。 定理1．9から、2点を結ぶ歩道が存在すれば、その2点を結ぶ道も存在することが証明 された。よって、連結の定義をするとき、「単純グラフや擬グラフにおいて、どの2つの頂 点をとっても、その2つの頂点を始点と終点とする歩道が存在する。」⇔「単純グラフや 擬グラフにおいて、どの2つの頂点をとっても、その2っの頂点を始点と終点とする道が存 在する。」となり、どちらを使っても良い。. 定義1．11グラフの頂点の次数について定義する。単純グラフにおいては、次数とは頂点に 隣接している辺の数と考えても良いが、擬グラフにおいては輪があるので次のように分けて 定義する。. 頂点αの次数は”頭α）であらわす。単純グラフにおいては、 ”α1（α）＝1｛θ∈」膠1εトα｝1. である。擬グラフにおいては、 りαZ（α）＝1｛e∈Eleトα，eは輪でない。｝1＋2i｛e∈Eleトα，eは輪である。｝1. となる。グラフGにおいて、頂点の次数の最大値を△（σ）または△であらわす。次数0の 頂点を孤立点という。. 定義1．122つのグラフG＝（鷲E）と（γ＝（γ’，E’）があるとする。全単射∫：V→y’が あって、. ”1，”2∈Vにたいして、”1十η2⇔∫＠1）十∫（η2） となるとき、2つのグラフσ＝（γE，）とG’＝（y’，Eノ）は、同型であるという。. 7.
(11) 定義1．13グラフのどの2つの頂点をとっても隣接しているとき、そのグラフを完全グラフ と言う。頂点数πの完全グラフをK。で表わす。 グラフには次のような性質がある。 定理1．14Gを単純グラフまたは擬グラフとし、｛η、，”2・一η。｝＝V（G）とする。この時. Σ蜘∂一21E（θ）1 2＝1 が成り立つ。. 証明 σを単純グラフまたは擬グラフとし、X＝｛＠，ε）∈y×1引uヨe｝とおく。 1．Gが単純グラフもしくは擬グラフで輪のない場合。 E（σ）の任意の元eに対して、＠，e）∈. Xとなる元は必ず2つずつあるから、 1♪（1＝211ヲ（σ）1. が成り立つ。またXは、頂点と頂点に隣接している辺の組の集合であるから、 ハ IXI一Σval＠∂ ぎ＝1. は明らかに成り立つ。よって ハ. Σ・・1＠∂一21E（G）1 づニ1. が成り立つ。. 2．σから、輪をすべて取り去ったグラフθoを考える。Goについては、 21E（G）1一Σval＠の 賜∈Go が成り立つ。（次数は、Goで考える）輪を1つ加えると、定義から次数は2増える。ま た21E（G）1も2増加する。今、有限グラフだけを考えているので、輪の数も有限で定 理が成り立つ。 ■. また上の定理は、単純グラフまたは擬グラフの次数の和が常に偶数であることを示して いる。よって次のことがいえる、 系1．15単純グラフまたは擬グラフにおいては、次数が奇数の頂点の個数は偶数である。. 証明 単純グラフまたは擬グラフθに、次数が奇数の頂点が奇数個あったとすると れ Σ・ψの づ＝1 の値は奇数となる。21E（σ）1の値は、明らかに偶数なので定理1．14に矛盾する。よって、系 は成り立つ。. 1. 8.
(12) 1．2 n色彩面部 この章では、前節で定義したグラフの頂点に色付けをすることを考える。互いに隣接す る頂点は異なる色となるように色づけすることを考えるのであるが、頂点に色づけする場合、 実際に色を塗っていく代わりに頂点に番号を割り当てていくという方法をとる。同じ番号の 頂点は同じ色と考えることができ、使う数を少なくすることで最小数の色づけを考えていく ことができる。. 定義1．16Gをグラフとする。写像∫：y（σ）→｛1，2，…η｝が、任意のσの頂点α，6に対し て、αと6が、Gで隣接しているならば、∫（α）≠∫（6）となるとき、！をσのn一彩色もしくは. 単に彩色という。Gのπ影色が存在するとき、 Gはn色彩色可という。 このように彩色とは実際に色を塗るのではなく、各頂点に数字を割り当てる事とする。. 定義1．17グラフσが、た色で彩色可でた一1色では彩色不可である時たをσの最小彩色数 といい、x（σ）またはxであらわす。∬⊂Gに対して、明らかにx（∬）≦x（σ）が成り立つ。. グラフの彩色を見つける方法の一つに、グリーディーアルゴリズムがある。グリーディー アルゴリズムとは、以下のような方法である。 1．y（σ）＝｛り1，η2…隔｝と頂点に順番付けを行う。. 2．最初にη1に、1を割り当てる。. 3．次にη2が、”1と隣接していなければ1を割り当てる。隣接していれば、2を割り当 てる。. 4．砺については、”1からu鳶一1までに1，2…1を割り当てたとし、次のようにする。. （a）”たが”1から”た一1のなかで1を割り当てたものと隣接していなければ1を割り当 てる。. （b）砺がη1から爆＿1のなかで1を割り当てたものと隣…接し、2を割り当てたものと 隣接していなければ2を割り当てる。 （c）この操作を繰り返し、1，2…1すべてに割り当てるものがなければ、1＋1をわり あてる。. ただし、グリーディーアルゴリズムを行うと、彩色はできるが、最小彩色数で彩色するとは 限らない。実際、図5のように頂点に番号づけを行うと、グリーディーアルゴリズムを使え ば、η1，り2，”3，η4に1、”5，η6，り7，η8に2が割り当てられ、最小彩色数による色づけを見つけ. る事ができるが、図6のように頂点に番号づけを行うと、グリーディーアルゴリズムを使え ば、η1，u2に1、η3，り4に2、η5，u6に3、、”7，”8に4が割り当てられ最小彩色数の色づけに. はならない。しかし、彩色する頂点の順を上手く変えることにより、最小彩色数で彩色を行 うことができる。一般にグラフの最小彩色数を求めることは容易ではない。 命題1．18グラフにおいて、彩色する頂点の順を上手く変えれば、グリーディーアルゴリズ ムによる彩色数と、最小彩色数は、一致する。. 9.
(13) ”2. η1. ”3. ”4. 図5. U5. ”6. η7. η8. り1. U3. ”5. ”7. 図6. η2. 1り4. tフ6. U8. 証明 σをグラフとしy（σ）＝｛り1，”2…η。｝とする。∫：y（σ）→｛1，2…m｝が、：最小彩 色数をあたえる写像であるとする。ノー1（1）＝｛u1，…，喝∫一1（2）＝｛η1＋1，…，uけ∫一1（3）＝. ｛”ゴ＋1，…，uの…このように、頂点を番号付ければよい。 璽. グリーディーアルゴリズムを使えば、△＋1色で彩色可の方法を見つけることはできる。 これによりグラフの最小彩色数を上から押さえることができる。 定理1．19σをグラフとする。このとき、X（σ）≦△＋1がなりたつ。 証明 y（σ）＝｛u1，u2…u。｝とする。グリーディーアルゴリズムを使って彩色するとき、. y（G）のある頂点吻に対して、それまでに△＋1色使われていたとする。val＠∂≦△であ る。また、物に隣接している頂点に使われている色の総数は、val＠∂以下である。よって、 △＋1色のなかに競に隣接している頂点に使われていない色が1つはあるはずである。よっ てその色を、競に割り当てられるので、彩色が△＋1色を超えることはない。 1. 定理1．20Gはグラフとする。∬はGの任意の誘導部分グラフとする。δ（∬）は、∬の頂点の 次数のうち最小の値とする。あらゆる∬のなかで、δ（∬）の最大値をんとすると、X（G）≦軒1 が成り立つ。. 10.
(14) 証明 1レ（σ）i＝ηとする。δ（∬）≦たであるから、V（G）のなかに、次数がた以下のある頂 点u。があるはず。σから、”。と”。に隣接しているすべての辺を取り去る。これをσ一｛ηπ｝. とかくことにする。瓦一1＝θ一｛u。｝とする。同様に、∬。樋のなかに、次数がん以下のある 頂点η。一1があるはず。瓦一2＝σ一連，”。一1｝とする。この操作を繰り返し、1点になるま で行う。γ（∬1），＝｛U1｝とすると、すべての点がη1，り2…η．とこの順に数え上げられる。こ の中のある頂点、物は、｛U1，η2・．●t】ゴー1｝のうち、高々焉個の頂点と隣接している。よってグ. リーディーアルゴリズムを使って彩色すれば、た＋1色以下で彩色可である。 ■. 1．3 臨界的なグラフとその性質 グラフの彩色数を絞っていく上で重要な概念として、臨界がある。最初に、グラフの臨 界的という状態について定義しておく。. 定義1．21グラフσにおいてX（σ）＝みとする。任意のσの真部分グラフ∬に対して、 x（∬）≦たとなるとき、σは、臨界的であるという。. また一般的なグラフと臨界的なグラフの間には次のような関係があり、臨界的なグラフの性 質を一般的なグラフに応用することができる。 定理1．22どんなグラフGもX（∬）＝X（G）となるような臨界的な部分グラフ丑を含む。 証明. もしGが臨界的なら、E＝σとして成り立つ。σが臨界的でないなら、 x（1／1）＝x（G）. となる真部分グラフ∬1がある。もし1／1が臨界的なら、111＝∬として定理は成り立つ。111 が臨界的でないなら、X（1τ1）コX（112）となる∬1の真部分グラフ∬2が存在する。σは、有 限グラフであるのでこの操作を繰り返していくとどこかでx偉．）＝x（G）となるσの臨界的 な真部分グラフ玩に行き着く。E＝」㌦として定理は成り立つ。 ■. また、次の二つの定理は、最小彩色数を決定するときに役に立つ良い評価となっている。 定理1．23σは、臨界的なグラフとする。このときGの任意の頂点”に対して、”α1＠）≧X−1 となる。. 証明 Gを臨界的なグラフとする。η∈γ（G），val（”）〈X−1となる頂点”があるとする。り に隣接している頂点を、η1，”2，…妬とする。σから、ηおよび、ηに隣接しているすべての. 辺を取り去る。これをG一｛η｝とかくことにする。σ一｛η｝は、σの真部分グラフである。 X（σ一のくX（G）よって、σ一｛η｝は、X−1色以下で、彩色可である。 G一｛暗にこの彩色. の一つを行う。ゐくX−1であるからり1，り2，…％は、X−2色以下の数の色で彩色されてい るはずで、G一｛u｝に彩色した色のうち”1，u2，…砺に使われていない色が一つはあるはず。 それを、りに彩色する。するとσは、X−1色で彩色可となり矛盾が生じる。よって定理は 成り立つ。 ■. 11.
(15) 上の2つの定理から、次の定理が導かれる。 定理1．24Gは臨界的なグラフとする。αo＝ly（σ）1，α1＝iE（σ）｝とする。 この時、（X−1）αo≦2α1がなりたつ。. 証明 σは臨界的なので、σのどの頂点も次数はX−1以上である。また、 む. Σ卿・）一2α・ づ＝1 が成り立つので、（）（一1）αo≦2α1がなりたつ。. この定理から、最小彩色数は頂点と辺の個数によってしぼることができる。. 12.
(16) 第2章 曲面の分類 2．1 多面体 2．1．1 多角形 この章では、（組み合わせ）多面体について述べる。最終的にグラフの閉曲面への埋め 込みを考えるのであるが、閉曲面のかわりに多面体を用いるわけである。多面体を作る要素 が多角形である。多面体は有限個の多角形をその辺の同一視により貼り合わせて構成され るのであるが、多角形として1角形や2角形も用いる。多角形は三角形以上のものについて は、ユークリッド空間における多角形をイメージしてもかまわない。. 定義2．1η角形はη＞3のときユークリッド平面上の1辺の長さ1の正η角形にユークリッ ド平面からの部分位相をいれた位相空間とする。 2角形はユークリッド平面上の部分空間としての単位円板のこととし、｛（cosθ，sinθ）1θ∈ ［0，π］｝および、｛（cosθ，sinθ）10∈［π，2π］｝をその辺とする。また（1，0）および（一1，0）を. その頂点とする。1角形は、ユークリッド平面上の部分空間としての単位円板のこととし、 ｛（cosθ，sinθ）1θ∈［0，2π］｝をその辺とする。また（1，0）を唯一の頂点とする。. 1角形、2角形は下図のような図形である。. 2角形. 1角形. 定義2．23角形以上の多角形の任意の辺を．4βとする。1＝［0，1］から、4βへの線形なパラ メーター付けを辺の向き付けという。具体的には、オ∈∫に対して、∫（オ）＝．4＋オ．4−Bまたは ノ（の＝B十オーBAのどちらかである。 2角形の場合は、辺｛（cosθ，sinθ）1θ∈［o，π］｝については. ∫（オ）＝（cosオ7「，sinオ7τ）、∫（オ）＝（cos（1一オ）7「，sin（1一オ）π）. 13.
(17) のどちらか、 辺｛（cosθ，sinθ）1θ∈［π，2π］｝については ∫（Z）＝（cos（1十孟）7「ラsin（1十オ）π）、∫（オ）＝（cos（2一オ）πラsin（2一オ）π）. のどちらか、. また1角形の場合は、 ノ（オ）＝（cos 2オ7「， sin 2オπ）、∫（舌）＝（cos 2（1一オ）π，sin 2（1一オ）π）. のどちらかのパラメーター付けを定めることを辺の向き付けという。パラメーターが0の点 をその辺の始点、パラメーターが1の点をその辺の終点という。. 定義2．32角形以上の多角形において、すべての辺に向きがあたえられているとする。ど の頂点にたいしても頂点は2辺に共有されているがその2辺のうち一方の辺については始 点もう一方の辺については終点となっているときこのすべての辺の向きの組を面の向きと いう。. 1角形については辺が唯一であるが、その辺の向きを面の向きという。. すべての多角形には、2つの向き付けがある。実際2角形以上の多角形においてひとつの 辺の向きを定めれば面の向きの定義からとなりあう辺についてつぎつぎに辺の向きが定ま るから2っしかないことがわかる。1角形についても向き付けが2つしかないのは明らかで ある。. 2．1．2 多面体の構成 上記で、定義した多角形を使って多面体を構成していく。多面体は有限個の多角形の辺 を以下の方法で同一視していったものとする。 1．すべての多角形の辺に向き付けをする。. 2．同じ数字が2回ずつあらわれるように、すべての辺に番号付けをする。 3．同じ番号の辺を、向きが合うようにはりあわせる。. ここで2から多角形の辺の総数は偶数となることは明らかであろう。3で辺と辺を向き が合うように貼り合わせるとは、辺隅βと、辺αDを、貼り合わせるとき ∫：1→孟β. 9：1→00 を、それぞれ辺AB、 CDのパラメーター付けとしたとき、みβ上の∫（オ）とσD上のg（オ）（オ∈1）. を貼り合わせるということである。この点飢，ッがこの貼り合わせで対応するとき∬∼宮と 書くことにし、関係斜を定める。. 14.
(18) 多面体は位相空間としてはこの関係弼によって生成される同値関係∼で有限個の多角 形に商位相をいれた空間となる。. 関係∼によって生成される同値関係∼とは具体的には、. 一｛1二∴．．＿，. で定義される。. 貼り合わせによる同一視において、次のことはすぐわかる。 1．面の内点は、他のどの点とも同一視されない。. 2．辺の端でない点は、他の辺の端でないただ一つの点と同一視される。 3．頂点は、必ず頂点と貼り合う。. 同一視した後、それぞれの多角形のことをその多面体の面という。同一視された多角形 の辺を多面体の辺、同一視された多角形の頂点を多面体の頂点という。. 定義2．4多面体Σにおいて、その頂点と辺だけによって擬グラフが構成される。この擬グ ラフをΣであらわす。. 定義2．5空間Xのどの点をとってもRπの開集合と同相な近傍を持つとき、Xをη次元位 相多様体という。. 定理2．6多面体は、2次元位相多様体である。 証明. 1．面の内点については、多面体の面且上の任意の内点αに対して、αの開近傍σ（のが、 σ（α）⊂Aとなるように取れるのでR2の開集合と同相な近傍をもつ。. 2．多面体の任意の辺Eはちょうど2つの多角形の辺が貼り合わされているので、その多 角形をA、Bとする。辺E上の端でない任意の点eについては、その開近傍σ（e）を、 下図のようにσ（e）⊂AU−Bとなるようにとれば良い。 3．頂点については、上記のように同一視していくと、多面体の任意の頂点灘は、有限個 の多角形の頂点が同一視された点である。その中の一つの頂点を￠oとする。多角形に. おいて頂点は2辺に共有され、貼り合わせば辺ごとに生じるから、鞠弼籟となるよ うな頂点籟は、2っしか存在しない。そのどちらか一方を￠1とする。次に、￠1側鋤 となるηのうち、物でない方の頂点を、￠2とする。この操作を繰り返していくと、頂. 点の列 ω0，ω1，ω2，●●。. 15.
(19) u（a）. B. a. A. がえられる。この列を5とする。有限個の頂点を同一視しているからどこかで η＝吻（乞くブ）. という頂点があるはずである。このとき列θでつぎの頂点を決めていく操作は可逆 だから、. ∬o＝吻＿唇（乞くゴ）. となる。ブー￠をmとおいて、∬0と同一視される頂点∬0，銑，…，￠m−1が得られた。. ｛矧0≦￠≦m−1｝をTとおく。ここで￠o弼￠1弼…弼編一1舘￠oに注意する。. 逆に鞠とッが、同一視されるとすると∼の定義から妬弼α1弼α2弼…弼転斜ッ となっている。任意の頂点と貼り合う頂点は2個しかないから、賜と貼り合う頂点は ｛矧0≦乞≦m−1｝のなかのどれかである。よってα1はTのなかのどれかになってお り、砺がTのどれかになっていれば、α組もTのどれかになっているから、ッもTの なかのどれかになっていることがわかる。. よって、鞠と同一視される頂点は、Tですべてであることがわかる。この時、図のよ うにXの開近傍σ（X）をとれば良い。. こうしてできた多面体は多角形を貼り合わせたものであるから貼り合わせ方を指定すれ ば決定される。面と辺に番号をつけて以下のように貼り合わせを表記することにする。 1．各面に向きを与える。. 2．各面についてその向きに沿って辺に対応する番号を順に書き並べる。 3．面の向きと、辺の向きが逆のときは、番号に｝1をつける。. 16.
(20) U（X）. ω2. 灘m＿1 ω1. 必0. b. b. f. a. A d. a. C. C. C. B f. e. D. d. e. 正4面体. このようにしてできた表現法を、多面体の記号表現という。各面の記号表現を、その記 号表現の行という。多面体の記号表現を表す場合、番号のかわりに記号を用いることもある。 例として下図のような、正四面体の記号表現を考える。. 各面の向き付けば、すべて反時計回りとすると、記号表現は ．4．c6−1d −B．αc−1ε一1 σ．αゐ一1／. 1）．ε一1∫一14. となる。このように、面の記号の後にピリオドを打ち、そのあとに辺の記号を並べた行を書 き並べて記号表現を表記することにする。 記号表現には、どの番号もちょうど2回ずつ表れるという性質がある。. 定理2．7多面体Σが連結ならば、記号表現は上記の性質「どの番号もちょうど2回ずつ表 れる」を満たすような2っの行の集合に分けられない。またその逆も成り立つ。 証明. 17.
(21) 1＿蝋1≦乞≦η），βゴ（1≦ブ≦m）は、多角形とし、. Σ＝且、UA2U…んuB、Uβ2U…β㎜／∼ とする。Σが連結で、記号表現が「どの番号もちょうど2回ずつ表れる」2つの行の集 合に分けられたとし、それぞれの行の集合に対応する多角形の集合を｛．41，、42，…，ん｝ と｛B1，β2，…，B滑とする。. この時. ノ11UA2U… UAπ／∼ と. BIUB2U… Uβ皿／∼ を考える。. 多角形の同一視は、同じ記号のついた2本の辺を貼り合わすことで行うため、 AIU／12U… U．4π／∼. の辺と. B、UB2U…Uβ飢／∼ の辺が貼り合わされることはないはずである。つまり多面体Σが Σ＝（A、Uん∪…U塩／∼）H（β、Uβ2U…UB視／∼） となっているわけである。ところがΣは商位相で、．41，、42，…ん，B1，一B2，…β祝はそ. れぞれ開集合であるので、AUん∪…uA。／∼と一β1Uβ2U…UB況／∼は、Σにお いてそれぞれ開集合となる。よってΣは、2つの開集合に分けられるので、連結の仮 定に反する。. 2．Σが、「どの番号もちょうど2回ずつ表れる」ような2つの行の集合に分けられないと する。行がただ1つのとき、つまり面が1つのときは明らかに弧状連結である。行が 2つのとき、仮定よりその2つの行両方に表れる番号があるはずである。よって、その 辺が同一視されることで、2つの多角形はつながるので、やはり弧状連結になる。行 が3つ以上の場合も同様に、2つの行に表れる番号によって、すべての多角形はつな がっていくのでやはり弧状連結である。よってΣは、連結である。 □. 定理2．6より、多面体は位相多様体であるから、ここでは連結と弧状連結は同値で上記 の定理は、仮定を弧状連結に置き換えても成立する。 以降、連結な多面体だけを扱うものとする。. 多面体の記号表現は一意的ではない。実際、面の向きや辺の向きの入れ換えで、同じ多 面体が違った記号表現で表されることもある。よって次の操作を行っても、同じ多面体の記 号表現となっている。. 18.
(22) 1．記号表現のある行において、巡回置換を行う。 2．同じ番号について、指数を入れ替える。. 3．ある行について次の2つの操作を同時に行う。 （a）指数をすべて逆にする。. （b）行の並びを逆にする。すなわち、一番後ろの番号が先頭になるよう逆順にする。. 定義2．8多面体Σにおいて、Σのすべての辺の番号が記号表現において両方の指数（両方 の方向）で表れるようにすべての面に向き付けができるとき、この多面体は向き付け可とい う。またどのように面を向き付けしても、すべての辺の番号が両方の指数で表れないとき、 この多面体は向き付け不可という。. 2．2 初等的操作 多面体の記号表示に対して、次の4つの初等的操作を考える。 1，記号表示の中のある文字αについて、αを6cに、α一1を。−16−1に置き換える。この操. 作を、1次元細分という。 2．1次元合成とは逆の操作を行う。つまり記号表示の中のある文字6，cについて、6cもし くは。−16−1という並びが2つあればゐ。をαに、ビ16−1をα『1に置き換える。この操作. を、1次元合成という。 3．記号表示の中に、 α・ ・6C…. 4. という1行があるとき、これを α＿醜一1 た。…4 ， という2行に置き換える。この操作を、2次元細分という。 4．2次元細分とは逆の操作を行う。つまり、記号表示の中に、. α＿醜一1 ん。…d という2行があるとき、 α…6c… （1. という1行に置き換える。この操作を、2次元合成という。. 19.
(23) 定義2．9Σ、Σ’を多面体とする。初等的操作を有限回行うことによってΣの記号表示をΣ’ の記号表示に変形できるとき、ΣとΣ’は初等的関係があるという。 定理2．10多面体Σ，Σ’が、初等的関係にあれば同相である。. 証明 初等操作4つそれぞれについて行った結果が同相である事を示せばよい。多面体Σ の記号表現を（Σ）とする。. 1．2次元合成の場合ん（1＜乞くη）は多角形とし、. Σ＝・41H／12H… HAπ／∼. とする。且1と．42が、貼り合う辺を共有しているとして、A1と．42のその辺を先に貼 り合わせてから他の辺を貼り合わせてもよい。m角形孟1と、η角形んを一辺で貼り あわしたものは、η＋m−2角形と同相なので、A1と五2を貼り合わせれば、同相な多 面体，. （（且、U孟2／∼）H且3H…H且m）. になる。これを、記号表現で見ると、辺たで、多角形Aとんを貼り合わせるとして、 5，7は、それぞれ番号の列を表すとして、 且、．θた一1ん．艀. となっており、これを貼り合わせれてできた多角形罵の行は、 且i．∬. となるので、2次元合成は位相を変えない。 2．. （Σ）. α… う。… （1. とする。2次元細分を行ってΣ’が得られたとすると、. （Σ’）. α… ゐん一1. た。…4 と記号表現が変わる。この（Σ’）に2次元合成を行うと、（Σ）が得られるからΣとΣ’は. 同相になる。よって、2次元細分は位相を変えない。 3．. Σ1＝AIHA2H… ノ㌔／∼. 20.
(24) として、五1，A2の行が同じ番号αをもつ辺を共有していたとする。面の向きを適当に 定めてやれば、A1，んの行の記号表現を 且1．… α… ．42．…α一1… としてよい。αについて1次元細分を行い、新しい多角形A、’，A2’がえられだとすると、. 且i．…6c… ・4…．…ビ16−1…. という2行がえられる。こうしてできた新しい多面体をΣ2とする。Σ1で、先にA1 と孟2を、辺αで貼り合わせた多面体以と、Σ2で、先に罵と遜を、辺6，Cで貼り 合わせた多面体瑳を考える。このとき、且1Uん／∼，罵∪馬／∼以外は全く同じで、 、41∪．42／∼，．4窪U．4も／∼の部分も下図のように同じになるので、Σ壬と易は同じ多面 体になる。. b ．42. ．41. b. 、41. ．42. C. C. 4．またある行が 一1 … α… α …. となっている場合は、まず2次元細分を行い、 ．．・α… た た一1… α一1．．．. と変形し、次に1次元細分を行い、 … わC…. た. つ た一1＿C−16−1＿. とし、さらに2次元合成を行うと、 ＿6C＿C−1わ一1＿. とできる。行った操作はすべて位相を変えないのでこの操作も位相を変えない。よっ て1次元細分は位相を変えない。. 21.
(25) 5．1次元合成も1次元細分のまったく逆の操作で行うのでやはり位相を変えない 定理2．11初等的操作を行っても向き付け可な多面体は向き付け可に、向き付け不可な多面 体は向き付け不可な多面体に変形される。 証明. 1．向き付け可な多面体があり、その記号表現の任意の記号で1次元細分を行うと、. ＿α＿α一1＿ となっている記号αならば、 ．δC＿＿ビ16−1．. となり、新しく出てきた記号6，cについても両方の指数が出てくるので向き付け可で ある。. ・。. ｿ・. 。α一1．. となっている記号αならば、 ．・. Uc＿. ＿C−16−1．. となり、やはり、両方の指数が出てくるので向き付け可である。. 1次元合成はこの逆の操作なのでやはり指数が両方出てくるので向き付け可な多面体 は向き付け可な多面体になる 2，向き付け可な多面体があり、その記号表現の任意の記号で2次元細分を行うと、 α・・ゐ。・ ・4. という1そ了が、. α＿．6ん一1. ん。…4 に変わったとすると、新たに出てくる記号んについても両方の指数が出てくるので多 面体は向き付け可である。2次元合成はこの逆の操作で、消える記号た以外の記号も 両方の指数で出てきているので、やはり向き付け可な多面体になる。 よって、初等的操作を行っても向き付け可な多面体は向き付け可な多面体になる。. また向き付け不可な多面体に初等的操作を行い向き付け可な多面体にできたとする。 初等的操作は可逆な操作なので、これは向き付け可な多面体が初等的操作で向き付け 不可な多面体になることになり矛盾。よって向き付け不可な多面体は初等的操作で 向き付け不可な多面体にうつる。 1. 22.
(26) 定義2．12多面体Σにおいて、αoをΣの頂点の数、α1をΣの辺の数α2をΣの面の数とす るとき、α0一α1＋α2の値を、Σのオイラー数といい、E（Σ）であらわす。. 初等的操作を行うと、多面体のオイラー数を変えずに記号表現を変形することができる。 定理2．13Σは多面体で、Σ’は、Σと初等的関係がある多面体とする。この時、E（Σ）＝E（Σ’） となる。. 証明 Σの、頂点数、辺の数、面の数をそれぞれα0，α1，α2としΣ’の、頂点数、辺の数、面 の数をそれぞれα6，α1，妬とすると E（Σ）＝α0一α1十α2 E（Σ’）＝α6一αi十α灸 となる。. 1．（Σ）に1次元細分を1回行って（Σ’）になったとすると、図のように面はそのままで、頂. 点数と辺数がそれぞれ1増加するから、. 1次元細分. Σ. Σノ. ノ. α2＝α2 α左＝α、＋！. α6＝α。＋1. 23.
(27) となっている。よって、 E（Σ）＝・配（Σ’）. が成り立つ。1次元合成は、1次元細分の逆の操作なのでやはり成り立つ。 2．Σに2次元細分を1回行ってΣ’になったとすると、図のように面数と辺数がそれぞれ 1増加するから、 b. a. b. 2次元細分 幽一一■一■一■一■一騨一●・ ．. ’＼＼／で α6＝α2＋1 α1＝α、＋1 ノ α0＝α0 となっている。よって、 E（Σ）＝E（Σ’）. が成り立つ。2次元合成は2次元細分の逆の操作なのでやはり成り立つ。 よって、初等的操作を有限回行ってもオイラー数は変わらない。. 2．3 曲面の分類 すべての多面体は、その向き付けと忌数と呼ばれる値によって初等的な関係にある多面 体に分類される。この節ではその分類方法について考察していく。. 定義2．14正の整数pに対して次の記号表現 （3，）・、6、α、一16、一1α、6、・、一1ゐ、一1…・，6，α，一16，『1. 24.
(28) であらわされる多面体を3pで表わす。また30は、 （30）αα一1. であらわされる多面体として定義する。θpφ≧0ノが向き付け可な多面体であることは明 らかであろう。. pのことを3pの種数という。. 定義2．15正の整数qに対して次の記号表現 （Nq）・、・1・、α、…・，・，. であらわされる多面体を瑞で表わす。. 萬権≧1ノは向き付け不可な多面体になる。gのことを瑞の面隠という。 定理2．16Σが向き付け可で連結な多面体ならば、ある整数p伽≧0ノが存在してΣはθpと 初等的関係になる。. 定理2．17Σが向き付け不可で連結な多面体ならば、ある整数q臼≧1ノが存在してΣはNq と初等的関係になる。. 以下上記2つの定理を証明する。これらの定理を証明は、実際に多面体の記号表現を 変形していくことで行うが、よく使う記号表現の変形の方法を先に紹介しておく。 記号表現の変形の説明においてはいくつかの辺（文字）の並びをあらわす記号をもち いると便利である。以下小文字のアルファベットはひとつの辺を表わす文字とし、大文字 のアルファベットは有限個の小文字のアルファベットの記号の列を表わすこととする。ただ し、大文字のアルファベットが、空の列を表わす場合もある。また、大文字のアルファベッ トで表わされたP＝α1α2…α。という列があったとき、P−1は、α。一1α。一ゴ1…α1−1という. 列を表わすこととする。. 1．連結な多面体が2つ以上の面を持っているとき、2次元合成を有限回使うことによって ただ1つの多角形からなる多面体に変形できる。この時、この多面体の記号表現は1行 になる。この操作を記号表現の1行化という。 2．記号表現の中に、 Pαα一1（2. という行があれば、. P9 という形に変形できる。このような操作を、記号表現の正規化という。実際. 25.
(29) 1次元合成で酌一1＝ととする. PC. −c−19 エ聾pg という操作によって1行に変形できる。次の図からわかるように、この変形により多 面体の面の辺の数は減少している。 ．∴・…’’’’”ぎ’’’’’’”∵. ．．．マ／・”／’潤”’”＼1. − a. a. a. a. 3．また、次のような記号表現の行、 P・96Rα一13う一1T. は、 PθR（∼T・ゐα一16−1. という2つの記号を行の後ろに並べた形に変形できる。このような変形をハンドル正 規化という。実際、 Pα（26Rα一15’6−1T一三型. 至望禦塩＿1丁. 巡回置換 96E・Pα「. 一α一136−1Tc−1 一堕璽96R，Pαα一・3わ一・T，一・墾。一・9bR。Pθ6一・T 2次元細分 C−1Q6E凶 巡回置換 RcたC−19b ん一1P3ゐ一1T. 26. 6−1Tん一1」Pθ.
(30) 難E。た。一・966一・7ゼP3王型三磁。一・gTた一・P5墨。一・9％一・P5舩 cについても同様に、 2次元細分 C−19乃. 巡回置換 9乃・『1. ゴー1ん一1PθEcた. Cんゴー1た一11）θR. 郵97ブ。一・Cんプ・た一・P5￡王聾9蹄プ・ん一・PθR. 墨PθRgT殉一・た一・聾P5丑9T。ゐα一・6−1 4．また Pc（∼cE. のような記号表現は、 P9−1Ecc. という、同じ文字を後ろに並べる変形ができる。このような変形のことを、クロスキャッ. プ正規化という。やはり初等的操作を使って変形していくと. P・g・丑2型綴. ・行・・攣変えて順番・逆にして・・行・には巡騰・行・P−1た・一1. c磁（2. たRc. 遡P一・ん磁（∼墨た磁（∼P一・塑 C−1ん（∼P−1 1行目に巡回置換、2行目は指数を変えて順番を逆にする. Ecん た一1C1）（∼一1. 2塑塑塾Eccpg一・聖攣pg一・RCC と変形できる。 5。. 1∼CCα6α一1ゐ一1. 27.
(31) のような行を、. Rccαα6み. という形にする変形を、2クロスキャップ正規化という。実際、 ECCα6α一・6一・墾α一・6一・ECCα6. 2次元細分. α一16−1」配Cた 巡回置換. た一1Cα6. ・Rcたα一16−1. 6ん一1Cα. 一R，んα一・ん一・Cα一心。た一・αCC. 一蝕んccαα一Rccαα66 これらの変形を使って、定理の証明を行う。 定理2．16の証明 向き付け可で、連結な多面体Σの記号表現を（Σ）とする。向き付け可. なので記号表現においてすべての番号は両方の指数をもつようになっているとしてよい。 （Σ）に、1二化を行い、できるかぎり正規化をおこなう。ここで記号表現の行が （Σ） α1α1−1. となるならば多面体Σは50と初等的関係になるので定理がなりたつ。もし5bにならな いときは記号表現に…α1α1−1…となる部分はないとしてよい。 よって任意の記号α1に対して、 一Pα1（∼α1−1R（gは、空でない）. という形に表わせる。gをできるだけ短くできるようにα1を選ぶと、 gからう1を一つ選べ ば、6f1は、 PかRにはいっている。もしそうでなければ、61わf1の長さが、 gより短くな. りgの取り方に矛盾する。よって適当に指数を逆にすれば記号表現は （Σ） Pα1961、Rα1−1361−1T. となるのでハンドル正規化を行えば、記号表現は P5丑9Tα161α1−161−1 となる。一P3丑（2TをあらたにPとおく。 1．一Pが、空ならα1b1αゴ161−1だけになる。. 2，Pが空でないなら、できるだけ正規化を行うと、先ほどと同様の議論により記号表現は …α、…6、…α牙1…6牙1…・、ゐ、・、一1b、一1. 28.
(32) という形になっているとしてよい。よって一Pが空でないならこの記号表現は 伽、9、δ、R、α牙15、6牙1乃・、6、αf16f1. という形に表現できる。 遡ち9、丑、3、乃・、6、ατ16τ1・、6、α牙・6牙・. 鳥（∼2R232乃に正規化を行い、空になればα1ゐ1αr1ゐτ1α262αヂう計だけが残る。空でなけ. れば更にハンドル正規化と正規化を行っていくと、行の長さが増えることはないから 最終的に、 ・・6・αf16f1α・6・・牙1う牙1…α，ゐ，・∬16憂1. という形が残る。 □. このようにしてできた ・・う・αr1ゐτ1・・う・・牙1ゐ牙1…α，6，・憂16憂1. を、種数pの向き付け可な多面体の正規形という。また、文字が1っだけになるαα一1とい う形の記号表現を、球面の正規形という。. 定理2．17の証明 向き付け不可で、連結な多面体Σの記号表現を（Σ）とする。（Σ）に、1行化を行い、正規化 をできる限りおこなう。向き付け不可なのでここで記号表現が50となることはない。さら に向き付け不可能性からおなじ指数をもつ文字があるはずなので、記号表現は （Σ） PcgcE という形をしているとしてよい。よって、クロスキャップ正規化を行えば、 （Σ） P（∼一11∼cc. となる。さらにもしPg−1Rのなかに同じ指数をもつ文字があれば、その文字についてクロ スキャップ正規化をおこなう。これをできる限りくりかえすと、記号表現は WCICIC2C2…CオC孟 となる。. Wのなかのすべての記号は、すべて両方の指数で表れる。実際、もし同じ指数の記号が あれば、もう一度クロスキャップ正規化を行うことができるので仮定に反する。よって、W は次のように表わされる、 W＝P、α、9、う、R、αi1θ、6τ1T1. 29.
(33) 実際定理2．16の証明でおこなったように、α161を選べばよい。. Wのなかのα161についてハンドル正規化をおこなうことにより、 W。、C、C、C、…・，C、遡隅・、C、C、C、…・、C，α、ゐ、。τ・6τ・. となる。ただし、隅＝P131E1（∼1銑とおいた。. ここで、略が、空でないなら正規化を再度できるかぎりおこない、Wについておこ なったようにハンドル正規化を繰り返せば 一審、C、C、C、…C，C、α、6、・r・6τ・。、6。α、一16、一1. 一・、C、C、C、…・，C，α、ゐ、・f・6τ・…・。わ。α」・6」・. ここで5は0かもしれないが、オは正であることに注意する。よって。衝α161αflbτ1の部分 に対して2クロスキャップ正規化をつぎつぎにおこなえば 2クロスキャップ正規化をできるだけ使う. CICIC2C2。●’CqCg. となり、定理が証明された。 ■. こうしてできたCI CI C2C2…CgCgを、種壷gの向き付け不可な多面体の正規形という。. この多面体の正規形のオイラー数をもとめておく。. 定理2．18種数pで、向き付け可な多面体の正規形のオイラー数は、2−2pである。 証明 1．. ・・6・・f16τ1α・6・α牙1ゐ｝1…α，6，α憂16憂1. で表わされる同一視する前の多角形の頂点数は4pである。この多角形の頂点を記号表 現の最初の文字α1で表わされる辺の始点から面の向きにそってη1，”2，…，”4pとする。 α1は、”1，”2に隣接し、61は、”2，”3に隣接し、α1−1は、り3，”4に隣接している。一般に は砺は”4ゼ＿3，り4ゼ＿2に隣i接し、αr1は”4レ1，η4」こ隣i接し、さらに砺は”4ぎ＿2，り4か1に隣i. 接し、6歪一1は”肋U餅1に隣…接している。α2とα2−1の貼り合わせで、η42−3と隔、咄一1. と”42−2が同一視される。6信と62−1の貼り合わせで頂点は、”4臼と鞍、”42＋1と劃一2. が同一視される。よってこれらから、すべての頂点が同一視されるので頂点数は1と なる。. 同一視を行うと、辺は2っずつが貼り合わされるので辺数は2pになる。 また面は明らかに1つなので、 19（5p）＝＝1−2p十1＝2−2p. 30.
(34) 2．次に、球面の正規形α1α1−1の場合は、頂点数2、辺数1、面数1となるので、 E（5b）＝2−1−1−1＝2. となり、やはり成り立つ。 1. 定理2．19向き付け不可な多面体の正規形のオイラー数は、2−qである。 証明 clclc2c2…CqCqで表わされる、同一視する前の多角形の辺数は2qである。この多角形 の頂点を記号表現の最初の文字C1で表わされる辺の始点から面の向きにそってU1，U2，…，”2q とする。とする。最初に表れるC1は、”1，η2に隣接し、次のC1は、η2，η3に隣…接し、次のC2. は、”3，η4に隣…接している。一般には最初に表れるQはU2臼，砺に隣接し、次に表れるC2は ”％，砺＋1に隣…接している。Qの貼り合わせで、砺一1とη21および砺と砺＋1が同一視される ので、すべての頂点が同一視される。. 同一視を行うと、辺は2つずつが貼り合わされるので、暦数はqになる。 また、面は明らかに1つなので、 1ヲ（！＞q）＝！−q十1＝2一く1 ■. 以上のことから、連結で向き付け可な多面体はすべて、それと初等的関係のある3pが存 在し、そのオイラー数は2−2pとなることがわかった。連結で向き付け不可な多面体もすべ て、それと初等的関係のあるNqが存在し、そのオイラー数は2−qとなることがわかった。 定理2．202つの連結で向き付け可な多面体Σ，Σ’のオイラー数が等しいならば、Σ，Σ’には、. 初等的関係がある。. 証明 Σには、オイラー数が等しく初等的関係のある魯が存在する。また、Σ’にもオイ ラー数が等しく初等的関係のある3p’が存在する。 E（Σ）＝E（Σ’）で、初等的関係があれば同. じオイラー数であるから、3Pと3〆は、オイラー数が等しい。ゆえに、2−P＝2一〆とな り、p＝p’より、実はθp＝5p’である。よって、Σは、θpと初等的関係があり、3pとΣ’に も初等的関係があるので、Σ，Σ’には、初等的関係があるといえる。 匿. 定理2．212っの連結で向き付け不可な多面体Σ，Σ’のオイラー数が等しいならば、Σ，Σ’に は、初等的関係がある。. 31.
(35) 証明 Σには、オイラー数が等しく初等的関係のある1＞gが存在する。また、Σ’にもオイ ラー数が等しく初等的関係のあるNq’が存在する。 E（Σ）＝E（Σ’）で、初等的関係があれば. 同じオイラー数であるから、瑞と1Vq’は、オイラー数が等しい。ゆえに、2−q＝2−9’と なりg＝4より、実はNq＝1＞g’である。よって、Σは、1Vqと初等的関係があり、！＞qとΣ’ にも初等的関係があるので、Σ，Σ’には、初等的関係があるといえる。 圏. 定理220、2．21から、定理2．11、2．13とは逆にオイラー数が等しく向き付けがともに可、. またはともに不可の多面体には初等的関係がある事が分かる。また、定理2．10の逆について も証明しておく。証明をするために、次の定理を認めることとする。 定理2．22 1．5pと3p’において、 p≠〆ならば、5pと3p，は、同相ではない。 ゑ！＞qと1＞q，において、q≠g’ならば、 Ngと瑞’は、同相ではない。. 33pとNgは、同相になることはない。 定理2．232つの多面体Σ，Σ’が、同相ならばΣ，Σ’には初等的関係がある。 証明 1，Σ，Σ’の一方が向き付け可で、もう一方が向き付け不可のとき、Σを向き付け可とする. と、Σには、オイラー数が等しく初等的関係のある5pが存在する。また、定理2．10よ り、初等的関係のあるものは同相であるから、Σと3pは同相である。Σ’は、向き付け 不可となるのでΣ’には、オイラー数が等しく初等的関係のあるNqが存在する。やは り、Σ’と！Vgも同相になる。定理2．22より、5pとNqが同相になることはないから、Σ とΣ’が同相になることはない。言い換えると、向き付けの可、不可の違う多面体は、 同相になることはないわけである。 2．Σ，Σ’が、ともに向き付け可ならば、Σには、オイラー数が等しく初等的関係のある3p が存在する。また、Σ’にもオイラー数が等しく初等的関係のある3p’が存在する。初 等的関係のあるものは同相であるから、Σとθpは同相であり、Σ’とθ〆も同相である。 よって3pとθp’は同相になる。もしp≠p’ならば、 E（3p）≠E（3〆）となり、3pとθp，. は同相にならない。ゆえに、p＝〆となり、3p＝3〆である。よって、Σ，Σ’は、同じ 3pと初等的関係があるので、初等的関係がある。 3．Σ，Σ’が、ともに向き付け不可ならば、Σには、オイラー数が等しく初等的関係のある 凡が存在する。また、Σ’にもオイラー数が等しく初等的関係のある1＞4が存在する。. 初等的関係のあるものは同相であるから、ΣとNgは同相であり、Σ’とNq，も同相であ る。よって1＞qと！Vg’は同相になる。もしq≠q’ならば、 E（Nの≠E（〈rのとなり、 Nq とNq’は、同相にならない。ゆえに、 q＝q’となり1＞α＝Nq’である。よって、Σ，Σ’は、. 同じ瑞と初等的関係があるので、初等的関係がある。 醒. 32.
(36) つぎの定理から多面体の位相同型による分類が得られる。 定理2．24Σ、Σ’は、ともにコンパクトで、向き付け可能な多面体とする。ΣとΣ’のオイ ラー数が等しいとき、ΣとΣ’は同相になり、また2つの多面体が同相ならば、その多面体の オイラー数は等しい。 証明 1．ΣとΣ’のオイラー数が等しいとする。定理2．20より、ΣとΣ’には初等的関係がある。 また定理2．10より、ΣとΣ’は同相になる。. 2．ΣとΣ’が、同相であるとする。定理2．23より、ΣとΣ’には初等的関係がある。また. 初等的関係があれば定理2．12より、ΣとΣ’はオイラー数が等しくなる。これで定 理が、証明された。. ■ 定理2．25Σ、Σ’は、ともにコンパクトで、向き付け不可能な多面体とする。ΣとΣ’のオイ ラー数が等しいとき、ΣとΣ’は同相になり、また2つの多面体が同相ならば、その多面体の オイラー数は等しい。. 証明. 向き付け可な多面体とまったく同じ方法で定理が証明される。. ■ 定理2．24、2．25から、すべての多面体は向き付け可能、不可能性とオイラー数でその 多面体と同相な多面体で分類できることがわかる。また次の定理が知られており多面体の 分類と閉曲面の位相同型による分類が等価であることを示している。. 定理2．265をコンパクトな閉曲面とするとき、この3と同相な多面体Σが存在する。 また、閉曲面のオイラー数については次のように定義する。. 定義2．27閉曲面θに対して5のオイラー数El（5）は、5と同相な多面体をΣとしたとき、 E（θ）・＝E（Σ）. で定める。このとき、もしΣと同相な多面体Σ’があっても、E（Σ）＝π（Σ’）となるので矛盾 なく定義できている。. 以上のことから、多面体ないしは閉曲面の位相同型による分類を表にまとめると、以 下のようになる。. オイラー数 2. 向き付け可 存在（球面）. 向き付け不可 なし. 1. なし. 存在（射影平面）. 0. 存在（トーラス）. 存在（クラインの壷）. 一1. なし. 存在. ●. ●. ●. ● o ●. ・ ・ ●. 向き付け可能な閉曲面のオイラー数は0以上の整数の種数pで2−2pと表わされ、向き 付け不可能な閉曲面のオイラー数は1以上の整数の種数qで2−qと表わされる。. 33.
Outline
関連したドキュメント
Robertson-Seymour の結果により，左図のように disjoint
変形を 2000 個準備する
特に、その応用として、 Donaldson不変量とSeiberg-Witten不変量が等しいというWittenの予想を代数
これはつまり十進法ではなく、一進法を用いて自然数を表記するということである。とは いえ数が大きくなると見にくくなるので、.. 0, 1,
管理画面へのログイン ID について 管理画面のログイン ID について、 希望の ID がある場合は備考欄にご記載下さい。アルファベット小文字、 数字お よび記号 「_ （アンダーライン）
解析の教科書にある Lagrange の未定乗数法の証明では,
の総体と言える。事例の客観的な情報とは、事例に関わる人の感性によって多様な色付けが行われ
だけでなく， 「家賃だけでなくいろいろな面 に気をつけることが大切」など「生活全体を 考えて住居を選ぶ」ということに気づいた生
