Chuyên đề đồ thị Hamilton

Chia sẻ: Basso Basso | Ngày: | Loại File: PPT | Số trang:22

0
507
lượt xem
132
download

Chuyên đề đồ thị Hamilton

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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

Chủ đề:
Lưu

Nội dung Text: Chuyên đề đồ thị Hamilton

  1. Chuyên đề ĐỒ THỊ HAMILTON    
  2. Giới thiệu: 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 Nhà toán học Hamilton    
  3. Định nghĩa: • Đường đi Hamilton là đường qua a b 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]) d c được gọi là đường đi Hamilton G2 nếu x[i]≠x[j] (1≤i
  4. Định nghĩa: • Chu trình Hamilton là đường đi b c Hamilton có một cạnh trong đồ thị nối đỉnh đầu với đỉnh cuối của đường đi a Hay chu trình (x[1],x[2],…,x[n],x[1]) e d được gọi là chu trình Hamilton nếu G1 x[i]≠x[j] (1≤i
  5. Định nghĩa: • Đồ thị Hamilton là đồ thị có chứa một chu trình Hamilton • Đồ thị nửa Hamilton là đồ thị có chứa một đường đi Hamilton    
  6. Một số ví dụ Đồ thị G1  là đồ thị  Đồ thị G2 là  b c a b đồ thị nửa  Hamilton Hamilton a d c e d G1 G2 a b e Đồ thị G3 không có  chu trình hay đường đi  Hamilton d c f g     G3
  7. Chú ý: Không giống như đồ thị Euler, chúng ta chưa có điều kiện cần và đủ để kiểm tra xem một đồ thị có là Hamilton hay không Cho đến nay chỉ có các điều kiện đủ để một đồ thị là đồ thị Hamilton hay có đường đi Hamilton.    
  8. Định lý về đồ thị Hamilton: 1. Đồ thị đầy đủ luôn là đồ thị Hamilton. Với n lẻ và n ≥ 3 thì Kn có (n-1)/2 chu trình Hamilton đôi một không có cạnh chung. Đồ thị đầy đủ K4    
  9. Định lý về đồ thị Hamilton: 2. Đơn đồ thị vô hướng G với n>2 đỉnh, mỗi đỉnh có deg(v) ≥ n/2 thì G là đồ thị Hamilton (Dirak 1952) b c a e d G    
  10. Định lý về đồ thị Hamilton: 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. Đồ 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 thỏa mãn                         
  11. Định lý về đồ thị Hamilton (tt): 4. Đồ thị đấu loại: là đồ thị có hướng mà trong đó 2 đỉnh bất kỳ của nó được nối với nhau bởi đúng một cung. a. Mọi đồ thị đấu loại là nửa Hamilton b. Mọi đồ thị đấu loại liên thông mạnh là Hamilton   Đồ thị đấu loại D5   Đồ thị đấu loại liên thông mạnh D6
  12. Định lý về đồ thị Hamilton (tt): 5. Đơn đồ thị vô hướng G gồm n đỉnh với n ≥ 3. Nếu deg(v) ≥(n-1)/2 với mọi đỉnh v của G thì G có đường b c đi Hamilton. a 6. Đơn đồ thị vô hướng G gồm n đỉnh với n ≥ 3. Nếu deg(x)+deg(y) ≥n với mọi cặp đỉnh x,y không kề nhau e d của G thì G là đồ thị Hamilton. G 7. Đơn đồ thị vô hướng G gồm n đỉnh và m cạnh. Nếu m ≥ (n2-3n+6)/2 thì G là đồ thị Hamilton.    
  13. Tìm chu trình Hamiloton của đồ thị: Cho tới nay, vẫn chưa tìm ra phương pháp với độ phức tạp đa thức để tìm chu trình cũng như đường đi Hamilton trong trướng hợp đồ thị tổng quát. Có thể sử dụng thuật toán quay lui để liệt kê chu trình Hamilton    
  14. Cấu trúc dữ liệu Lưu trữ đồ thị đã cho dưới dạng danh sách kề Ke(v) Liệt kê các chu trình Hamilton thu được bằng việc phát  triển dãy đỉnh  (X[1],…,X[k­1])    
  15. Mô tả thuật toán: Bước 1: Bắt đầu đi từ đỉnh 1,  x[1]:=1 Bước 2: Tìm và lưu đỉnh có cạnh nối với x[i] và đỉnh j này                chưa thăm trước đó. Bước 3: Nếu đỉnh j này là x[n] và giữa j và x[1] có cạnh nối   thì xuất ra đồ thị Hamilton.                        Nếu đỉnh j vẫn chưa phải là x[n] thì tiếp tục bước 2.     
  16. Mã giả của thuật toán Procedure Hamilton(k); Begin ∈    for  y     Ke(X[k­1]) do      if (k=n+1) and (y=v0) then ghinhan(X[1],…,X[n],v0)      else          if chuaxet[y] then           begin              X[k]:=y;              chuaxet[y]:=false;              Hamilton(k+1);              chuaxet[y]:=true;           end; End;    
  17. Dữ liệu vào: (input) Đồ thị vô hướng G gồm 5 đỉnh và 6 cạnh 1      5   6      1   2      1   3 5 2 1   4 2   4   2   5 3   5 4 3    
  18. Mô tả quá trình tìm chu trình Hamilton 1 5 2 4 3 1 2 3 4 5 6 X= Chu trình   1 3 2 5 4 2 1 3 4 1  1 Hamilton
  19. Nhận xét Với đồ thị có số cạnh lớn thuật tóan trên sẽ không thể đáp  ứng hai yêu cầu: 1. Thời gian thực hiện: độ phức tạp của thuật toán trong  trường hợp xấu nhất là O(n*m) (với n là số cạnh và m là  số đỉnh của đồ thị) 2. Kích thước bộ nhớ: do thuật toán sử dụng là thuật toán  quay lui nên việc xử lý đồ thị lớn sẽ gây tràn bộ nhớ.  Thuật toán này chỉ có khả năng làm việc với đồ thị có số  cạnh nhỏ    
  20. Bài tập 6 1 5 7 9 8 2 3 4 Đây có là đồ thị hamilton không?    
Đồng bộ tài khoản