Definition (cont.)
subgraph的定義：G = (V, E, g) 而 G1 = (V1, E1, g1)，而V1是V的nonempty subset，E1是E的subset，且對所有屬於E的e來說，g(e) = g1(e) = {u,v} implies u,v屬於v1。
上述的定義有點複雜，但其實G1就是G的一部分。
proper subgraph的定義：G1是G的subgraph且E1為E的proper subset或V1為V的proper subset。
也就是說 不包含全部的V或E。
使U為V的nonempty subset，則當V1=U而且所有端點屬於U的edge都在E中，則G1是a subgraph induced by U.。記作G1 = G[U]。也就是說取出一部分的點，還有這些點所連成的線盡數包含。
同理的也可以用edge set去induce subgraph。
G - {v}代表去除頂點v和所有和頂點v incident的edge。
simple graph代表此圖中沒有parallel和loop edge。Petersen graph即是一個simple graph。
如果G包含至少兩個頂點，則至少會有兩個頂點其degree是相同的。(證明之)
Pigeonhole principle：如果有n+1隻鴿子和n個鴿巢，則至少有兩隻鴿子佔據同一個鴿巢。
Complete graph：Graph中每一點都和其他所有點adjacent。
Complete graph的edge數量是
，也就是
，任意兩點所形成的邊的數量總和，也可以透過(n-1) + (n-2) + ... + 0來得到。
對某一graph G來說，clique指的是一個V的subset U，而subgraph induced by U是一個complete graph。
Size指的是clique的頂點數量。
Maximal clique指的是這個clique不是其他任何clique的proper subset。Maximal clique可以同時存在多個。
Largest clique指的是這個clique的頂點數量超過或等於其他所有clique。
intractable: 棘手的
對某一graph G來說，independent set指的是V的subset U，其induce的subgraph沒有任何點相連。一個graph可以有多個independent set。
2-switch的定義：在某個graph G中有u, v, x, y四個頂點，且u和v相連，x和y相連，但u和x不相連，v和y不相連，則透過2-switch得到的graph h為u和x相連，v和y相連。也就是說有兩條線改為交錯了。
如果定義H是G經過一系列2-switch處理之後得到的graph，則：
(i) V(G) = V(H)
(ii) H經過一系列2-switch處理之後也可以得到G
(iii) 對所有頂點V來說 degG(V) = degH(V)
這裡有個Lemma，但我看不太懂他的證明…
這裡有個Theorem(Berge)，這是代表這是Berge's theorem，還是這個theorem是Berge發現的？
定理(Berge)：如果兩個graph其deg都相同，則一定可以透過2-switch互相轉換。
使得d1, d2, d3, ..., dn為一個遞減的sequence，而這個sequence等同於某個simple graph中的degree sequence，那麼這個sequence被稱為是graphical的。
因為是simple graph，所以不會有loop或parallel edges，因此di < n-1 for all i，1 <= i <= n。
Havel和Hakimi的Theroem可以用來測試一個Sequence是否為graphical：
例如說，43322只有在(3-2), (3-2), (2-1), (2-1)是graphical的情況下會是graphical，可以參考StackExchange。
但是1102這個sequence應該是graphical的，卻會化簡成02這個非graphical的sequence，還是說化簡時都要由大到小排序？
Complements of Simple Graph：有n個vertex的complete simple graph為Kn(不是應該是Kn-1嗎？)，因為其每個頂點的degree都相同，而有n個vertex的simple graph G其補集即是G-bar，G-bar的edge set E-bar即為Kn的edge set E1減掉G的edge set E。
Theorem：六個點的Graph或其補集中一定會有一個含有三角形。這個theorem可以類比成題目「六個人的派對中一定有三個人互相認識或互相不認識」，證明請見講義。
Cartesian Product:
使G1 = (V1, E1)而G2 = (V2, E2)，則此兩者的笛卡爾積G1 X G2即是此兩個圖片所有頂點之間互相的組合，而在G1 X G2上若是某兩點其兩者之一的座標相同且另外一個座標在原圖上adjacent，則這兩點也是adjacent。
而G1和G2的Join G1 + G2則是包含了G1和G2中所有的頂點和邊和兩邊頂點的全部配對，
Union即為聯集，頂點和邊的OR，intersection即為交集，頂點和邊的AND。Ring sum則類似互斥或，包含兩個graph中所有的頂點，和邊集合互斥或運算的結果。
subgraph的定義：G = (V, E, g) 而 G1 = (V1, E1, g1)，而V1是V的nonempty subset，E1是E的subset，且對所有屬於E的e來說，g(e) = g1(e) = {u,v} implies u,v屬於v1。
上述的定義有點複雜，但其實G1就是G的一部分。
proper subgraph的定義：G1是G的subgraph且E1為E的proper subset或V1為V的proper subset。
也就是說 不包含全部的V或E。
使U為V的nonempty subset，則當V1=U而且所有端點屬於U的edge都在E中，則G1是a subgraph induced by U.。記作G1 = G[U]。也就是說取出一部分的點，還有這些點所連成的線盡數包含。
同理的也可以用edge set去induce subgraph。
G - {v}代表去除頂點v和所有和頂點v incident的edge。
simple graph代表此圖中沒有parallel和loop edge。Petersen graph即是一個simple graph。
如果G包含至少兩個頂點，則至少會有兩個頂點其degree是相同的。(證明之)
Pigeonhole principle：如果有n+1隻鴿子和n個鴿巢，則至少有兩隻鴿子佔據同一個鴿巢。
Complete graph：Graph中每一點都和其他所有點adjacent。
Complete graph的edge數量是
，也就是，任意兩點所形成的邊的數量總和，也可以透過(n-1) + (n-2) + ... + 0來得到。對某一graph G來說，clique指的是一個V的subset U，而subgraph induced by U是一個complete graph。
Size指的是clique的頂點數量。
Maximal clique指的是這個clique不是其他任何clique的proper subset。Maximal clique可以同時存在多個。
Largest clique指的是這個clique的頂點數量超過或等於其他所有clique。
intractable: 棘手的
對某一graph G來說，independent set指的是V的subset U，其induce的subgraph沒有任何點相連。一個graph可以有多個independent set。
2-switch的定義：在某個graph G中有u, v, x, y四個頂點，且u和v相連，x和y相連，但u和x不相連，v和y不相連，則透過2-switch得到的graph h為u和x相連，v和y相連。也就是說有兩條線改為交錯了。
如果定義H是G經過一系列2-switch處理之後得到的graph，則：
(i) V(G) = V(H)
(ii) H經過一系列2-switch處理之後也可以得到G
(iii) 對所有頂點V來說 degG(V) = degH(V)
這裡有個Lemma，但我看不太懂他的證明…
這裡有個Theorem(Berge)，這是代表這是Berge's theorem，還是這個theorem是Berge發現的？
使得d1, d2, d3, ..., dn為一個遞減的sequence，而這個sequence等同於某個simple graph中的degree sequence，那麼這個sequence被稱為是graphical的。
因為是simple graph，所以不會有loop或parallel edges，因此di < n-1 for all i，1 <= i <= n。
Havel和Hakimi的Theroem可以用來測試一個Sequence是否為graphical：
但是1102這個sequence應該是graphical的，卻會化簡成02這個非graphical的sequence，還是說化簡時都要由大到小排序？
Complements of Simple Graph：有n個vertex的complete simple graph為Kn(不是應該是Kn-1嗎？)，因為其每個頂點的degree都相同，而有n個vertex的simple graph G其補集即是G-bar，G-bar的edge set E-bar即為Kn的edge set E1減掉G的edge set E。
Theorem：六個點的Graph或其補集中一定會有一個含有三角形。這個theorem可以類比成題目「六個人的派對中一定有三個人互相認識或互相不認識」，證明請見講義。
Cartesian Product:
使G1 = (V1, E1)而G2 = (V2, E2)，則此兩者的笛卡爾積G1 X G2即是此兩個圖片所有頂點之間互相的組合，而在G1 X G2上若是某兩點其兩者之一的座標相同且另外一個座標在原圖上adjacent，則這兩點也是adjacent。
Union即為聯集，頂點和邊的OR，intersection即為交集，頂點和邊的AND。Ring sum則類似互斥或，包含兩個graph中所有的頂點，和邊集合互斥或運算的結果。
留言
張貼留言