離散数学とアルゴリズム | 天游ヶ丘数理学院

概要

本単元は、読者が有限な構造と、その構造を入力として受け取る手続きについて、数え上げと証明の方法を学部初年次の水準で習得することを目的とします。そのため本単元は、帰納法と再帰的な定義から始めて、和の法則と積の法則、包除原理、漸化式と母関数によって、有限な対象を数える方法を整えます。続いて集合の分割と写像、関係と順序、グラフと木という構造の言葉を定めます。そのうえで、整列、探索、最短路、全域木、位相ソート、マッチング、彩色を求める手続きが正しい答えを返すことを証明し、入力の大きさに応じて計算の手数がどれだけ増えるのかを評価します。

本単元が立てる問いは、二つに分かれます。第一は、条件を満たす対象がいくつあるのかという問いです。第二は、その対象を求める手続きが正しい答えを返し、何回の操作で終わるのかという問いです。対象が有限であるため、どちらの問いも個数についての等式または不等式として書き表すことができます。

最大フロー、Dilworth の定理、五色定理、確率的手法、動的計画法などは、後続の「離散数学 II」で扱います。本単元は、その後続に必要な定義、基本定理、正当性証明の型を整える役割を負います。

この単元のねらい

本単元は、読者が次に掲げる能力を習得することを目標とします。

帰納法を、ひとつ前の場合だけを仮定する形と、それより小さいすべての場合を仮定する形とに分けて用い、再帰的に定義された対象について、定義の構造に沿って証明することができます。
二つの有限集合のあいだに全単射を作って個数が等しいことを示し、順列、組合せ、重複組合せの個数を導くことができます。
包除原理を証明し、全射の個数や、与えられた数以下でその数と互いに素である数の個数を、符号が交互に変わる和として求めることができます。
鳩の巣原理を平均以上の値をとる対象の存在という形で用い、結論されるのが存在だけであることを述べることができます。
数え上げの問題から漸化式を立て、特性方程式または母関数によって一般項を求めることができます。
関係を反射律、対称律、推移律によって分類し、同値関係による類別と半順序集合の構造を記述することができます。
第二種 Stirling 数と Bell 数の漸化式を証明し、集合の分割と写像の十二相を数え分けることができます。
グラフ、木、連結性を定義し、オイラー路の存在条件のような基本的な定理を証明することができます。
手続きが正しい答えを返すことを、ループ不変量によって証明することができます。
手続きが必ず停止することを、繰り返しのたびに減少する非負整数によって証明することができます。
計算の手数を漸近記法によって評価し、分割統治から生じる漸化式を解くことができます。
比較だけで並べ替える手続きを決定木として表し、比較の回数の下界を導くことができます。
幅優先探索、深さ優先探索、ダイクストラの方法、クラスカルの方法が正しい答えを与えることを証明することができます。
閉路をもたない有向グラフの頂点を辺の向きと矛盾しないように一列に並べ、その操作が半順序を全順序へ広げることを述べることができます。
ホールの定理、貪欲な彩色による彩色数の上界、平面に描くことのできるグラフについてのオイラーの公式を証明することができます。

前提知識

本単元は、「集合と論理」で扱う集合の記法、命題と条件、背理法、数学的帰納法の論理構造を、証明の記述にそのまま用います。本単元の証明の多くは頂点の個数または辺の個数についての帰納法によって進み、手続きが正しい答えを返すという主張は、繰り返しのすべての回について成り立つ全称命題として述べられます。同単元の「発展・応用」で扱う量化子の入れ子と定義の展開を先に読んでいる読者は、手続きの正当性の証明を早く読み進めることができます。ただし同単元のこの区分は必修ではないため、本単元は必要な事項を改めて述べます。

本単元は、「ε-論法と基礎解析」および「線形代数 I」と並行して読むことができます。本単元は実数の連続性と極限を本論の証明に用いません。また、「線形代数 I」で扱う行列を本単元が用いるのは、グラフを隣接行列によって表すときだけです。本論の証明にベクトル空間の言葉を用いる記事は、本単元に一つもありません。読者は、この三つの単元をどの順序で読み始めてもかまいません。

本単元は、「場合の数と確率統計」を前提としません。順列、組合せ、包除原理を計算として扱った経験は、例を読むときの助けになります。しかし本単元は、数え上げの原理を全単射の構成として定義し直し、包除原理を有限個の有限集合について自前で証明します。したがって、本単元が包除原理を改めて証明することは、既習の内容の繰り返しではなく、前提を置かないことの帰結です。

