planar graph: 畫在平面上則稱為plane graph，用圖案的方式(pictorial representation)來表達稱為planar representation。
在plane上有plane graph G，被G切割的區域稱之為faces of G。形成face的邊稱為boundary。在平面上的任何一點到boundary都不必經過任何edge，無論是透過直線還是曲線(curved line)。在G之外，沒有邊界無限延伸的face稱為exterior (outer) face(exterior: 外部)。
不是exterior faces的稱之為interior face。
Theory(Euler): G為一個connected planar graph，那麼其vertex數 - edge數 + face數 = 2。
Corollary: H1, H2, H3...為G的components，一共有k個，那麼總vertex數 - 總edge數 + 總face數 = k + 1。
Proof: 請參考講義，注意全部components的faces加起來會等於總face數量+k-1，為何?
k應該是多出來的exterior face，1則是少算一個face，但不知道是什麼face(平面整體?)。
如果某graph經過計算不符合Euler's theorem，那它即不是planar graph。如要符合Euler's theorem，K(3,3)的face數量必須等於5。
K(3,3)由4-cycles組成，沒有3-cycles(triangle)。如果頂點會形成face，那他們之間一定是cycle。
有5個cycle，每個都是4-cycles，代表說所有edge總共應該在cycles中出現4 * 5 = 20次。
但是實際數過後發現9個edges只有在cycles中出現18次，所以K(3,3)不是planar graph。
Theory: 對有k個components的simple planar graph G來說，edge數量 <= 3 * vertex數量 - 6k。
Corollary
Let G be a simple planar graph. Then there exists a vertex v in G such
that deg(v ) <= 5
a subdivision of a graph
homeomorphic isomorphic
Theorem (Kuratowski)
A simple graph is planar if and only if it does not contain a subgraph
homeomorphic to K5 or K3,3.
在plane上有plane graph G，被G切割的區域稱之為faces of G。形成face的邊稱為boundary。在平面上的任何一點到boundary都不必經過任何edge，無論是透過直線還是曲線(curved line)。在G之外，沒有邊界無限延伸的face稱為exterior (outer) face(exterior: 外部)。
不是exterior faces的稱之為interior face。
Theory(Euler): G為一個connected planar graph，那麼其vertex數 - edge數 + face數 = 2。
Corollary: H1, H2, H3...為G的components，一共有k個，那麼總vertex數 - 總edge數 + 總face數 = k + 1。
Proof: 請參考講義，注意全部components的faces加起來會等於總face數量+k-1，為何?
k應該是多出來的exterior face，1則是少算一個face，但不知道是什麼face(平面整體?)。
如果某graph經過計算不符合Euler's theorem，那它即不是planar graph。如要符合Euler's theorem，K(3,3)的face數量必須等於5。
K(3,3)由4-cycles組成，沒有3-cycles(triangle)。如果頂點會形成face，那他們之間一定是cycle。
有5個cycle，每個都是4-cycles，代表說所有edge總共應該在cycles中出現4 * 5 = 20次。
但是實際數過後發現9個edges只有在cycles中出現18次，所以K(3,3)不是planar graph。
Theory: 對有k個components的simple planar graph G來說，edge數量 <= 3 * vertex數量 - 6k。
Corollary
Let G be a simple planar graph. Then there exists a vertex v in G such
that deg(v ) <= 5
a subdivision of a graph
homeomorphic isomorphic
Theorem (Kuratowski)
A simple graph is planar if and only if it does not contain a subgraph
homeomorphic to K5 or K3,3.
proper vertex coloring
Vertex k-coloring即是用function f有k個顏色的color set去對應每一個vertex。如果相鄰的vertex都為不同顏色，則function f則稱為proper vertex k-coloring。而該graph則稱為vertex k-colorable。
chromatic number: 要用來proper vertex color某個graph所需要最少的color數量。
chromatic index則是proper edge coloring所需要的color數量。
XG為function(chromatic polynomial)
XG(k)則是對G來說proper vertex k-colorings的數量
XG是一個function，X(G)則是最小需要的顏色數量，兩者是不同的。
Vertex k-coloring即是用function f有k個顏色的color set去對應每一個vertex。如果相鄰的vertex都為不同顏色，則function f則稱為proper vertex k-coloring。而該graph則稱為vertex k-colorable。
chromatic number: 要用來proper vertex color某個graph所需要最少的color數量。
chromatic index則是proper edge coloring所需要的color數量。
XG為function(chromatic polynomial)
XG(k)則是對G來說proper vertex k-colorings的數量
XG是一個function，X(G)則是最小需要的顏色數量，兩者是不同的。
留言
張貼留言