グラフ理論の用語


点(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

グラフ理論入門

グラフ理論入門