Tìm kiếm
Đang tải khung tìm kiếm
Kết quả 1 đến 1 của 1

    THẠC SĨ Chu trình Hamilton và chu trình dài nhất trong một số lớp đồ thị có tổng bậc lớn

    D
    dream dream Đang Ngoại tuyến (18495 tài liệu)
    .:: Cộng Tác Viên ::.
  1. Gửi tài liệu
  2. Bình luận
  3. Chia sẻ
  4. Thông tin
  5. Công cụ
  6. Chu trình Hamilton và chu trình dài nhất trong một số lớp đồ thị có tổng bậc lớn

    Lời cảm ơn
    Luận án được hoàn thành dưới sự hướng dẫn tận tâm của PGS.TSKH. Vũ
    Đình Hòa. Tác giả xin bày tỏ lòng biết ơn sâu sắc đến thầy, người đã thường xuyên
    động viên, giúp đỡ, định hướng và đóng góp những ý kiến quý báu cho công việc
    của tác giả trong suốt thời gian học tập và làm nghiên cứu sinh.
    Tác giả cũng xin bày tỏ lòng biết ơn sâu sắc tới GS.TS. Vũ Đức Thi, người đã
    giúp đỡ tận tình và hướng dẫn tác giả từ khi làm luận văn Cao học cho đến khi hoàn
    thành bản luận án này.
    Tác giả xin trân trọng biết ơn Viện Công Nghệ Thông Tin – Viện Hàn Lâm
    Khoa Học và Công Nghệ Việt Nam, Học Viện Tài Chính và bộ môn Khoa Học Máy
    Tính – Đại học Sư Phạm Hà Nội đã có những quan tâm ưu ái và tạo điều kiện tốt
    cho tác giả trong thời gian làm nghiên cứu sinh.
    Tác giả cũng xin được tỏ lòng biết ơn sâu sắc tới gia đình, những người luôn
    động viên và giúp đỡ tác giả cả về tinh thần lẫn vật chất trong suốt thời gian học tập
    và làm nghiên cứu sinh.
    Xin cảm ơn các bạn bè đồng nghiệp gần xa đã động viên, giúp đỡ và khích lệ
    tác giả trong thời gian làm nghiên cứu sinh.

    iii
    Mục Lục
    Lời cam đoan . i
    Lời cảm ơn ii
    Danh sách các ký hiệu . v
    Danh mục hình vẽ . vii
    Danh mục bảng ix
    MỞ ĐẦU 1
    CHƯƠNG 1. TỔNG QUAN VỀ CHU TRÌNH TRONG ĐỒ THỊ . 4
    1.1. Một số khái niệm và quy ước . 4
    1.1.1. Các khái niệm cơ bản của lý thuyết đồ thị . 4
    1.1.2. Một số ký hiệu và quy ước . 7
    1.2. Chu trình trong đồ thị 2-liên thông . 8
    1.3. Chu trình Hamilton . 9
    1.3.1. Độ phức tạp của bài toán . 10
    1.3.2. Một số điều kiện cần 11
    1.3.3. Một số điều kiện đủ đối với bậc của đỉnh 12
    1.3.4. Một số thuật toán xác định chu trình Hamilton 14
    1.4. Bao đóng đồ thị . 15
    1.5. Chu trình Dominating . 18
    1.6. Chu trình trong đồ thị có tập láng giềng lớn . 20
    1.7. Kết luận Chương 1 21
    CHƯƠNG 2. MỘT SỐ LỚP ĐA THỨC CỦA BÀI TOÁN 22
    2.1. Giới thiệu bài toán và . 22
    2.2. Độ phức tạp của bài toán và 22
    2.3. Độ phức tạp của bài toán . 24
    2.3.1. Một số kết quả với 24
    2.3.2. Chứng minh cho Định lý 2.3 27
    2.3.3. Thuật toán đa thức nhận biết ba dạng đồ thị đặc biệt thỏa mãn 48
    2.4. Bài toán 50 iv
    2.5. Kết luận Chương 2 51
    CHƯƠNG 3. THUẬT TOÁN ĐA THỨC XÁC ĐỊNH CHU TRÌNH
    HAMILTON TRONG ĐỒ THỊ VÀ
    53
    3.1. Thuật toán cho lớp đồ thị 53
    3.2. Thuật toán cho lớp đồ thị
    . 57
    3.3. Sử dụng bao đóng cho các lớp đồ thị có tổng bậc lớn 59
    3.4. Chương trình thực nghiệm 61
    3.4.1. Giới thiệu chương trình 62
    3.4.2. Bộ dữ liệu đầu vào . 63
    3.4.3. Đánh giá hiệu năng . 64
    3.5. Kết luận Chương 3 69
    CHƯƠNG 4. ĐÁNH GIÁ ĐỘ DÀI CHU TRÌNH DÀI NHẤT TRONG ĐỒ THỊ
    1-TOUGH VỚI . 70
    4.1. Giới thiệu Giả thuyết Bauer 70
    4.2. Các Tính chất và Bổ đề . 70
    4.3. Chứng minh cho các trường hợp 79
    4.4. Kết luận Chương 4 91
    KẾT LUẬN 92
    Những công trình đã công bố liên quan đến luận án . 93
    Tài liệu tham khảo 94

    v
    Danh sách các ký hiệu
    Đồ thị với tập đỉnh và tập cạnh | | Bậc (hay số đỉnh) của đồ thị Cạnh nối đỉnh và đỉnh Bậc của đỉnh trên đồ thị Bậc tối tiểu của Đồ thị đầy đủ với đỉnh Chỉ số ổn định trong của đồ thị Số thành phần liên thông của đồ thị Chỉ số liên thông của đồ thị Tập láng giềng của đỉnh trên đồ thị Đồ thị là đồ thị con của đồ thị . , với . ⋃ , với . ̅ Đồ thị bù của Đồ thị con thu được từ bằng cách loại bỏ tất cả các đỉnh của , Đồ thị thu được từ bằng cách loại bỏ cạnh , Đồ thị thu được từ bằng cách bổ sung cạnh nối và [ ] Đồ thị con sinh của trên tập đỉnh con Toughness của đồ thị Khoảng cách của hai đỉnh trong đồ thị Phép kết nối đồ thị và Đồ thị lũy thừa Bao đóng của đồ thị [ ] [ ] Nhãn của cạnh và nhãn của cạnh . Tổng bậc nhỏ nhất của đỉnh độc lập Tổng bậc nhỏ nhất của các cặp đỉnh có khoảng cách bằng 2. ⃗⃗⃗ Chu trình theo một chiều quay định hướng. ⃖⃗⃗⃗ Chu trình với chiều quay ngược với chiều của ⃗⃗⃗ Đỉnh liền trước và đỉnh liền sau của theo chiều ⃗⃗⃗ . , với . vi
    , với . ⃗⃗⃗ ⃖⃗⃗⃗ Đoạn đường trên từ tới theo chiều quay ⃗⃗⃗ . Đường đi với các đỉnh cuối là . | | | | Số đỉnh của đường đi , chu trình . Độ dài (số cạnh) của đường đi , chu trình . Chu vi của , hay độ dài của chu trình dài nhất trong . Bài toán đường đi Hamilton (Hamiltonian Path) Bài toán chu trình Hamilton (Hamiltonian Cycle) Bài toán trong lớp đồ thị thỏa mãn
    Bài toán trong lớp đồ thị thỏa mãn | | . | | . , với với là một chu trình dài nhất của . là một chu trình dài nhất của .

    vii
    Danh mục hình vẽ
    Hình 1.1. Đồ thị . . 5
    Hình 1.2. Đường đi sau khi mở rộng đến đỉnh . 8
    Hình 1.3. Đồ thị Petersen. 12
    Hình 1.4. Đồ thị . . 13
    Hình 1.5. Quá trình tạo bao đóng đồ thị. . 16
    Hình 1.6. Biến đổi chu trình . 18
    Hình 1.7. Chu trình Dominating. . 19
    Hình 1.8. Đồ thị . 20
    Hình 2.1. Đồ thị ̅ . 23
    Hình 2.2. Đồ thị ̅ . . 24
    Hình 2.3. Đồ thị Dạng 1, Định lý 2.3. 25
    Hình 2.4. Đồ thị Dạng 2, Định lý 2.3. 26
    Hình 2.5. Đồ thị Dạng 3, Định lý 2.3. 26
    Hình 2.6. Minh họa cho chứng minh phần c) Mệnh đề 2.3. 30
    Hình 2.7. Minh họa cho chứng minh Mệnh đề 2.4. . 31
    Hình 2.8. Đồ thị trong phần chứng minh I, Định lý 2.3. 33
    Hình 2.9. Minh họa cho Trường hợp 1, phần chứng minh II, Định lý 2.3. . 34
    Hình 2.10. Minh họa cho Trường hợp 2, phần chứng minh II, Định lý 2.3. . 35
    Hình 2.11. Minh họa cho Trường hợp 2.1, phần chứng minh II, Định lý 2.3. 36
    Hình 2.12. Minh họa đỉnh kề với và , Trường hợp 2.1. 36
    Hình 2.13. Đồ thị trong phần chứng minh Trường hợp 2.1, Định lý 2.3. 37
    Hình 2.14. Minh họa cho chứng minh Khẳng định 2.9. 37
    Hình 2.15. Minh họa cho chứng minh Khẳng định 2.10. 38
    Hình 2.16. Minh họa cho chứng minh Khẳng định 2.12. 39
    Hình 2.17. Minh họa cho chứng minh Khẳng định 2.13. 40
    Hình 2.18. Đồ thị trong phần chứng minh Trường hợp 2.2, Định lý 2.3. 41
    Hình 2.19. Minh họa cho Trường hợp 2.3, phần chứng minh II, Định lý 2.3. 41
    Hình 2.20. Minh họa cho Trường hợp 3, phần chứng minh II, Định lý 2.3. . 42
    Hình 2.21. Minh họa cho chứng minh Khẳng định 2.16. 43
    Hình 2.22. Minh họa cho chứng minh Khẳng định 2.18. 43
    Hình 2.23. Minh họa cho chứng minh Khẳng định 2.20. 44
    Hình 2.24. Minh họa cho chứng minh Khẳng định 2.21. 45
    Hình 2.25. Minh họa cho chứng minh Khẳng định 2.24. 46
    Hình 2.26. Đồ thị trong phần chứng minh Trường hợp 3.2, Định lý 2.3. 47 viii
    Hình 2.27. Minh họa cho Trường hợp 3.3, phần chứng minh II, Định lý 2.3. 48
    Hình 3.1. Mở rộng chu trình theo trường hợp thứ 2 và 3 của Thuật toán 3.2. . 58
    Hình 3.2. Một số chương trình tìm chu trình Hamilton khác (nguồn [44]) . 60
    Hình 3.3. Sơ đồ thuật toán xác định chu trình Hamilton sử dụng bao đóng đồ thị . 61
    Hình 3.4. Sơ đồ khối thực hiện chương trình 62
    Hình 3.5. Biểu đồ thời gian chạy Chương trình 1 và Chương trình 2 theo số đỉnh . 64
    Hình 3.6. Chu trình ban đầu và vòng lặp mở rộng . 65
    Hình 3.7. Biểu đồ thời gian chạy Chương trình 2 trên đồ thị S3-2000 theo độ dài chu trình
    khởi tạo ban đầu. 68
    Hình 4.1. Minh họa việc thiết lập các đỉnh trên . . 72
    Hình 4.2. Minh họa Trường hợp 1, Bổ đề 4.2. 74
    Hình 4.3. Minh họa cho chứng minh Bổ đề 4.3. 74
    Hình 4.4. Minh họa cho chứng minh Bổ đề 4.4. 75
    Hình 4.5. Minh họa cho chứng minh Bổ đề 4.5. 75
    Hình 4.6. Minh họa cho chứng minh Bổ đề 4.6. 76
    Hình 4.7. Minh họa cho chứng minh Bổ đề 4.7. 76
    Hình 4.8. Minh họa cho chứng minh Bổ đề 4.9. 77
    Hình 4.9. Minh họa cho chứng minh Bổ đề 4.10. 78
    Hình 4.10. Minh họa cho chứng minh Khẳng định 4.1. 79
    Hình 4.11. Minh họa cho chứng minh Khẳng định 4.2. 79
    Hình 4.12. Minh họa cho chứng minh Khẳng định 4.5. 81
    Hình 4.13. Minh họa cho chứng minh Khẳng định 4.7. 81
    Hình 4.14. Minh họa cho chứng minh Khẳng định 4.8. 82
    Hình 4.15. Minh họa cho Trường hợp 2.1. 84
    Hình 4.16. Minh họa cho chứng minh Khẳng định 4.11. 85
    Hình 4.17. Minh họa cho chứng minh Khẳng định 4.12. 85
    Hình 4.18. Minh họa cho chứng minh Mệnh đề 4.3. . 87
    Hình 4.19. Minh họa cho chứng minh Khẳng định 4.19. 88
    Hình 4.20. Minh họa cho chứng minh Khẳng định 4.21. 89
    Hình 4.21. Minh họa cho chứng minh Mệnh đề 4.4. . 90

    ix
    Danh mục bảng
    Bảng 1.1. Một số thuật toán Backtrack và Heuristic xác định chu trình Hamilton . 14
    Bảng 3.1. Các chương trình thực nghiệm xác định chu trình Hamilton 62
    Bảng 3.2. Danh sách các đồ thị được tiến hành thực nghiệm 63
    Bảng 3.3. Thống kê thời gian chạy chương trình khi sử dụng Thuật toán 1.1 64
    Bảng 3.4. Tổng hợp thời gian chạy Chương trình 1 trước và sau khi cải tiến. 67
    Bảng 3.5. Tổng hợp thời gian chạy Chương trình 2 trước và sau khi cải tiến. 67
    Bảng 3.6. Thống kê thời gian chạy Chương trình 2 trên đồ thị S3-2000 theo độ dài chu
    trình khởi tạo ban đầu. . 68


    1
    MỞ ĐẦU
    Các vấn đề của lý thuyết đồ thị đã có từ vài trăm năm trước (năm 1736 với bài
    toán 7 cây cầu ở thành phố Konigsber) nhưng phải tới vài chục năm gần đây, theo
    cùng sự phát triển của công nghệ thông tin, thì lý thuyết đồ thị mới thực sự phát
    triển mạnh mẽ không ngừng cả về chiều sâu cũng như chiều rộng. Sự phát triển của
    lý thuyết đồ thị gắn liền với những tên tuổi các nhà toán học lớn như Euler, Gauss,
    Hamilton, Erdos . Một trong những lý do khiến lý thuyết đồ thị phát triển mạnh mẽ
    như vậy là vì lý thuyết đồ thị khá gần gũi với thực tế và có những ứng dụng sâu
    rộng trong công nghệ thông tin và nhiều ngành khoa học khác.
    Vấn đề chu trình là một vấn đề trung tâm của lý thuyết đồ thị và đã có rất
    nhiều công trình nghiên cứu tới vấn đề này, đặc biệt là chu trình Hamilton với
    khoảng 400 bài báo khoa học được đăng tải trên các tạp chí khoa học quốc tế có uy
    tín hàng đầu trong vòng 20 năm gần đây [25], [26], [27]. Hiện nay, các nghiên cứu
    về chu trình nói chung và chu trình Hamilton rộng trên nhiều khía cạnh, trong đó
    tập trung chủ yếu tới bậc của đỉnh; ngoài ra còn nghiên cứu trên các đồ thị 1-tough,
    đồ thị path-tough, đồ thị có tập láng giềng lớn, đồ thị phẳng, đồ thị ngẫu nhiên, đồ
    thị lưỡng phân và chu trình dài nhất, chu trình Dominating . Tại Việt Nam, một số
    tác giả cũng đã tập trung nghiên cứu về chu trình Hamilton trên các lớp đồ thị khác
    nhau, chẳng hạn như Ngô Đắc Tân nghiên cứu trên lớp đồ thị split và cubic, Vũ
    Đình Hòa nghiên cứu trên lớp đồ thị 1-tough có tổng bậc lớn
    Chu trình Hamilton có nhiều ứng dụng trong thực tế, ví dụ như trong bài toán
    người bán hàng, lập kế hoạch, hay trong thiết kế vi mạch, thiết kế đường truyền
    trong mạng Bài toán (xác định sự tồn tại của chu trình Hamilton trong đồ thị)
    được biết là bài toán [23] nên trong trường hợp tổng quát sẽ không có thuật
    toán tốt (thời gian đa thức) để giải nó. Do đó, việc tìm ra được các trường hợp thuộc
    lớp của bài toán cũng như việc thiết kế được thuật toán thời gian đa thức để
    xác định được chu trình Hamilton có ý nghĩa hết sức quan trọng.
    Các nghiên cứu hiện nay hầu hết là dựa trên những lớp đồ thị đặc biệt và tập
    trung vào việc chỉ ra sự tồn tại của chu trình Hamilton trong những lớp đồ thị đó.
    Có rất nhiều lớp đồ thị được xét tới, trong đó phần lớn các lớp đồ thị này được xác
    định theo điều kiện tổng bậc (của đỉnh) đủ lớn [15], [17], [18], [20], [22], [29],
    [30], [31], [36] . Một số tác giả nghiên cứu độ phức tạp của bài toán [3], [15],
    [23], [34], [37], hoặc đánh giá số lượng chu trình Hamilton [14] Một số khác 2
    nghiên cứu đến việc thiết kế các thuật toán để xác định chu trình Hamilton, trong đó
    có các thuật toán Backtrack, Heuristic và các thuật toán thời gian đa thức áp dụng
    cho những lớp đồ thị đặc biệt [5], [12], [22], [28], [38], [44]
    Trong [15] (Định lý 16), các tác giả đã đánh giá độ phức tạp của bài toán
    với lớp đồ thị thỏa mãn
    vẫn còn là bài toán với mọi . Có
    thể nói rằng kết quả này là tiền đề cho nghiên cứu về chu trình Hamilton của tác giả
    trong luận án. Thêm vào đó, một số kết quả trong [11], [17], [32], [36] đã khẳng
    định sự tồn tại của chu trình Hamilton trong các lớp đồ thị được xác định theo điều
    kiện của tổng bậc và đủ lớn, tuy nhiên các lớp đồ thị được xác định
    theo điều kiện và là chưa có thuật toán xác định chu trình Hamilton.
    Cùng với chu trình Hamilton, chu trình dài nhất trong đồ thị cũng được tập
    trung nghiên cứu tới và có nhiều kết quả đối với chu trình dài được áp dụng cho
    việc chứng minh sự tồn tại cũng như thiết kế thuật toán để xác định chu trình
    Hamilton. Trong bài báo [8], các tác giả D. Bauer, G. Fan, H. J. Veldman đã đưa ra
    một Giả thuyết đánh giá độ dài chu trình dài nhất theo giá trị mà cho tới nay
    vẫn chưa có chứng minh thỏa đáng nào cho Giả thuyết này.
    Mục tiêu nghiên cứu của luận án là:
     Nghiên cứu bài toán trên các lớp đồ thị có tổng bậc và lớn, trong
    đó tập trung vào trường hợp .
     Đánh giá độ phức tạp của bài toán theo một tham số . Xác định để
    bài toán chuyển từ lớp sang lớp .
     Xây dựng thuật toán thời gian đa thức để xác định chu trình Hamilton
    trong một số lớp đồ thị đã khảo sát.
     Đánh giá tính hiệu quả và khả thi của các thuật toán bằng chương trình
    thực nghiệm trên các đồ thị lớn.
     Đánh giá độ dài của chu trình dài nhất trong lớp đồ thị 1-tough với .
    Kết cấu của luận án gồm: phần mở đầu, 4 chương và phần kết luận.
    Chương 1: Tổng quan về chu trình trong đồ thị.
    Giới thiệu một số vấn đề cơ bản của lý thuyết đồ thị, các khái niệm, các quy
    ước và ký hiệu sử dụng trong luận án. Tiếp đến, giới thiệu tổng quan về vấn đề chu
    trình trong đồ thị, trọng tâm là chu trình Hamilton. Ngoài ra, tác giả đưa ra một số 3
    kết quả nghiên cứu về bao đóng của đồ thị để sử dụng trong một số chứng minh của
    luận án.
    Chương 2: Một số lớp đa thức của bài toán .
    Chương này nghiên cứu về chu trình Hamilton theo hai bài toán và (với nguyên dương, số thực là tham số) như sau:
    Instance: Đồ thị thỏa mãn
    .
    Question: có là đồ thị Hamilton?
    Instance: Đồ thị thỏa mãn .
    Question: có là đồ thị Hamilton?
    Tác giả tập trung vào việc đánh giá độ phức tạp của bài toán theo tham số để
    tìm ra các lớp đa thức của bài toán .
    Chương 3: Thuật toán đa thức xác định chu trình Hamilton trong đồ thị và
    .
    Chương này sẽ thiết kế thuật toán đa thức xác định chu trình Hamilton cho các
    lớp đồ thị và
    , sau đó tác giả tiến hành thực nghiệm trên các
    đồ thị lớn (hàng nghìn đỉnh) để cho thấy tính hiệu quả và khả thi thực hiện của các
    thuật toán. Thêm vào đó, tác giả đưa ra một số đề xuất mới để làm tăng hiệu năng
    thực hiện của thuật toán.
    Chương 4: Đánh giá độ dài chu trình dài nhất trong đồ thị 1-tough với .
    Chương này của luận án sẽ đưa ra một chứng minh cho Giả thuyết của các tác
    giả Bauer, Fan, Veldman trong [8] về cận dưới của độ dài chu trình dài nhất rằng:
    Nếu là đồ thị 1-tough và thì .
    Giả thuyết trên cũng đã được một số tác giả khác quan tâm và tìm cách chứng
    minh, tuy nhiên các chứng minh đưa ra đều chưa thỏa đáng. Cho đến nay vẫn chưa
    có chứng minh đúng nào cho Giả thuyết này và đây vẫn là vấn đề mở.
    4
    CHƯƠNG 1. TỔNG QUAN VỀ CHU TRÌNH TRONG ĐỒ THỊ
    1.1. Một số khái niệm và quy ước
    1.1.1. Các khái niệm cơ bản của lý thuyết đồ thị
    Trong luận án này, ta chỉ xét tới các đồ thị hữu hạn, đơn, vô hướng và không
    có trọng số. Các khái niệm, ký hiệu chủ yếu tham khảo trong [16].
    Một đồ thị là một cặp , trong đó là tập đỉnh và [ ] là tập
    cạnh. Số đỉnh của đồ thị gọi là bậc của đồ thị , được viết là | | . Trong luận án
    luôn sử dụng ký hiệu là số đỉnh của đồ thị .
    Hai đỉnh và được gọi là kề nhau nếu là một cạnh của đồ thị . Nếu mọi
    đỉnh của kề nhau từng đôi một thì được gọi là đồ thị đầy đủ. Một đồ thị đầy đủ
    có đỉnh được ký hiệu là . Tập đỉnh con là độc lập nếu mọi cặp đỉnh
    thuộc đều không kề nhau. Ký hiệu (hay viết đơn giản là nếu không xảy ra
    sự hiểu lầm) là số phần tử của tập độc lập lớn nhất trong và được gọi là số ổn
    định trong của .
    Với đỉnh , ta ký hiệu (hay viết đơn giản là ) là tập láng
    giềng của trong , . Bậc của đỉnh , ký hiệu bởi
    (hay viết đơn giản là ) là số phần tử của , | | .
    Đồ thị được gọi là đồ thị con của đồ thị , ký hiệu là , nếu
    và . Với , ta ký hiệu là đồ thị con thu được từ đồ
    thị bằng cách loại bỏ tất cả các đỉnh thuộc và các cạnh nối tới các đỉnh đó.
    Ngoài ra, đồ thị con sinh của trên tập đỉnh , ký hiệu là [ ] , được định nghĩa là
    đồ thị trên tập đỉnh và bảo toàn tập cạnh, tức là hai đỉnh trong [ ] kề nhau khi và
    chỉ khi chúng kề nhau trong . Trong luận án thường viết đơn giản là thay cho [ ] .
    Với thì ta ký hiệu là tập hợp các đỉnh thuộc và có láng
    giềng thuộc , tức là: . Ta cũng thường
    viết thay cho nếu không xảy ra sự hiểu lầm.
    Đồ thị (hoặc ) và (hoặc ) tương ứng được
    ký hiệu là đồ thị thu được từ đồ thị bằng cách loại bỏ hoặc bổ sung cạnh nối giữa
    hai đỉnh và . 5
    Đồ thị bù của , ký hiệu bởi ̅ , là đồ thị có tập đỉnh là và tập cạnh là [ ] .
    Hai đồ thị và được gọi là rời nhau nếu . Với số
    nguyên dương cho trước và đồ thị đôi một rời nhau , phép kết
    nối đồ thị này là một đồ thị được ký hiệu bởi với tập đỉnh là và tập cạnh là
    với mọi . Ví dụ, , hay với số nguyên thì là đồ thị được biểu diễn như trong Hình 1.1.

    Hình 1.1. Đồ thị .
    Khái niệm đường đi và chu trình trong luận án là đơn, nghĩa là chúng chỉ đi
    qua các đỉnh không quá một lần. Một đường đi (đơn) là một đồ
    thị con không rỗng có cấu trúc: và .
    trong đó, với mọi . Các đỉnh được nối bởi , và gọi là các
    đỉnh cuối; các đỉnh gọi là các đỉnh trong của . Số cạnh của đường đi
    gọi là độ dài của nó, ký hiệu là .
    Nếu là một đường đi và thì được
    gọi là một chu trình, khi đó chu trình được viết như sau:
    . Số cạnh của chu trình gọi là độ dài của nó, ký hiệu là .
    Chu trình có độ dài được ký hiệu là . Độ dài của chu trình dài nhất trong đồ thị được gọi là chu vi, ký hiệu là .
    Đồ thị được gọi là liên thông nếu hai đỉnh bất kỳ của nó được nối với nhau
    bởi một đường đi trong . Nếu không liên thông thì sẽ bao gồm các đồ thị con
    liên thông và gọi là các thành phần liên thông của . Ký hiệu số thành phần liên 6
    thông của là . Đỉnh được gọi là đỉnh cắt nếu . Tập đỉnh được gọi là tập đỉnh cắt nếu .
    Đồ thị được gọi là -liên thông ( ) nếu | | và liên
    thông với mọi tập mà | | . Số nguyên lớn nhất thỏa mãn là -liên
    thông gọi là chỉ số liên thông của , ký hiệu là .
    Khoảng cách giữa hai đỉnh , ký hiệu là , được định nghĩa như sau:
    nếu cùng thuộc một thành phần liên thông thì là độ dài của đường đi
    ngắn nhất nối hai đỉnh đó, ngược lại thì .
    Với số nguyên dương , ta định nghĩa như sau: là tập đỉnh độc lập ,
    Trường hợp thì đặt . Với và chỉ xét tới các
    cặp đỉnh có khoảng cách 2, ta định nghĩa: ,
    Trong luận án thường viết lần lượt thay cho và nếu không
    xảy ra sự hiểu lầm. Nếu không là đồ thị đầy đủ, ta định nghĩa giá trị và như sau: | | , | | .
    Trường hợp là đồ thị đầy đủ thì đặt . Ta cũng
    thường viết đơn giản là lần lượt thay cho và .
    Đồ thị được gọi là -tough ( ) nếu với mọi tập đỉnh cắt thì
    | |
    . Đồ thị 1-tough cũng thường được gọi là đồ thị tough.
    Lưu ý 1.1.
     Việc kiểm tra tính liên thông và tìm các thành phần liên thông của đồ thị chỉ cần
    một thuật toán đa thức không quá phép toán thực hiện [1].
     Việc tìm một đường đi giữa hai đỉnh của đồ thị cũng chỉ cần một thuật toán đa
    thức không quá phép toán thực hiện [1]. Nếu sử dụng phương pháp tìm
    kiếm theo chiều rộng (BFS) thì đường đi tìm được sẽ là đường đi ngắn nhất. 7
     Mọi đồ thị tough đều là đồ thị 2-liên thông nhưng điều ngược lại không đúng,
    chẳng hạn như đồ thị ̅ (với nguyên dương) là đồ thị 2-liên thông
    nhưng không là đồ thị tough.
     Việc nhận biết một đồ thị có là 2-liên thông hay không chỉ cần một thuật toán đa
    thức không quá phép toán thực hiện nên đây là vấn đề thuộc lớp . Tuy
    nhiên, việc nhận biết một đồ thị có là tough hay không lại là vấn đề thuộc lớp [6].
    1.1.2. Một số ký hiệu và quy ước
    Các ký hiệu khi viết không kèm theo đồ thị tường minh thì hiểu mặc định là
    đồ thị . Ví dụ, viết tương ứng thay cho .
    Giả sử là một đường đi và là một chu trình của đồ thị . Trong luận án,
    đôi khi ta có thể xem như là một tập đỉnh con của (tương ứng thay cho ).
    Một đường đi là mở rộng (theo tập đỉnh) của đường đi nếu
    . Tương tự, một chu trình là mở rộng của chu trình nếu .
    Với , ta ký hiệu là đoạn đường chạy dọc theo từ đỉnh tới
    đỉnh . Như vậy, nếu là các đỉnh cuối của thì cũng chính là . Ngoài ra, | | quy ước là số đỉnh nằm trên đoạn đường con này.
    Giả sử chu trình . Ta quy định một chiều quay ⃗⃗⃗ theo thứ tự chỉ số các đỉnh và chỉ số các đỉnh được lấy theo . Với đỉnh , ký hiệu lần lượt là đỉnh liền trước và liền sau của theo chiều quay
    đã định. Với tập đỉnh thì , . Với số
    nguyên dương , ký hiệu và
    . Ta ký hiệu đoạn đường trên bắt đầu từ một đỉnh và kết thúc tại theo chiều quay đã quy định bởi ⃗⃗⃗ , đoạn đường đó theo chiều ngược lại
    ký hiệu là ⃖⃗⃗⃗ . Nếu là một thành phần liên thông của , ký hiệu là
    tập hợp các láng giềng của trên . Một dãy cung ngoại biên nối hai đỉnh trên là
    một đường đi có các đỉnh cuối là 2 đỉnh đó và các đỉnh trong thuộc . Đặc
    biệt, một cạnh nối 2 đỉnh không liền nhau trên cũng là một dãy cung ngoại biên.
    Đôi khi ta cũng thường không viết dấu phẩy (,) ngăn cách giữa các đỉnh của
    một chu trình hoặc một đường đi. Ví dụ, viết thay cho
    . 8
    1.2. Chu trình trong đồ thị 2-liên thông
    Trước hết, ta có một khẳng định quan trọng sau cho đồ thị 2-liên thông:
    Mệnh đề 1.1. Mọi đồ thị 2-liên thông đều có chu trình.
    Việc chứng minh Mệnh đề 1.1 là khá đơn giản và cũng đã được đề cập trong
    [16]. Có thể xây dựng thuật toán đa thức xác định một chu trình bất kỳ cho đồ thị 2-
    liên thông bằng cách là xuất phát từ một đường đi độ dài 1 (gồm 2 đỉnh kề nhau),
    sau đó ta sẽ liên tục mở rộng đường đi cho đến khi nào có đỉnh cuối thỏa mãn tính
    chất có láng giềng thuộc đoạn đường trước đó và | | (Hình 1.2). Khi đó,
    ta sẽ có chu trình gồm các đỉnh từ tới dọc theo đường , sau đó quay trở lại .

    Hình 1.2. Đường đi sau khi mở rộng đến đỉnh .
    Thuật toán 1.1. Xác định một chu trình trong đồ thị 2-liên thông
    Input: Đồ thị 2-liên thông .
    Output: Một chu trình của .
    Procedure Create_Cycle()
    Begin
    Tìm một cạnh ; ; ;
    While ( ) Do
    Begin
    Lấy là một đỉnh cuối của ;
    If and | | Then
    Else Begin
    Tìm một đỉnh ; ;
    End;
    End;
    End; 9
    Thuật toán trên là đúng đắn vì trong trường hợp đỉnh cuối không có láng
    giềng thuộc thì sẽ tồn tại một đỉnh và | | , vì nếu không
    thì và do đó đồ thị không 2-liên thông (khi ta loại bỏ đỉnh liền trước
    trên đoạn đường thì số thành phần liên thông của đồ thị sẽ lớn hơn 1). Thuật toán
    sẽ kết thúc sau không quá phép toán thực hiện.
    Nếu là một chu trình dài nhất của , ta có Bổ đề quan trọng sau:
    Bổ đề 1.1. Cho đồ thị 2-liên thông với đỉnh và là một chu trình dài nhất của , là một thành phần liên thông của . Nếu có không quá đỉnh thì :
    (a) .
    (b) Không có dãy cung ngoại biên nối hai đỉnh của hoặc .
    (c) Nếu với thì không có ⃗⃗⃗ sao cho đồng thời có . Tương tự, không có ⃗⃗⃗ sao cho đồng thời có .
    Việc chứng minh các phần (a), (b), (c) của Bổ đề 1.1 là đơn giản và đã trở
    thành chuẩn (luôn chứng minh bằng phản chứng và chỉ ra mâu thuẫn bằng cách mở
    rộng được chu trình ) nên ta không chứng minh lại ở đây. Với giả thiết là chu
    trình với không quá đỉnh, ta có kết quả sau:
    Bổ đề 1.2. Cho đồ thị 2-liên thông với đỉnh và là một chu trình của với
    không quá đỉnh, là một thành phần liên thông của . Nếu
    và là tập đỉnh độc lập thì với mọi và với mọi
    ta có: .
    Chứng minh. Có | | | | | | | | . Theo giả thiết
    suy ra | | | | | | | | | | | | , do đó
    | | | | | | | | | | | | . (Đpcm)
    1.3. Chu trình Hamilton
    Chu trình đi qua mọi đỉnh của đồ thị, mỗi đỉnh đi qua đúng một lần, gọi là chu
    trình Hamilton. Đồ thị có chu trình Hamilton được gọi là đồ thị Hamilton. Tương
    tự, đường đi qua mọi đỉnh của đồ thị, mỗi đỉnh đi qua đúng một lần, gọi là đường
    Hamilton và đồ thị có đường Hamilton gọi là đồ thị nửa Hamilton.

    Xem Thêm: Chu trình Hamilton và chu trình dài nhất trong một số lớp đồ thị có tổng bậc lớn
    Nội dung trên chỉ thể hiện một phần hoặc nhiều phần trích dẫn. Để có thể xem đầy đủ, chi tiết và đúng định dạng tài liệu, bạn vui lòng tải tài liệu. Hy vọng tài liệu Chu trình Hamilton và chu trình dài nhất trong một số lớp đồ thị có tổng bậc lớn sẽ giúp ích cho bạn.
    #1
  7. Đang tải dữ liệu...

    Chia sẻ link hay nhận ngay tiền thưởng
    Vui lòng Tải xuống để xem tài liệu đầy đủ.

    Gửi bình luận

    ♥ Tải tài liệu

social Thư Viện Tài Liệu

Từ khóa được tìm kiếm

Nobody landed on this page from a search engine, yet!

Quyền viết bài

  • Bạn Không thể gửi Chủ đề mới
  • Bạn Không thể Gửi trả lời
  • Bạn Không thể Gửi file đính kèm
  • Bạn Không thể Sửa bài viết của mình
  •  
DMCA.com Protection Status