本単元は、「数列と極限」で漸化式を解いた経験も前提としません。定数を係数とする線形の漸化式の解法と母関数は、本単元で改めて扱います。

この単元を貫く4つの方針

本単元の各記事は、次の4点を共通の方針とします。

数え上げの等式は、数えることによって示します。 二つの式が等しいことを式の変形によって示す代わりに、両辺が同じ対象を数えていることを示すか、両辺が数えている二つの集合のあいだに全単射を作ります。この方法は、その等式が何についての等式であるかを同時に示します。
対象を有限な構造として定め直します。 与えられた条件を、頂点と辺の組、関係、順序として書き直します。書き直した後で何を求めるのかを述べ直し、書き直す前の条件と同値であるかどうかを確かめます。
正しい答えを返すこと、必ず停止すること、計算の手数の三つを分けて示します。 正しい答えを返すことはループ不変量によって、必ず停止することは繰り返しのたびに減少する非負整数によって示し、計算の手数は漸近記法によって評価します。三つは別々の主張であり、一つを示しても残りの二つは従いません。
存在の証明と構成手続きを区別します。 数え上げや平均から対象の存在が従っても、その対象を出力する手続きが得られるとは限りません。構成、正当性、停止性を別々に確認します。

学習の順序と各記事の内容

本単元の記事はすべて必修です。前の記事で定めた言葉と証明した定理を後の記事が用いるので、読者は次の順に読みます。

必修

読者が、有限な対象を数える方法と構造を記述する言葉を整え、そのうえで手続きの正しさと計算の手数を証明することができるようになる段階です。各記事が扱う内容と、その順序の理由は、次のとおりです。

