nano_exit

基礎的なことこそ、簡単な例が必要だと思うのです。

グラフ理論の個人用メモ（その２）

数学

bipartite grapheのcycleは全て偶数長。

edge数の制限

vertex数 $n$ のsimple graphにおいて、connected graphが $k$ 個含まれているとき、edge数 $m$ は次の不等式を満たす。
$\displaystyle n-k \le m \le\frac{1}{2}(n-k)(n-k+1)$
これは、cycleが無いときに最もedge数が少なく、complete graphのときに最もedge数が多いことが背景にある。

conneceted graphの条件。

vertex数 $n$ のsimple graphにedge数が $m \ge \frac{1}{2}(n-1)(n-2) + 1$ 個あれば、connected graphである。

disconnecting set

edge setの部分集合で、それをgraphから消去すると、disconnected graphになるようなもの。非連結化集合。

cutset

disconnecting setのうち、真部分集合がdisconnecting setではないもの。

bridge

元が1個からなるcutset。

edge connectivity

最小なcutsetの大きさ。辺連結度。

separating set

vertex setの部分集合で、その部分集合およびvertexにincidnetしているedgeを消去すると、disconnected graphになるようなもの。分離集合。

cut vertex

元が1個からなるseparating setに含まれているvertex。

girth

最短なcycleの長さ。内周。

distance

最短のpathの長さ。距離。

Turánの極値定理

vertex数2kのsimple graphで、三角形が無いとすると、edge数は $k^2$ 以下。

独立

edge setにcycleが含まれていないとき、edge setは独立であるという。

handshakingg lemma

任意のgraphにおけて、全てのvertexのdegreeの和は偶数になる。握手補題。

補題6.1

全てのvertexのdegreeが2以上のとき、cycleが存在する。

定理6.2

connected diagramがEulerian graphである必要十分条件は、全てのvertexのdegreeが偶数であることである。

系6.3

connected diagramがEulerian graphである必要十分条件は、edge setが互いに素なcycleに分割できることである。

系6.4

connected diagramがsemi-Eulerian graphである必要十分条件は、奇数次のvertexを2個だけ含んでいることである。

Fleuryのアルゴリズム

次の規則に従いながら、任意のinitial vertexから自由にedgeを辿る。
1. 辿ったedgeは削除する。それによりisolated vertexが生じたら、それも削除する。
2. どの段階でも、他に辿るedgeが無い限り、bridgeは渡らない。

Oreの定理

$n \ge 3$ のsimple graphにおいて、adjacentでない任意の二つのvetexを $v, w$ とするとき、 $deg( v ) + deg( w ) \ge n$ であれば、Hamiltonian graphとなる。

Diracの定理

$n \ge 3$ のsimple graphにおいて、任意のvertex $v$ に対して $\forall v \, deg(v) \ge n/2$ であれば、Hamiltonian graphとなる。

参考文献：グラフ理論入門