グラフ - HifeLacks - serenista@wiki

■グラフ覚書(別ページから移動。後で削除)

• 頂点(vertex)。ノードとか呼ばれることも
• 辺(edge)。
• グラフGの
  • 頂点の集合: V(G)
  • 辺の集合: E(G)
• 次数: 頂点に接続する辺の数。d(v)
  • すべてのvにおいてd(v)=kの時、「k-正則」と言う
  • 入次数: 頂点に入ってくる辺の数
  • 出次数: 頂点から出る辺の数

グラフの定義

• 単純グラフ：V(G)とE(G)からなるグラフ(p.10)
  • V(G): 非空な点集合(vertex set)
  • E(G): 辺集合(edge set)
  • 辺はV(G)の異なる2点の非順序対
    • ループは含まない
• 一般グラフ(general graph): ループを許すグラフ(p.11)
  • ループ: 同じ点を結ぶ辺
• グラフの定義(p.11)
  • V(G): 点からなる非空の有限集合(点集合)
  • E(G): V(G)の元の非順序対からなる有限の族(辺族)
    • 多重辺アリ
• 同形(isomorphic)(p.11)
  • ふたつのグラフG1とG2の点の間に1体1対応がある
  • G1の任意の2点を結ぶ辺がG2の対応する2点を結ぶ辺数に等しい
  • (点の隣接性が保存されること)
• 連結性(p.12)
  • グラフの和
    • V(G1)とV(G2)が素である時、G1∪G2は、V(G1)∪V(G2)と、E(G1)∪E(G2)を持つグラフとなる
  • ふたつのグラフの和として表せないグラフは「連結されている(connected)」
  • 任意の非連結グラフは連結グラフの和として表せる。各連結グラフは「成分(component)」という
• 隣接(p.14)
  • 2点v, wを結ぶ辺vwがある時、vとwは「隣接」している(adjacent)
  • その時vとwは辺vwに「接続」している(incident)
  • 2本の辺がひとつの点を共有している時、2辺は「隣接」している
• 次数(degree)(p.14)
  • deg(v): 点vに接続している辺の本数
    • ループは2本と数える
  • 孤立点(isolated vertex): 次数0の点
  • 端点(end-vertex): 次数1の点
  • 次数列(degree sequence): 次数を昇順に、重複を含めて列挙したリスト
  • 任意のグラフのすべての点の次数の合計は偶数
    • 握手補題とも(handshaking lemma)
• 部分グラフ(subgraph)(p.15)
  • すべての点はV(G)に属し、すべての辺はE(G)に属するグラフ
  • eがGの辺である時、Gからeを除去して得られるグラフをG-eと表す
  • Gの辺の任意の集合FをGから除去して得られるグラフをG-Fと表す
  • 点に関しては、G-v, G-Sと表す
  • 縮約。G\e。辺eを除去し、その端点vとwを1点にしてできるグラフ
• 隣接行列(adjacency matrix)(p.17)
  • 点iとjを結ぶ辺の本数をij要素とするn×nの行列
• 接続行列(incidence matrix)(p.17)
  • 点iが辺jに接続している時1, そうでない時0をij要素とするn×m行列

さまざまなグラフ

• 空グラフ(null graph)(p.21)
  • 辺集合が空であるグラフ
  • n個の点の空グラフをNnと表す(nは下つき)
• 完全グラフ(complete graph)(p.22)
  • 相異なる2点がすべて隣接しているグラフ
  • n個の点の完全グラフをKnと表す(同上)
  • Knにはちょうとn(n-1)/2本の辺がある
• 閉路グラフ、道グラフ、車輪(p.22)
  • 次数2の正則連結グラフを閉路グラフ(cycle graph)といい、Cnと表す
  • Cnからひとつの辺を除去して得られるグラフを道グラフ(path graph)といい、Pnと表す
  • C(n-1)にひとつの新しい点vを加え、vと他のすべての点を結んで得られるグラフを車輪(wheel)といい、Wnと表す。
• 正則グラフ(regular graph)(p.23)
  • どの点の次数も同じであるグラフ
  • 次数をrとすると、次数rの正則グラフ、またはr-正則グラフと呼ぶ
  • 空グラフNnは次数0の正則グラフである
  • 閉路Cnは次数2の正則グラフである
  • 完全グラフKnは次数n-1の正則グラフである
  • 正則グラフの例
    • ピータスン・グラフ: 次数3の有名な例。星形の外に五角形
    • プラトン・グラフ: 性多面体の頂点と辺からできるグラフ
• 二部グラフ(bipartite graph)(p.24)
  • Gの点集合をふたつの素な集合AとBに分割し、Gのすべての辺がAの点とBの点を結ぶようにしたグラフ
• 単純グラフの補グラフ(p.25)

連結性

• 歩道(walk)(p.35)
  • 隣接する辺の有限列(v0v1, v1v2,...vm-1vm)
  • v0を歩道の始点(initial vertex)
  • vmを歩道の終点(final vertex)
  • 歩道の長さ: 歩道中の辺の本数
• 小道(trail)(p.35)
  • すべての辺が異なる歩道
• 道(path)(p.35)
  • すべての点が異なる小道
• 閉路(cycle)(p.35)
  • v0=vmの時、道ないし小道は閉じている
  • 閉路: 少なくとも1本の辺を持つ閉じた道
  • ループは閉路
  • 2本の多重辺も閉路
• 連結(p.36)
  • グラフの各2点の間に道がある時、かつその時に限り、グラフは連結であるという
  • グラフGの閉路がすべて偶数長である時、かつその時に限り、Gは二部グラフである
• 非連結化集合(disconnetcing set)(p.38)
  • それを除去するとGが非連結になるような辺の集合。それを除去すると成分の数が増える辺の集合。
  • カットセット(cutset)(p.38): どんな真部分集合も非連結化集合でないような非連結化集合
  • 橋(bridge)(p.36): その辺ひとつでカットセットとなるような辺
• 辺連結度(edge-connectivity)(p.38)
  • 連結グラフGの最小のカットセットの大きさ。λ(G)
  • Gを非連結にするために除去すべき辺の最小数
  • λ(G)≧kの時「k-辺連結」という
• 分離集合(separating set)(p.39)
  • それを除去するとGが非連結になるような点の集合
  • カット点(cut-vertex)(p.39): その点ひとつで分離集合となるような点
• (点)連結度(p.39)
  • Gの最小の分離集合の大きさ。κ(G)
  • Gを非連結にするために除去すべき点の最小数
  • κ(G)≧kの時「k-連結」という
  • 任意の連結グラフGに対してκ(G)≦λ(G)
• オイラー・グラフ(p.42)
  • オイラー・グラフ: 連結グラフGのすべての辺を含む閉じた小道(オイラー小道)があるグラフ
  • 半オイラー・グラフ: オイラー・グラフではないが、すべての辺を含む小道があるグラフ
  • 連結グラフGがオイラー・グラフであるための必要十分条件は、Gの点の次数がすべて偶数であることである
  • 連結グラフが半オイラー・グラフであるための必要十分条件は、次数が奇数の点が2個だけあることである。
• ハミルトン・グラフ(p.48)
  • ハミルトン・グラフ: すべての点をちょうど一度だけ通る閉じた小道(ハミルトン閉路)があるグラフ
  • 半ハミルトン・グラフ: すべての点を通る道があるグラフ