帰納法と再帰的な定義 — 自然数についての帰納法を、ひとつ前の場合だけを仮定する形と、それより小さいすべての場合を仮定する形とに分けて述べ、二つが同値であることを示します。空でない部分集合が、その部分集合のなかに真に小さい元をもたない元を含むという性質を整礎性として定めます。文字列や木を再帰的に定義し、その定義の構造に沿って証明する手順を扱います。高等学校で扱う数学的帰納法との違いは、この整礎性にあります。整礎性を定めることによって、自然数の上に並んでいない対象についても帰納法を用いることができます。本単元の証明はほとんどが帰納法によって進むので、読者はこの記事から読み始めます。
数え上げの原理と全単射による数え上げ — 有限集合、直積、写像、単射、全射、全単射をここで定義し、和の法則と積の法則を要素の個数についての等式として述べます。二つの有限集合のあいだに全単射を作って個数が等しいことを示す方法から、順列、組合せ、重複組合せの個数を導きます。ここで定める写像と直積の言葉は、以降のすべての記事が用います。
包除原理の応用と鳩の巣原理の一般形 — 有限個の有限集合に対する包除原理を帰納法によって証明します。この原理を用いて、全射の個数と、与えられた数以下でその数と互いに素である数の個数を、いずれも符号が交互に変わる和として求めます。包除原理の証明は集合の個数についての帰納法によって進むので、「帰納法と再帰的な定義」で述べた帰納法と、「数え上げの原理と全単射による数え上げ」で述べた和の法則を用います。あわせて、鳩の巣原理を平均以上の値をとる対象の存在という形まで一般化し、対象の存在だけが結論されることを確かめます。この形の議論を、後続の「離散数学 II」にある「確率的手法」が期待値によって広げます。
漸化式と母関数 — 数え上げの問題から漸化式を立て、定数を係数とする線形の漸化式を特性方程式によって解きます。母関数を形式的なべき級数として定義し、数列の項ごとの和が母関数の和に、畳み込みが積に対応することを示して、部分分数へ分解して一般項を取り出します。係数だけを比べる計算では収束を論じません。何を数えているのかが定まってはじめて漸化式を立てることができるので、読者は数え上げの原理を定める記事を読んだ後に、この記事を読みます。
関係・同値関係・順序集合 — 直積の部分集合として関係を定義し、反射律、対称律、推移律のどれを満たすかで分類します。直積は「数え上げの原理と全単射による数え上げ」で定めています。同値関係が集合を類別することを示し、半順序集合と Hasse 図を定め、極大元と最大元が一致しない例を挙げます。二元の上限と下限から束を定義します。ここで定める半順序は、「有向グラフ・位相ソート・強連結成分」で全順序へ広げる操作の対象となり、「離散数学 II」の Dilworth の定理が用います。
分割と写像の数え上げ — 第二種 Stirling 数と Bell 数の漸化式を証明します。さらに、球と箱を区別するかどうか、および写像へ単射・全射の条件を課すかどうかによる十二相を整理します。「数え上げの原理」の和・積・組合せと、「関係・同値関係・順序集合」の類別をここで結びます。
グラフ・木・連結性・オイラー路 — グラフ、次数、道、閉路、連結性を定義し、次数の総和が辺の個数の 2 倍であることを証明します。木を連結で閉路をもたないグラフとして定め、木であることと同値な条件を並べます。連結なグラフについては、オイラー閉路が存在するための必要十分条件が、すべての頂点の次数が偶数であることを示します。あわせて、オイラー路が存在するための必要十分条件が、奇数次数の頂点が 0 個または 2 個であることを示します。証明は辺の個数についての帰納法によって進みます。以降でグラフを扱う記事は、すべてこの記事の定義を用います。
アルゴリズムの正当性と計算量 — 手続きが正しい答えを返すことをループ不変量によって、必ず停止することを繰り返しのたびに減少する非負整数によって証明します。漸近記法を定め、基本的な手続きの計算の手数を評価して、分割統治から生じる漸化式を解きます。多項式時間で解くことができる問題と、解を与えられれば多項式時間で検証することができる問題が一致するかどうかは、未解決です。探索や最短路が正しい答えを与えることの証明は、ループ不変量と漸近記法を用いて書きます。そのため読者は、探索を扱う記事より前にこの記事を読みます。
整列と比較回数の下界 — 併合による整列と分割による整列の手順を定め、正しく並ぶことと計算の手数を、分割統治から生じる漸化式によって示します。この漸化式の解き方は、「アルゴリズムの正当性と計算量」で扱っています。さらに、比較だけで並べ替える手続きを決定木として表し、葉の個数が要素の並べ方の総数以上であることから、比較の回数の下界を導きます。この議論は、一つの手続きの手数を数える議論ではなく、どの手続きにも共通する限界を示す議論です。読者は、ここで計算量の下界を証明する最初の経験をします。
探索・最短路・全域木 — 幅優先探索と深さ優先探索の手順を定め、頂点を訪問する順序と探索によって得られる木の性質を確かめます。重みを考えないグラフでは幅優先探索が、辺の重みが非負ならダイクストラの方法が最短路を与えること、および重みの小さい辺から選ぶクラスカルの方法が最小全域木を与えることを証明します。いずれの証明も、ループ不変量を選んで繰り返しのたびに保たれることを示すという形をとります。二部グラフであるかどうかを探索の途中で判定する方法も扱い、この判定は「マッチング・彩色・平面グラフ」で用います。
有向グラフ・位相ソート・強連結成分 — 辺に向きのあるグラフを定義し、閉路をもたない有向グラフの頂点を、辺の向きと矛盾しないように一列に並べることができることを証明します。この並べ方は、「関係・同値関係・順序集合」で定めた半順序を全順序へ広げる操作にあたります。すなわち、比較することができない二つの要素に対しても、もとの順序と矛盾しない前後を定めます。あわせて、深さ優先探索によって強連結成分へ分ける手順と、その手順が正しい答えを返すことを扱います。
マッチング・彩色・平面グラフ — マッチングを定義し、二部グラフの一方の頂点集合をすべて覆うマッチングが存在する条件をホールの定理として証明します。頂点彩色と彩色数を定め、貪欲な彩色から彩色数が最大次数に 1 を加えた値以下であることを導きます。連結で平面に描くことのできるグラフについてオイラーの公式を証明し、四色定理は主張だけを述べます。五色定理、四色定理の放電法、最大フロー最小カット定理は「離散数学 II」へ送ります。

学習到達点の確認方法

本単元は、数え上げの計算と、構造についての証明と、手続きについての証明の三つを確かめます。確かめる内容は、次のとおりです。

