顯示具有 Discrete Mathematic 標籤的文章。 顯示所有文章
顯示具有 Discrete Mathematic 標籤的文章。 顯示所有文章

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).

[離散] 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)
Courtesy of http://www.aya.or.jp/~babalabo/Hamilton/Draft1-2.html
(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 :