グラフ理論における「結合と次数」
グラフ理論の「結合と次数」について
-
結合…頂点vi がある辺ejの端点である時,viとejは互いに結合しているという.
- 接する…共通の頂点を持つ,二つの平行でない辺は「接する」という.同様に,二つの頂点が共通の辺の端点であるときに「接する」という.
- 次数…頂点vが接する辺の数のこと.自己ループしている辺があるときは2回数える.尚,頂点vの次数はd(v)と表す.
- グラフGにおける最小次数,最大次数はそれぞれδ(G),Δ(G)と表す.
図２において,各頂点の結合次数はそれぞれ以下のとおりである.
d(v1)=2 d(v2)=３ d(v3)=３ ,d(v4)=２,
また,最小次数,最大次数は次のとおりである.
δ(G)=２ Δ(G)=３
定理１ グラフGにおいて,次数の合計は辺の数の二倍である.
それぞれの辺は端点として２つの頂点を持つので,全ての辺の両端にある頂点の合計は辺の数の２倍である.
- 奇頂点と偶頂点…ある頂点の次数が奇数であるときは奇頂点,偶数である時は偶頂点であるという.
定理２グラフGにおいて,奇頂点の数は偶数個ある.(ハンドシェイクの補題)
【証明】頂点の次数合計は
(偶頂点の次数の合計)＋(奇頂点の次数の合計)＝(全頂点の次数の合計)・・・(１)
で表され,偶頂点の次数の合計は偶数であるであることは明らかである.
ここで,定理１より
(全頂点の次数の合計)=(全辺の合計)×２
だったので,（１）式に代入すると
(偶頂点の次数の合計)＋(奇頂点の次数の合計)＝(全辺の合計)×２
となる.ここから偶頂点の合計を移項して
(全辺の合計)×２ー(偶頂点の次数の合計)＝(奇頂点の次数の合計)
が求められるので,奇頂点の次数の合計は偶数となる.
したがって,全ての条件において奇頂点の次数の合計が偶数であることは,
奇頂点が偶数個あるということである.
- 孤立した頂点…辺と接しない頂点のこと.
- つり飾り頂点…次数が１である頂点のこと.
- 空グラフ…辺の無いグラフのこと.(頂点の数は問わない)