数え上げでは、読者が重複と漏れなく数えることができるかを確かめます。あわせて、読者が用いた原理と、数えている対象が何であるかを述べることができるかを確かめます。
構造についての主張では、読者が証明を書くことができるかを確かめます。帰納法を用いる場合には、読者が何についての帰納法であるかと、帰納法の仮定をどこで用いたかを明示することができるかを確かめます。
手続きでは、読者が三つの主張を分けて論じているかどうかを確かめます。三つの主張とは、手続きが正しい答えを返すこと、手続きが必ず停止すること、および計算の手数についての評価です。あわせて、読者がループ不変量と減少する量を自分で選ぶことができるかを確かめます。
計算の手数の下界では、読者が一つの手続きについての評価と、どの手続きにも共通する限界の主張とを区別することができるかを確かめます。

本単元は、演習に、答えが一意に定まる数え上げの問題と、証明を書く問題、および手続きが正しい答えを返すことを論じる問題を用います。証明を伴う解答については、本単元は、用いた原理、帰納法の構造、ループ不変量の選び方を確かめます。手続きを具体的な入力へ適用してみることは、手順を理解する手段としては有用ですが、正しい答えを返すことの証明とは別のものです。

前後の単元との関係

集合と論理 — 同単元は、集合の記法、命題と条件、量化子、数学的帰納法の論理構造を扱います。本単元は、集合の記法と帰納法を、グラフについての定理と、手続きが正しい答えを返すことの証明に用います。
ε-論法と基礎解析 — 同単元は、極限と連続性を量化子による定義から扱います。本単元と同単元は、どちらも定義だけを根拠として証明を書く段階にあたりますが、扱う対象が離散的であるか連続的であるかで分かれ、互いを前提としません。
線形代数 I — 同単元は、行列の演算、ベクトル空間、階数と次元を扱います。本単元は、行列をグラフの隣接行列として、および線形計画の双対定理との対応を述べるときに用います。
場合の数と確率統計 — 同単元は、順列、組合せ、包除原理、期待値の線形性を計算として扱います。本単元は、数え上げの原理を全単射の構成として定義し直し、包除原理を有限個の有限集合について証明します。
数列と極限 — 同単元は、漸化式の解法と数列の極限を扱います。本単元は、数え上げの問題から漸化式を立て、母関数によって一般項を求めます。
初等整数論 — 同単元は、割り切れることと互いに素であることを扱います。本単元は、与えられた数以下でその数と互いに素である数の個数を、包除原理によって求めます。
雑多な話題 — 同単元は、鳩の巣原理や二通りに数える論じ方を、分野をまたぐ問題について扱います。本単元は、同じ論じ方を定理の形で述べ、証明します。
計算理論 — 同単元は、何を計算することができるのかを Turing 機械と形式言語によって定め、時間計算量と空間計算量を扱います。同単元は、本単元が立てる多項式時間についての問いに、 $\mathrm{P}$ と $\mathrm{NP}$ の関係として厳密な形を与えます。
離散数学 II — 同単元は、本単元の関係・順序・グラフ・アルゴリズムを前提に、Dilworth の定理、Möbius 反転、 Pólya の数え上げ、マトロイド、最大フロー、動的計画法、五色定理、確率的手法へ進みます。
組合せ論・グラフ理論 — 同単元は、Ramsey 理論、極値集合論、彩色とマッチングの構造定理、平面性、確率論的手法を「離散数学 II」より先の段階で扱います。
凸最適化 — 同単元は、線形計画の双対とミニマックス定理を、一般の凸計画の双対性の一部として扱います。「離散数学 II」の最大フロー最小カット定理は、その組合せ的な特別な場合にあたります。
群論入門 — 同単元は、群とその作用を一般の形で扱い、Burnside の補題による対称性を除いた数え上げを供給します。「離散数学 II」の Pólya の数え上げはこれを前提とします。
確率論入門 — 同単元は、測度論の上に確率空間と確率変数を置きます。「離散数学 II」の確率的手法は、期待値とその線形性を同単元から受け取ります。

大学課程における位置づけ

本単元は、日本の大学において「離散数学」「離散数学とアルゴリズム」「グラフ理論」などの名称で、理学部の数学科および情報系の学科に開講される科目に対応します。英語圏では Discrete Mathematics と呼ばれ、数え上げ、グラフ、アルゴリズム、論理を一つの科目にまとめて扱うことが多くあります。アルゴリズムを扱う部分は、Algorithms または Data Structures and Algorithms として別の科目に分かれることもあります。

§D2離散数学とアルゴリズム全12項目

概要