組み合わせグラフモデルとして利用する多くのグラフは有限で連結な組み合わせグラフです。本記事は、連結、グラフ理論、ループ辺、多重辺、組み合わせグラフについて解説する記事です。本記事を読むにあたり、「グラフとは何か?」「路」について知っている必要があるため、以下の記事も合わせてご覧ください。連結は本シリーズの最初にサラッと述べた通り、シンプルなコンセプトです。一言で述べればグラフに対して、どの頂点からどの頂点へも辺をたどって移動できるときに、そのグラフは連結であるという。このコンセプトは前回解説した路でもって記述されます。ちなみに、路とは以下でした。満たすとき、\(c\)を長さ(length)が\(n\)の路(path)という。\(c\)の長さを、\(|c|\)により表し、\(o(e_1)\)を\(c\)の始点、\(t(e_n)\)を終点といい、それぞれ\(o(c)\)、\(t(c)\)で表す。その2を御覧ください。連結って何ですか?では、「連結とは何か?」ということについて答えようと思います。V\)に対して、\(o(c)=x\)、\(t(c)=y\)となる路\(c\)が存在するとき、\(X\)は連結(connected)という。グラフの連結とはまさに、「どんな2点も”繋がっている”」という状態で、離れ小島が無い、ということです。連結を「どんな2点も”繋がっている”こと」と表現すると、「じゃあ、連結でないグラフは点だけ離れ小島のようになっているグラフということだな?」となるかもしれませんが、無向グラフについてはそれでOKです。有向グラフについてはそうもいきません(後の記事で解説します)。有向グラフでは、下図のように離れ小島がなくとも有向辺の向きによっては連結でない場合が考えられます。連結のちょっとした性質ここで、連結のちょっとした性質を紹介します。V\)が次の性質を満たすとする。故に\(A=V\)である。e_1,\dots,e_n\right)\)が存在します。\(t(c)=y\)ですので、\(t(e_n)=y\)と書き直すことが出来ます。A\)が示されれば、証明完了です。A\)であることを数学的帰納法で証明します。