Graphic Theory (2)

Definition(cont.)

3-cube的定義：
使B3為一個包含所有長度為3的binary strings {000,001,010,011,100,101,110,111}
使得G為一個其vertex set V為對應到B3所有元素的vertex set。而在V中的任意兩點u 和 v是adjacent的 if and only if u 和 v兩點之間只有差一個位元。

3-cube的圖片請見講義。

同樣的，對應到長度為k的binary strings的graph就稱為k-cube，寫作Bk或Qk。

loop會讓vertex +2 degree。

Degree sequence 為 G 每一點的degree，且由大排到小，例如n1, n2, n3, n4...並且n1 >= n2 >= n3 >= n4...

Graph中每一點的degree總和等於edge數量的兩倍，因為每個edge都會提供2點degree的總和。

Graph中degree為奇數的點數量必定為偶數，因為degree總和必定為偶數。

Directed path的definition:

A directed graph (or digraph) G is a triple (V, E, g), where
(i) V is a finite nonempty set of vertices;
(ii) E is a finite set (may be empty) of directed edges or arcs; and
(iii) for nonempty set E, g : E -> V x V is a function that assigns to each arc
e an ordered pair (v,w), where v and w are vertices (v and w may be the
same). (一個將E和兩點對應起來的function)

Directed path 簡稱為 Digraph 。

如果g(e) = (v,w)，則v稱為起始點tail，w則是結束點head。(是不是寫反了？)

v的in-degree或indeg(v)即是連入v的edge數量，out-degree或outdeg(v)則是連出v的edge數量。而我們再定義loop會提供一個indeg和outdeg給它的v。

indeg的總和會等於outdeg的總和，也會等於edge的數量。

Tournament Graph的定義：

A tournament graph is a directed graph where for every pair of distinct

vertices u and v there is exactly one arc from u to v or from v to u, but

not both.

任兩點之間都有唯一一條線相鄰，(u,v)或者(v,u)。

Round-robin:循環賽

循環賽的比賽結果就可以表示為一個tournament graph。

Binary relation的定義：

定義R為A和B之間的relation，則。

也就是說R是AxB的subset(什麼是AxB?)

那假如，

則a稱作R-related至b，記作aRb。

empty set和AxB都subset equal()AxB，這兩種Relation分別稱作empty relation和universal relation。

可以用R來表示Graph中的線的連結關係，例如說R = {(a,a), (a,b), (b,c), (c,d)}。

之所以叫binary relation，我想應該是因為兩個點之間的線不是存在就是不存在(例如(a,b)和(b,a))。

對R來說，如果：
每個點都連到自身，aRa，則R是reflexive的。

對任意點a連到b則b也連到a，aRb implies bRa，則R是symmetric的。
對任意點a連到b，b連到c，則a也會連到c，aRb and bRc imply aRc，則R是transitive的。

如果這三者都成立，則R是equivalance relation。