Đồ Thị

PHÂN LOẠI BÀI TOÁN ĐỒ THỊ
1. LỜI MỞ ĐẦU 2
2. MỘT SỐ KHÁI NIỆM CƠ BẢN 2
2.1. cấu trúc đồ thị 2
2.2. Phép duyệt đồ thị 3
2.3. Đồ thị và hàm chi phí 4
2.4. Đồ thị và quan hệ 6
2.5. Cây và cây có gốc 8
2.6. Biểu diễn đồ thị và cây 10
3. TÌM HIỂU MỘT SỐ CÁCH PHÂN LOẠI BÀI TOÁN ĐỒ THỊ 11
3.1. Một số cách phân loại bài toán đồ thị 11
3.1.1. Phân loại theo chương trình khung của Bộ GD&ĐT 11
3.1.2. Phân loại theo logic lý thuyết đồ thị 12
3.1.3. Phân loại bài toán theo nhóm các thuật toán trên đồ thị 13
3.2. Nhận xét và lựa chọn của chúng tôi 14


1. LỜI MỞ ĐẦU
Bài toán trên đồ thị là một chủ đề truyền thống trong các kỳ thi HSG Quốc gia, Olympic Tin học Quốc tế và khu vực. Không những thế mà số lượng các bài toán đồ thị được đưa vào các đề thi chiếm tỷ lệ khá lớn.
2. MỘT SỐ KHÁI NIỆM CƠ BẢN
2.1. Cấu trúc đồ thị
Một cấu trúc đồ thị G(V,E) được xác định bởi một tập hữu hạn V gồm các đỉnh và tập hữu hạn E các liên kết mà mỗi liên kết nối một cặp đỉnh với nhau. Một liên kết là có hướng khi cặp đỉnh tương ứng là có thứ tự và liên kết là vô hướng khi cặp đỉnh không có thứ tự. Ta gọi liên kết không có thứ tự là cạnh và liên kết có thứ tự là cung.
Nếu E là tập cạnh (cung) có sự lặp lại ta gọi đồ thị đó là đa đồ thị, nếu không có cạnh lặp ta gọi đồ thị đó là đơn đồ thị như vậy có thể chia ra bốn loại đồ thị: đơn đồ thị vô hướng, đơn đồ thị có hướng, đa đồ thị vô hướng, đa đồ thị có hướng. Và với mỗi loại đồ thị này, thuật toán giải quyết các bài toán tương tự là khác nhau. Ví dụ với thủ tục hiển thị cấu trúc đồ thị dưới dạng ma trận liên thuộc g[][]. Với một cấu trúc cho trước từ tệp tin đầu vào dưới dạng danh sách cạnh (cung) ta có thể gán g[v][w] = 1 ứng với cung (v,w), nhưng với cạnh (v,w) thì cần phải gán g[v][w] = 1 và g[w][v] = 1. Với các liên kết (v,v) ta gọi là khuyên, và người ta thường chỉ cho phép khuyên có mặt trong đồ thị có hướng.


Hình 1: Minh họa đồ thị
2.2. Phép duyệt đồ thị
Ý tưởng "di chuyển" trong một cấu trúc đồ thị, đi từ một đỉnh tới một đỉnh khác qua cạnh (cung) nối giữa chúng là một trong những thao tác cơ bản khi làm việc với đồ thị và ta gọi đó là duyệt đồ thị. Ta gọi một dãy các đỉnh v0, v1, ..., vm của một đồ thị có hướng là đường đi độ dài m từ đỉnh v0 đến đỉnh vm, nếu cung (vi, vi+1)(E với i = 0,1,..., m-1. Khi v0 = vm ta gọi đường đi đó là một chu trình. Ta cũng gọi một dãy các đỉnh v0, v1, ..., vm của một đồ thị vô hướng là đường đi độ dài m từ đỉnh v0 đến đỉnh vm, nếu cạnh(vi, vi+1)(E và vi-1 ≠ vi+1 với i = 0,1,..., m-1. Khi v0 = vm ta gọi đường đi đó là một chu trình. Điều kiện vi-1 ≠ vi+1 là quan trọng nếu không sẽ xảy ra loại chu trình kiểu 1,2,1 hoặc 1,1, 2, 1 (với cạnh (1,2) của đồ thị).
Trong một đồ thị, nếu giữa hai đỉnh bất kỳ luôn có đường đi, ta nói đồ thị đó liên thông. Trong đồ thị có hướng, giữa hai đỉnh bất kỳ có ít nhất một đường đi theo một hướng nào đó, thì gọi là liên thông yếu. Khi một đồ thị không liên thông, nó sẽ được phân chia thành một số đồ thị con liên thông ta gọi chúng là những thành phần liên thông. Ngoài ra còn có các khái niệm đường đi không có đỉnh nào (hoặc cạnh nào) lặp lại. Đường đi mà mỗi cạnh (cung) chỉ xuất hiện đúng một lần gọi là đường đi Euler. Đường đi mà mỗi đỉnh chỉ xuất hiện đúng một lần gọi là đường đi Hamilton.
2.3. Đồ thị và hàm chi phí
Mỗi cấu