tailieunhanh - Chuyên đề đồ thị Hamilton

Khái niệm đường đi Hamilton được xuất phát từ bài toán: “Xuất phát từ một đỉnh của khối thập nhị diện đều, hãy đi dọc theo các cạnh của khối đó sao cho đi qua tất cả các đỉnhkhác, mỗi đỉnh đi qua đúng một lần, sau đó trở về đỉnh xuất phát” Bài toán này được nhà toán học Hamilton đưa ra vào năm 1859 | Chuyên đề ĐỒ THỊ HAMILTON Khái niệm đường đi Hamilton được xuất phát từ bài toán: “Xuất phát từ một đỉnh của khối thập nhị diện đều, hãy đi dọc theo các cạnh của khối đó sao cho đi qua tất cả các đỉnhkhác, mỗi đỉnh đi qua đúng một lần, sau đó trở về đỉnh xuất phát” Bài toán này được nhà toán học Hamilton đưa ra vào năm 1859 Giới thiệu: Nhà toán học Hamilton Đường đi Hamilton là đường qua tất cả các đỉnh của đồ thị và đi qua mỗi đỉnh đúng một lần Hay đường đi (x[1],x[2], ,x[n]) được gọi là đường đi Hamilton nếu x[i]≠x[j] (1≤i2 đỉnh, mỗi đỉnh có deg(v) ≥ n/2 thì G là đồ thị Hamilton (Dirak 1952) Định lý về đồ thị Hamilton: a b e c d G 3. Giả sử G là đồ thị có hướng liên thông mạnh với n đỉnh. Nếu với mỗi đỉnh thuộc đồ thị thoả: deg+(v) ≥ n/2 và deg-(v) ≥ n/2 thì G là đồ thị Hamilton. Định lý về đồ thị Hamilton: Đồ thị G có hướng liên thông mạnh Ví dụ: Đồ thị G là đồ thị có hướng liên thông mạnh .