グラフ理論の用語
・点(vertex) または 節点(node)
図中の黒丸で示される点
・辺(edge)
図中の線
・グラフ(graph)
点と辺から成る図全体
・次数(degree)
点に接続する辺の数。例:点Pの次数は1。点Tの次数は3
・多重辺(multiple edges)
重複する辺。例:点Pと点Qを結ぶ辺
・ループ(loop)
同じ点を結ぶ辺。例:点Rと点Rを結ぶ辺
・単純グラフ(simple graph)
多重辺とループを含まないグラフ。例:Fig.1
・有向グラフ(directed graph)
辺に向きのあるグラフ
・歩道(walk)
ある点からある点への行き方。
・道(path)
始点と終点が異なり、どの点も高々一度しか通らない歩道。例: Fig.1 のP→Q→T→U
・閉路(cycle)
始点と終点が同一で、どの点も高々一度しか通らない歩道。例: Fig.1 のQ→R→S→T→Q
・オイラーグラフ(Eulerian graph)
一筆書きで全ての辺を通ることが可能なグラフ。ただし出発点に戻ってこれる。(辺に注目)
・ハミルトングラフ(Hamiltonian graph)
すべての点をちょうど1回通って出発点に戻ってこれるグラフ。(点に注目)
・連結グラフ(connected graph)
ひとかたまりのグラフ。例:Fig.1、Fig.2
・非連結グラフ(disconnected graph)
連結でないグラフ。ある点から別の点への道が存在しない。
・木(tree)
閉路が無い連結グラフ(どの2点間にも道が1本しか存在しない)
・平面的グラフ(planar graph)
辺の交差が無いように平面に描けるグラフ
・同形(isomorphic)
同じグラフであること
・点の隣接(adjacent vertices)
辺で結ばれた2点。例: Fig.1 の点Qと点Tは隣接。QとSは隣接でない。
・辺の隣接(adjacent edges)
同じ点に接続する辺。例: Fig.1 の辺QP, QR, QTは隣接。
・点と辺の接続(incident)
接続関係にある点と辺の関係
・孤立点(isolated vertex)
次数0の点
・端点(end vertex)
次数1の点
・部分グラフ(subgraph)
グラフの一部
・空グラフ(null graph)
点も辺もないグラフ
・正則グラフ(regular graph)
どの点も次数が同じグラフ。例:ピータスン・グラフは3次の正則グラフ
・完全グラフ(complete graph)
異なる2点がすべてつながっているグラフ。n個の点を持つ完全グラフKnの辺の数はn(n-1)/2
・閉路グラフ(cycle graph)
閉路を1つ持つグラフ(2次の正則グラフの1つ)。Cn。例:Fig.3 C5
・道グラフ(path graph)
道を1つ持つグラフ。Pn。例:Fig.3 P5
・車輪(wheel)
閉路グラフの中心に1つの頂点を配置したもの。Wn。例:Fig.3 W5
・プラトン・グラフ(Platonic graph)
正多面体の頂点と辺のグラフ
・二部グラフ(bipartite graph)
●と○を結ぶ辺しか存在しない、という条件で頂点を●と○の2種類に分けられるグラフ。例:Fig.4
・完全二部グラフ(complete bipartite graph)
異なる●と○がすべてつながっている二部グラフ。例:Fig.4
・補グラフ(complement graph)
同じ点集合を持ち、辺の有無が逆転しているグラフ
メモ1:(全ての点の次数の和)=(辺の数)×2
メモ2:奇数次の点の数は偶数
■ Regular Graph
http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html
- 作者: R.J.ウィルソン,Robin J. Wilson,西関隆夫,西関裕子
- 出版社/メーカー: 近代科学社
- 発売日: 2001/10/01
- メディア: 単行本
- 購入: 10人 クリック: 90回
- この商品を含むブログ (17件) を見る