NOTE 1 : Although there is no Δ (Triangle), we should not only check e ≤ 2 v - 4, but also check e ≤ [ k / (k-2) ] * (v - 2).
就也是一個念資訊的大學生,涉足領域在網路、資安、程設、系統、網設..... Next City @ Veck:http://veck.logdown.com/
2012年11月1日 星期四
[離散] Planar Graph and Coloring Theorem
Problem 1: Show that the graph is not planar, and find a subgraph homeomorphic to K3,3.
NOTE 1 : Although there is no Δ (Triangle), we should not only check e ≤ 2 v - 4, but also check e ≤ [ k / (k-2) ] * (v - 2).
NOTE 1 : Although there is no Δ (Triangle), we should not only check e ≤ 2 v - 4, but also check e ≤ [ k / (k-2) ] * (v - 2).
[離散] Euler Circuit and Hamiltonian Cycle Prove
This is my note for learning and proving Euler Circuit and Hamiltonian Cycle problems.
Problem 1: Given a 2-dimension mesh graph of m rows and n columns as follows (m>2, n>2)
(a) Please show that if both m and n are even number, the mesh graph doesn't contain an Euler Circuit.
(b) Please show that if both m and n are even number, the mesh graph doesn't contain an Euler Trail.
(c) Please show that if both m and n are even number, the mesh graph contains a Hamiltonian Cycle.
(d) Please show that if both m and n are odd number, the mesh graph contains a Hamiltonian Path.
Proof :
Problem 1: Given a 2-dimension mesh graph of m rows and n columns as follows (m>2, n>2)
| Courtesy of http://www.aya.or.jp/~babalabo/Hamilton/Draft1-2.html |
(b) Please show that if both m and n are even number, the mesh graph doesn't contain an Euler Trail.
(c) Please show that if both m and n are even number, the mesh graph contains a Hamiltonian Cycle.
(d) Please show that if both m and n are odd number, the mesh graph contains a Hamiltonian Path.
Proof :
訂閱:
文章 (Atom)
