グラフ理論

グラフ理論(Graph theory)とは、グラフの持つ様々な性質を解明し、日常の様々な場面で利用することを目的とする数学分野の1つである。
グラフ理論におけるグラフ (Graph)とは、頂点(node)と辺(edge)により構成された図形のことである。グラフは主に、有向グラフ (directed graph)と無向グラフ (undirected graph)の2つに分類される。有向グラフとは、頂点と向きを持つ辺(矢印)により構成されたグラフであり、無向グラフとは、頂点と辺により構成されたグラフである。有向グラフの辺を有向辺、無向グラフの辺を無向辺という。また、ある2頂点が辺で結ばれている場合、その2頂点は隣接するという。この教科書では、特に利用分野の多い無向グラフについて説明する。そのため、この教科書では、無向グラフを単にグラフと記述することとする。
グラフは頂点の集合と辺の集合の2つの順序対で構成される。グラフ G {\displaystyle G} を構成する頂点の集合を V {\displaystyle V} 、辺の集合を E {\displaystyle E} とし、 G = ( V , E ) {\displaystyle G=(V,E)} と表記する。頂点を u {\displaystyle u} や v {\displaystyle v} で表すことが多く、頂点 u , v {\displaystyle u,v} を結ぶ辺を { u , v } {\displaystyle \{u,v\}} または、 u v {\displaystyle uv} と表す。しかし、紛らわしい表記であるため、この教科書では、 { u , v } {\displaystyle \{u,v\}} と表記することとする。ただし、 { u , v } {\displaystyle \{u,v\}} と { v , u } {\displaystyle \{v,u\}} はどちらでも構わない。
「グラフの定義」で説明したとおり、グラフは頂点と辺により構成される。とは言うものの、実際にどのように作図すればいいのかわからないだろう。この節では、グラフの作図について説明する。まず、頂点を丸で表し、辺を直線または、曲線で表す。そのとき、マルの大きさや直線の長さ、曲線の曲がり具合はグラフの本質には関係ないので、厳密に作図する必要はない。以下にグラフの作図例を紹介する。
頂点の周囲に u {\displaystyle u} や v {\displaystyle v} などと記すと、グラフを表記するとき、便利である。頂点の中にラベル(重み)を記す場合があるが、まず、グラフの基本から説明する必要があるため、この節で紹介するのはやめておく。
(1) 以下のグラフ G 1 {\displaystyle G_{1}} を G 1 = ( V 1 , E 1 ) {\displaystyle G_{1}=(V_{1},E_{1})} の形式で表せ。
V 1 = { v 1 , v 2 , v 3 , v 4 } {\displaystyle V_{1}=\{v_{1},v_{2},v_{3},v_{4}\}} , E 1 = { { v 1 , v 3 } , { v 1 , v 4 } , { v 2 , v 3 } , { v 2 , v 4 } } {\displaystyle E_{1}=\{\{v_{1},v_{3}\},\{v_{1},v_{4}\},\{v_{2},v_{3}\},\{v_{2},v_{4}\}\}} であるから、 G 1 = ( { v 1 , v 2 , v 3 , v 4 } , { { v 1 , v 3 } , { v 1 , v 4 } , { v 2 , v 3 } , { v 2 , v 4 } } ) {\displaystyle G_{1}=(\{v_{1},v_{2},v_{3},v_{4}\},\{\{v_{1},v_{3}\},\{v_{1},v_{4}\},\{v_{2},v_{3}\},\{v_{2},v_{4}\}\})} (2) グラフ G 2 = ( { v 1 , v 2 , v 3 , v 4 } , { { v 1 , v 2 } , { v 1 , v 3 } , { v 1 , v 4 } , { v 2 , v 3 } , { v 3 , v 4 } } ) {\displaystyle G_{2}=(\{v_{1},v_{2},v_{3},v_{4}\},\{\{v_{1},v_{2}\},\{v_{1},v_{3}\},\{v_{1},v_{4}\},\{v_{2},v_{3}\},\{v_{3},v_{4}\}\})} を作図せよ。
(1) 以下のグラフ G 3 {\displaystyle G_{3}} を G 3 = ( V 3 , E 3 ) {\displaystyle G_{3}=(V_{3},E_{3})} の形式で表せ。
(2) グラフ G 4 = ( { v 1 , v 2 , v 3 , v 4 , v 5 } , { { v 1 , v 3 } , { v 2 , v 3 } , { v 2 , v 5 } , { v 3 , v 4 } , { v 3 , v 5 } , { v 4 , v 5 } } ) {\displaystyle G_{4}=(\{v_{1},v_{2},v_{3},v_{4},v_{5}\},\{\{v_{1},v_{3}\},\{v_{2},v_{3}\},\{v_{2},v_{5}\},\{v_{3},v_{4}\},\{v_{3},v_{5}\},\{v_{4},v_{5}\}\})} を作図せよ。
頂点の数を位数(order)、辺の数をサイズという。
グラフにおける次数(degree)とは、ある頂点に結ばれている辺の数である。
あるグラフにおいて、 { v 0 , v 1 } , { v 1 , v 2 } , ⋯ , { v n − 1 , v n } {\displaystyle \{v_{0},v_{1}\},\{v_{1},v_{2}\},\cdots ,\{v_{n-1},v_{n}\}} がすべて辺であるとき、それぞれの辺の集合を頂点 v 0 {\displaystyle v_{0}} と頂点 v n {\displaystyle v_{n}} を結ぶ道(path)と言う。
ある2つのグラフが同型(isomorphism)であるということは、それぞれのグラフを構成する頂点と辺の結びつきが同じであるということである。
連結(connected)なグラフとは、任意の2頂点間に道が存在するグラフのことである。
完全グラフ(complete graph)とは、すべての頂点同士が辺で結ばれているグラフのことである。頂点数 n {\displaystyle n} の完全グラフを K n {\displaystyle K_{n}} と表す。
オイラーグラフ: オイラー閉トレイルが存在するグラフをオイラーグラフと呼ぶ。
オイラー閉トレイル: グラフのすべての辺とすべての点を含む閉トレイルをオイラー閉トレイルと呼ぶ。
オイラートレイル: グラフのすべての辺とすべての点を含むトレイルをオイラートレイルと呼ぶ。
ハミルトングラフ: ハミルトン閉路を含むグラフをハミルトングラフと呼ぶ。
ハミルトン閉路: グラフのすべての頂点を含む閉路をハミルトン閉路と呼ぶ。
根(root)という頂点を持ち、
問題の解答を記載しておく。
(1) G 3 = ( { v 1 , v 2 , v 3 , v 4 , v 5 } , { { v 1 , v 3 } , { v 1 , v 5 } , { v 2 , v 3 } , { v 2 , v 4 } , { v 2 , v 5 } , { v 3 , v 5 } } ) {\displaystyle G_{3}=(\{v_{1},v_{2},v_{3},v_{4},v_{5}\},\{\{v_{1},v_{3}\},\{v_{1},v_{5}\},\{v_{2},v_{3}\},\{v_{2},v_{4}\},\{v_{2},v_{5}\},\{v_{3},v_{5}\}\})} (2)
以下のURLにアクセスするとファイルをダウンロードすることができる。もちろん、自由に利用して構わない。 https://skydrive.live.com/redir.aspx?cid=322baa2fe886dd76&resid=322BAA2FE886DD76!230&parid=root (リンク切れ) この教科書に利用されているファイルWikibooks graph theory*.pngはgraph*.svgやgraph*.png,graph*.epsの3種類の形式で保存されている。そのため、様々な用途に利用できる。フォルダとして一括でダウンロードすることも可能である。