グラフ理論
グラフ理論(Graph theory)とは、グラフの持つ様々な性質を解明し、日常の様々な場面で利用することを目的とする数学分野の1つである。
グラフとは
編集グラフ理論におけるグラフ (Graph)とは、頂点(node)と辺(edge)により構成された図形のことである。グラフは主に、有向グラフ (directed graph)と無向グラフ (undirected graph)の2つに分類される。有向グラフとは、頂点と向きを持つ辺(矢印)により構成されたグラフであり、無向グラフとは、頂点と辺により構成されたグラフである。有向グラフの辺を有向辺、無向グラフの辺を無向辺という。また、ある2頂点が辺で結ばれている場合、その2頂点は隣接するという。この教科書では、特に利用分野の多い無向グラフについて説明する。そのため、この教科書では、無向グラフを単にグラフと記述することとする。
グラフの表記
編集グラフは頂点の集合と辺の集合の2つの順序対で構成される。グラフ を構成する頂点の集合を 、辺の集合を とし、 と表記する。頂点を や で表すことが多く、頂点 を結ぶ辺を または、 と表す。しかし、紛らわしい表記であるため、この教科書では、 と表記することとする。ただし、 と はどちらでも構わない。
グラフの作図
編集「グラフの定義」で説明したとおり、グラフは頂点と辺により構成される。とは言うものの、実際にどのように作図すればいいのかわからないだろう。この節では、グラフの作図について説明する。まず、頂点を丸で表し、辺を直線または、曲線で表す。そのとき、マルの大きさや直線の長さ、曲線の曲がり具合はグラフの本質には関係ないので、厳密に作図する必要はない。以下にグラフの作図例を紹介する。
-
作図例
頂点の周囲に や などと記すと、グラフを表記するとき、便利である。頂点の中にラベル(重み)を記す場合があるが、まず、グラフの基本から説明する必要があるため、この節で紹介するのはやめておく。
例題1
編集(1) 以下のグラフ を の形式で表せ。
, であるから、
(2) グラフ を作図せよ。
問題1
編集(1) 以下のグラフ を の形式で表せ。
(2) グラフ を作図せよ。
位数とサイズ
編集頂点の数を位数(order)、辺の数をサイズという。
次数
編集グラフにおける次数(degree)とは、ある頂点に結ばれている辺の数である。
道と閉路
編集あるグラフにおいて、 がすべて辺であるとき、それぞれの辺の集合を頂点 と頂点 を結ぶ道(path)と言う。
同型のグラフ
編集ある2つのグラフが同型(isomorphism)であるということは、それぞれのグラフを構成する頂点と辺の結びつきが同じであるということである。
連結なグラフ
編集連結(connected)なグラフとは、任意の2頂点間に道が存在するグラフのことである。
完全グラフ
編集完全グラフ(complete graph)とは、すべての頂点同士が辺で結ばれているグラフのことである。頂点数 の完全グラフを と表す。
特殊なグラフとその構成
編集オイラーグラフ: オイラー閉トレイルが存在するグラフをオイラーグラフと呼ぶ。
オイラー閉トレイル: グラフのすべての辺とすべての点を含む閉トレイルをオイラー閉トレイルと呼ぶ。
オイラートレイル: グラフのすべての辺とすべての点を含むトレイルをオイラートレイルと呼ぶ。
ハミルトングラフ: ハミルトン閉路を含むグラフをハミルトングラフと呼ぶ。
ハミルトン閉路: グラフのすべての頂点を含む閉路をハミルトン閉路と呼ぶ。
木
編集根(root)という頂点を持ち、
順序木
編集問題の解答
編集問題の解答を記載しておく。
問題1
編集(1)
(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種類の形式で保存されている。そのため、様々な用途に利用できる。フォルダとして一括でダウンロードすることも可能である。