グラフ理論

数学 > グラフ理論

　グラフ理論（Graph theory）とは、グラフの持つ様々な性質を解明し、日常の様々な場面で利用することを目的とする数学分野の1つである。

グラフとは

　グラフ理論におけるグラフ （Graph）とは、頂点(node)と辺(edge)により構成された図形のことである。グラフは主に、有向グラフ （directed graph）と無向グラフ （undirected graph）の2つに分類される。有向グラフとは、頂点と向きを持つ辺（矢印）により構成されたグラフであり、無向グラフとは、頂点と辺により構成されたグラフである。有向グラフの辺を有向辺、無向グラフの辺を無向辺という。また、ある2頂点が辺で結ばれている場合、その2頂点は隣接するという。この教科書では、特に利用分野の多い無向グラフについて説明する。そのため、この教科書では、無向グラフを単にグラフと記述することとする。

グラフの表記

　グラフは頂点の集合と辺の集合の2つの順序対で構成される。グラフ $G$ を構成する頂点の集合を $V$ 、辺の集合を $E$ とし、 $G=(V,E)$ と表記する。頂点を $u$ や $v$ で表すことが多く、頂点 $u,v$ を結ぶ辺を $\{u,v\}$ または、 $uv$ と表す。しかし、紛らわしい表記であるため、この教科書では、 $\{u,v\}$ と表記することとする。ただし、 $\{u,v\}$ と $\{v,u\}$ はどちらでも構わない。

グラフの作図

　「グラフの定義」で説明したとおり、グラフは頂点と辺により構成される。とは言うものの、実際にどのように作図すればいいのかわからないだろう。この節では、グラフの作図について説明する。まず、頂点を丸で表し、辺を直線または、曲線で表す。そのとき、マルの大きさや直線の長さ、曲線の曲がり具合はグラフの本質には関係ないので、厳密に作図する必要はない。以下にグラフの作図例を紹介する。

作図例

頂点の周囲に $u$ や $v$ などと記すと、グラフを表記するとき、便利である。頂点の中にラベル（重み）を記す場合があるが、まず、グラフの基本から説明する必要があるため、この節で紹介するのはやめておく。

例題1

(1)　以下のグラフ $G_{1}$ を $G_{1}=(V_{1},E_{1})$ の形式で表せ。

$G_{1}$

$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}\}\}$ であるから、
$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}\}\})$ を作図せよ。

$G_{2}$

問題1

(1)　以下のグラフ $G_{3}$ を $G_{3}=(V_{3},E_{3})$ の形式で表せ。

$G_{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}\}\})$ を作図せよ。

位数とサイズ

　頂点の数を位数（order）、辺の数をサイズという。

次数

　グラフにおける次数（degree）とは、ある頂点に結ばれている辺の数である。

道と閉路

　あるグラフにおいて、 $\{v_{0},v_{1}\},\{v_{1},v_{2}\},\cdots ,\{v_{n-1},v_{n}\}$ がすべて辺であるとき、それぞれの辺の集合を頂点 $v_{0}$ と頂点 $v_{n}$ を結ぶ道(path)と言う。

同型のグラフ

　ある2つのグラフが同型（isomorphism）であるということは、それぞれのグラフを構成する頂点と辺の結びつきが同じであるということである。

連結なグラフ

　連結(connected)なグラフとは、任意の2頂点間に道が存在するグラフのことである。

完全グラフ

　完全グラフ（complete graph）とは、すべての頂点同士が辺で結ばれているグラフのことである。頂点数 $n$ の完全グラフを $K_{n}$ と表す。

特殊なグラフとその構成

オイラーグラフ：　オイラー閉トレイルが存在するグラフをオイラーグラフと呼ぶ。

オイラー閉トレイル：　グラフのすべての辺とすべての点を含む閉トレイルをオイラー閉トレイルと呼ぶ。

オイラートレイル：　グラフのすべての辺とすべての点を含むトレイルをオイラートレイルと呼ぶ。

ハミルトングラフ：　ハミルトン閉路を含むグラフをハミルトングラフと呼ぶ。

ハミルトン閉路：　グラフのすべての頂点を含む閉路をハミルトン閉路と呼ぶ。

木

根（root）という頂点を持ち、

順序木

問題の解答

　問題の解答を記載しておく。

問題1

(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}\}\})$
(2)

$G_{4}$

ファイルのダウンロード

以下の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種類の形式で保存されている。そのため、様々な用途に利用できる。フォルダとして一括でダウンロードすることも可能である。