Chapter 2, Section 1:
Walk描述的是從點u到點v中間經過的點和線所組成的sequence。
(u = v1, e1, v2, e2, v3, e3, . . . , vn1, en1, vn, en, vn+1 = v)
而directed walk就是在directed walk中描述。
Length of a walk即為這個walk中包含的edge數量，如果其為零，則這個walk僅包含一個點。
從u到v的walk可稱為 u-v(directed) walk。如果u和v是相同的點，則稱為closed (directed) walk，反之則稱為open (directed) walk。
沒有重複邊的walk稱為trail，沒有重複點的walk稱為path。Path一定為trail(沒有重複的點也就不可能有重複的邊)，但trail不一定是path。
一個只有一個點的walk稱為trvial walk。
也就是說，一個nontrivial closed trail稱為circuit。因為是trail，所以circuit中是有可能存在重複的點的。
而除了起始點之外沒有任何重複的點的circuit就稱為cycle。有n個頂點的cycle就稱為Cn。
對於cycle C，以下的theorem成立：
C中的每一點deg都>=2
C中的每一點都一定剛好和C中的兩個edge incident。
若C'是包含在C中的一個cycle，C'的vertex set包含在C的vertex set，C'的edge set包含在C的edge set，則C' = C。
有k條edge的cycle即稱為k-cycle，若edge數量是even(odd)則稱為even(odd) cycle。
Chapter 2, Section 2:
Connected: G中的任意兩點u和v都有walk的話稱為connected，反之則為disconnected。
而totally disconnected則是指任意兩點都沒有path。
Underlying graph: 有向圖G的underlying graph即是把有向改成無向。
Weakly and strongly connected: 一個digraph G如果其underlying graph為connected就稱為weakly connect。如果任意兩點u-v都有directed walk那就稱為strongly connected。有些點會因為方向的關係無法到達，那這個圖就不是strongly connected的。
Component: 如果Subgraph H是G的component，則代表H中任意兩點都是connected的，且H is not properly contained in any connected subgraph of G(?)。
Properly contained是什麼意思?Connected subgraph又是什麼意思?
Theorem: A connected graph with n vertices has at least n-1 edges, where n >= 1。
我看不懂證明。
Theorem: 有2n個vertices的simple graph，如果每個點的degree都至少有n，那個這個圖是connected的。證明並未給出。
例子：地圖上有100個城市，每個城市都至少和50個其他城市透過公車相連，那麼透過搭公車即可以到地圖上任何的城市。
Theorem: 有n個vertices的simple graph，如果每個點的degree都大於等於(n-1)/2，那麼這個圖是connected的。基本上就是上面的theorem，只是可以處理奇數，滿足條件必須所有degree都大於等於ceil(n/2)。
Theorem: G = (V, E)有n個vertices和k個edges，那麼G至少要有(n-k)個component。證明並未給出，或許可以看成每個edge都會讓component的數量減少。
Definition: G = (V, E)是一個圖，而v則是V中的一個點。如果將v從G中刪除後產生的新圖G - {v}比G有更多component，那麼v就稱為G的cut vertex(或articulation point)。
Articulation: 關節。
想法: 如果G分割後會產生不同component，那在分割前，不同component應該都是透過cut vertex相連。
Lemma: v是G = (V, E)中的一個cut vertex若且唯若對於G中的另外兩點u和w來說，所有u跟w之間的path u-w都會通過v。
也就是說，u和w之間的溝通一定要經過v，而這一定會使其成為cut vertex。
Complete graph沒有cut vertex。
這裡提到了path graph，但我不知道它是什麼意思。對u-w的path graph來說，除了u和w之外的所有點都是cut vertex，我想它就是一條線吧。
Definition: 對graph G來說，移除vertex cut set中的任意一點都會使G變成disconnected。
也就是說，移除這個set中的任意一點都會產生獨立的點，所以其中所有點都是cut vertex嗎？
Definition: 對graph G來說，最少需要移除幾個點才能使G變成disconnected或只剩下一個點的數量稱為connectivity of G，或記作K(G)。如果K(G) >= K，K為非負整數，則G可稱作K-Connected。
也就是說，還需要移除幾個點才能使G的連結性消失。
Complete graph Kn的connectivity為n-1，n >= 1。
對connected simple graph G來說，如果G的connectivity為1，那麼G擁有cut vertex，或是G是K2。也就是說刪除cut vertex馬上可以使G消失連結性。
不是K1的simple graph G其connectivity為0若且唯若G不是connected的。
Definition: G中的兩點u和v的distance，或記作d(u, v)，是兩個點之間的shortest path的length。如果兩個點無法連接，那d(u, v)定義為inf。
d(u, v)一定大於等於零。
d(u, v) = d(v, u)。
d(u, v) + d(v , w) >= d(u, w)。
Definition: G = (V, E)為connected graph，那麼diameter of G，或記作diam G，定義為diam G = max{d(u, v) | u, v belongs to V}。
Diameter: 半徑。
也就是說diam G是G中最長的distance。
Theorem: G = (V, E)為有n >= 2個vertices的connected simple graph，則G至少有兩個點不是cut vertex。
這個theorem沒那麼直覺。
證明: 在G中，存在兩個點u, v的distance大於或等於其他所有點的distance。假設它們其中一點v是cut vertex，那麼就會存在一點w，在刪去v的圖G - {v}中，u和w不屬於同一個component。這意味著在G中u和w之間的所有path u-w上都應該有v(因為v是cut vertex)，也就是說d(u,w) > d(u, v)，發生矛盾，所以v和u不可能是cut vertex。
所以說，simple graph中距離最遠的那兩個點一定不會是cut vertex。
Definition: 如果從G = (V, E)中刪除edge e會使component的數量增加，使G失去連接性，則e即為G的cut edge，或稱為bridge。
Bridge這個名稱應是代表了G的兩個部分都一定要通過e來溝通。
Theorem: 如果G是connected graph，e是G的cut edge若且唯若e不屬於任何cycle。
證明: 看不太懂，先跳過。
Definition: 對simple graph G來說，最少需要移除幾個邊才能使G變成disconnected或null graph的數量稱作edge connectivity，記作K'(G)。
K'(G) = 1若且唯若G有cut edge。
Definition: δ(G) = min{deg(v) | v is a vertex in G}。
δ念作delta，δ(g)是V中存在最低的deg值。
δ(G) = 2。
v4為cut vertex，K(G) = 1。
K'(G) = 2，因為需要移除e6和e7才能使G成為disconnected。
K(G) < K'(G) <= δ(G)。
Theorem: 對simple graph G來說，K(G) <= K'(G) <= δ(G)。
難以理解的定理…
證明: 太複雜，先跳過。
Definition: 使u和v為graph G中的兩個不同的點，再使F = {Pi1, Pi2, ..., Pik}為u到v之間不同path的集合，如果對F中的任意兩個path來說，u和v都是唯二共通的點，則F稱為a collection of k internally disjoint paths between u and v。
Internally disjoint path，應該就是指u和v之間不同的path?
Theorem: G是一個至少有三個vertices的simple graph。則G是2-connected(見上方的定義)若且唯若對所有任意兩個不同點u和v來說都有2 disjoints paths between u and v。
這個theorem不太直覺，而且也沒有證明。
2-connected指的是至少需要移除兩點才能分離G嗎?
Chapter 2, Section 3:
Definition: 如果vertex set V of G可以被分成兩部分，V1和V2，使E中的每條edge都是分別和V1和V2的其中一個點incident，那麼G就稱作Bipartite graph。
Definition: 如果V1和V2分別有m和n個vertices，且V1和V2中的任意點都有相連，那麼G稱作complete bipartite graph，或記作Km,n。
Theorem: 如果G = (V, E)是由V1, V2組成的k-regular bipartite graph，那麼|V1| = |V2|。
Theorem: Non-null graph為bipartite的若且唯若它不包含任何odd-length cycle。
像是三角形就不是bipartite。
Chapter 2, Section 4:
假設有一群女生和一群男生，每個女生都只喜歡一部分的男生，將其兩兩配對，如何才能讓每個女生都剛好配到一個男生，每個男生都至多配到一個女生呢？
將男女生視為vertices，女生如果喜歡某個男生，則Gi和Bi即為相連。這樣就形成了一個bipartite graph。
Definition: 使G = (V, E)為一個simple graph，那麼a subset M of the edge set E可以稱做matching，只要M中的所有edges都沒有common end vertex。
Definition: G = (V, E)是一個simple graph，M是其matching，則:
M-saturated的vertex V指的是M中有edge其end point是V。
A是G中的vertex set，那麼如果A中的所有vertex是M-saturated的，A也稱作M-saturated。
如果G中的每一個頂點都為M-saturated，那麼M稱作G的Perfect match。
如果M是G中能找到的matching中edge數量最多者，那麼M是maximum的。
所有perfect match都為maximum。
Definition: 使G = (V, E)為一個由V1, V2組成的bipartite graph，而A是V1的一個subset，那麼NG(A)代表的即是V2中所有至少和A中的點有一邊相連的點的集合，又記作neighbors of A。
也就是V2中和A相鄰的點。
Hall's Marriage Theorem: 使G = (V, E)為一個由V1, V2組成的bipartite graph，那麼存在一個M且M saturates V1若且唯若對V1的所有subset A來說，|A| <= |NG(A)|。
也就是說，A的鄰居數量至少要大於或等於A的數量，A才能為saturated。而且如果所有A都滿足條件，那麼M一定saturate V1。
Corollary: G = (V, E)為V1, V2組成的k-regular bipartite graph，那麼G一定有perfect match。
Walk描述的是從點u到點v中間經過的點和線所組成的sequence。
(u = v1, e1, v2, e2, v3, e3, . . . , vn1, en1, vn, en, vn+1 = v)
而directed walk就是在directed walk中描述。
Length of a walk即為這個walk中包含的edge數量，如果其為零，則這個walk僅包含一個點。
從u到v的walk可稱為 u-v(directed) walk。如果u和v是相同的點，則稱為closed (directed) walk，反之則稱為open (directed) walk。
沒有重複邊的walk稱為trail，沒有重複點的walk稱為path。Path一定為trail(沒有重複的點也就不可能有重複的邊)，但trail不一定是path。
一個只有一個點的walk稱為trvial walk。
也就是說，一個nontrivial closed trail稱為circuit。因為是trail，所以circuit中是有可能存在重複的點的。
而除了起始點之外沒有任何重複的點的circuit就稱為cycle。有n個頂點的cycle就稱為Cn。
對於cycle C，以下的theorem成立：
C中的每一點deg都>=2
C中的每一點都一定剛好和C中的兩個edge incident。
若C'是包含在C中的一個cycle，C'的vertex set包含在C的vertex set，C'的edge set包含在C的edge set，則C' = C。
有k條edge的cycle即稱為k-cycle，若edge數量是even(odd)則稱為even(odd) cycle。
Chapter 2, Section 2:
Connected: G中的任意兩點u和v都有walk的話稱為connected，反之則為disconnected。
而totally disconnected則是指任意兩點都沒有path。
Underlying graph: 有向圖G的underlying graph即是把有向改成無向。
Weakly and strongly connected: 一個digraph G如果其underlying graph為connected就稱為weakly connect。如果任意兩點u-v都有directed walk那就稱為strongly connected。有些點會因為方向的關係無法到達，那這個圖就不是strongly connected的。
Component: 如果Subgraph H是G的component，則代表H中任意兩點都是connected的，且H is not properly contained in any connected subgraph of G(?)。
Properly contained是什麼意思?Connected subgraph又是什麼意思?
Theorem: A connected graph with n vertices has at least n-1 edges, where n >= 1。
我看不懂證明。
Theorem: 有2n個vertices的simple graph，如果每個點的degree都至少有n，那個這個圖是connected的。證明並未給出。
例子：地圖上有100個城市，每個城市都至少和50個其他城市透過公車相連，那麼透過搭公車即可以到地圖上任何的城市。
Theorem: 有n個vertices的simple graph，如果每個點的degree都大於等於(n-1)/2，那麼這個圖是connected的。基本上就是上面的theorem，只是可以處理奇數，滿足條件必須所有degree都大於等於ceil(n/2)。
Theorem: G = (V, E)有n個vertices和k個edges，那麼G至少要有(n-k)個component。證明並未給出，或許可以看成每個edge都會讓component的數量減少。
Definition: G = (V, E)是一個圖，而v則是V中的一個點。如果將v從G中刪除後產生的新圖G - {v}比G有更多component，那麼v就稱為G的cut vertex(或articulation point)。
Articulation: 關節。
想法: 如果G分割後會產生不同component，那在分割前，不同component應該都是透過cut vertex相連。
Lemma: v是G = (V, E)中的一個cut vertex若且唯若對於G中的另外兩點u和w來說，所有u跟w之間的path u-w都會通過v。
也就是說，u和w之間的溝通一定要經過v，而這一定會使其成為cut vertex。
Complete graph沒有cut vertex。
這裡提到了path graph，但我不知道它是什麼意思。對u-w的path graph來說，除了u和w之外的所有點都是cut vertex，我想它就是一條線吧。
Definition: 對graph G來說，移除vertex cut set中的任意一點都會使G變成disconnected。
也就是說，移除這個set中的任意一點都會產生獨立的點，所以其中所有點都是cut vertex嗎？
Definition: 對graph G來說，最少需要移除幾個點才能使G變成disconnected或只剩下一個點的數量稱為connectivity of G，或記作K(G)。如果K(G) >= K，K為非負整數，則G可稱作K-Connected。
也就是說，還需要移除幾個點才能使G的連結性消失。
Complete graph Kn的connectivity為n-1，n >= 1。
對connected simple graph G來說，如果G的connectivity為1，那麼G擁有cut vertex，或是G是K2。也就是說刪除cut vertex馬上可以使G消失連結性。
不是K1的simple graph G其connectivity為0若且唯若G不是connected的。
Definition: G中的兩點u和v的distance，或記作d(u, v)，是兩個點之間的shortest path的length。如果兩個點無法連接，那d(u, v)定義為inf。
d(u, v)一定大於等於零。
d(u, v) = d(v, u)。
d(u, v) + d(v , w) >= d(u, w)。
Definition: G = (V, E)為connected graph，那麼diameter of G，或記作diam G，定義為diam G = max{d(u, v) | u, v belongs to V}。
Diameter: 半徑。
也就是說diam G是G中最長的distance。
Theorem: G = (V, E)為有n >= 2個vertices的connected simple graph，則G至少有兩個點不是cut vertex。
這個theorem沒那麼直覺。
證明: 在G中，存在兩個點u, v的distance大於或等於其他所有點的distance。假設它們其中一點v是cut vertex，那麼就會存在一點w，在刪去v的圖G - {v}中，u和w不屬於同一個component。這意味著在G中u和w之間的所有path u-w上都應該有v(因為v是cut vertex)，也就是說d(u,w) > d(u, v)，發生矛盾，所以v和u不可能是cut vertex。
所以說，simple graph中距離最遠的那兩個點一定不會是cut vertex。
Definition: 如果從G = (V, E)中刪除edge e會使component的數量增加，使G失去連接性，則e即為G的cut edge，或稱為bridge。
Bridge這個名稱應是代表了G的兩個部分都一定要通過e來溝通。
Theorem: 如果G是connected graph，e是G的cut edge若且唯若e不屬於任何cycle。
證明: 看不太懂，先跳過。
Definition: 對simple graph G來說，最少需要移除幾個邊才能使G變成disconnected或null graph的數量稱作edge connectivity，記作K'(G)。
K'(G) = 1若且唯若G有cut edge。
Definition: δ(G) = min{deg(v) | v is a vertex in G}。
δ念作delta，δ(g)是V中存在最低的deg值。
v4為cut vertex，K(G) = 1。
K'(G) = 2，因為需要移除e6和e7才能使G成為disconnected。
K(G) < K'(G) <= δ(G)。
Theorem: 對simple graph G來說，K(G) <= K'(G) <= δ(G)。
難以理解的定理…
證明: 太複雜，先跳過。
Definition: 使u和v為graph G中的兩個不同的點，再使F = {Pi1, Pi2, ..., Pik}為u到v之間不同path的集合，如果對F中的任意兩個path來說，u和v都是唯二共通的點，則F稱為a collection of k internally disjoint paths between u and v。
Internally disjoint path，應該就是指u和v之間不同的path?
Theorem: G是一個至少有三個vertices的simple graph。則G是2-connected(見上方的定義)若且唯若對所有任意兩個不同點u和v來說都有2 disjoints paths between u and v。
這個theorem不太直覺，而且也沒有證明。
2-connected指的是至少需要移除兩點才能分離G嗎?
Chapter 2, Section 3:
Definition: 如果vertex set V of G可以被分成兩部分，V1和V2，使E中的每條edge都是分別和V1和V2的其中一個點incident，那麼G就稱作Bipartite graph。
Definition: 如果V1和V2分別有m和n個vertices，且V1和V2中的任意點都有相連，那麼G稱作complete bipartite graph，或記作Km,n。
Theorem: 如果G = (V, E)是由V1, V2組成的k-regular bipartite graph，那麼|V1| = |V2|。
Theorem: Non-null graph為bipartite的若且唯若它不包含任何odd-length cycle。
像是三角形就不是bipartite。
Chapter 2, Section 4:
假設有一群女生和一群男生，每個女生都只喜歡一部分的男生，將其兩兩配對，如何才能讓每個女生都剛好配到一個男生，每個男生都至多配到一個女生呢？
將男女生視為vertices，女生如果喜歡某個男生，則Gi和Bi即為相連。這樣就形成了一個bipartite graph。
(這個範例隱含了男生只要是女生都來者不拒的前提。)
Definition: Subset M of the set E稱為G的mathcing，如果M中包含的edges剛好可以將bipartite的V1, V2中的所有點相連，且沒有edge共享同樣的頂點。V2有可能有沒被連到的多餘頂點。Definition: 使G = (V, E)為一個simple graph，那麼a subset M of the edge set E可以稱做matching，只要M中的所有edges都沒有common end vertex。
Definition: G = (V, E)是一個simple graph，M是其matching，則:
M-saturated的vertex V指的是M中有edge其end point是V。
A是G中的vertex set，那麼如果A中的所有vertex是M-saturated的，A也稱作M-saturated。
如果G中的每一個頂點都為M-saturated，那麼M稱作G的Perfect match。
如果M是G中能找到的matching中edge數量最多者，那麼M是maximum的。
所有perfect match都為maximum。
Definition: 使G = (V, E)為一個由V1, V2組成的bipartite graph，而A是V1的一個subset，那麼NG(A)代表的即是V2中所有至少和A中的點有一邊相連的點的集合，又記作neighbors of A。
也就是V2中和A相鄰的點。
Hall's Marriage Theorem: 使G = (V, E)為一個由V1, V2組成的bipartite graph，那麼存在一個M且M saturates V1若且唯若對V1的所有subset A來說，|A| <= |NG(A)|。
也就是說，A的鄰居數量至少要大於或等於A的數量，A才能為saturated。而且如果所有A都滿足條件，那麼M一定saturate V1。
Corollary: G = (V, E)為V1, V2組成的k-regular bipartite graph，那麼G一定有perfect match。
留言
張貼留言