Luận văn tốt nghiệp - Một số vấn đề cơ bản của đồ thị

Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh này, các loại đồ thị khác nhau được phân biệt bởi kiểu và số lượng cạnh nối hai đỉnh nào đó của đồ thị. Giả sử X là tập hữu hạn, không rỗng các phần tử nào đó và U X X. Bộ G = được gọi là đồ thị hữu hạn. Mỗi phần tử x X gọi là một đỉnh và mỗi phần tử u = (x,y) U gọi là một cạnh của đồ thị G = . Xét một...
Nội dung trích xuất từ tài liệu:
Luận văn tốt nghiệp - Một số vấn đề cơ bản của đồ thịLuận văn tốt nghiệp Chương 1 MỘT SỐ VẤN ĐỀ CƠ BẢN CỦA ĐỒ THỊ I. CÁC ĐỊNH NGHĨA ĐỒ THỊ 1. Định nghĩa đồ thị Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh này, các loại đồ thị khác nhau được phân biệt bởi kiểu và số lượng cạnh nối hai đỉnh nào đó của đồ thị. Giả sử X là tập hữu hạn, không rỗng các phần tử nào đó và U X X. Bộ G = được gọi là đồ thị hữu hạn. Mỗi phần tử x X gọi là một đỉnh và mỗi phần tử u = (x,y) U gọi là một cạnh của đồ thị G = . Xét một cạnh u U khi đó tồn tại 2 đỉnh x, y X sao cho u = (x, y), ta nói rằng x nối với y hoặc x và y thuộc u. x u y - Nếu cạnh u = (x, y) mà x và y là hai đỉnh phân biệt thì ta nói x, y là hai đỉnh kề nhau. - Nếu u = (x, x) thì u là cạnh có hai đỉnh trùng nhau ta gọi đó là một khuyên. - Nếu u = (x, y) mà x,y là cặp đỉnh có phân biệt thứ tự hay có hướng từ x đến y thì u là một cung, khi đó x là gốc còn y là ngọn hoặc x là đỉnh ra, y là đỉnh vào. - Khi giữa cặp đỉnh (x, y) có nhiều hơn một cạnh thì ta nói những cạnh cùng cặp đỉnh là những cạnh song song hay là cạnh bội y x y x y a) b) c) a. Tại đỉnh y có một khuyên b. Một cung có hướng từ x sang y c. Cặp đỉnh (x, y) có 2 cạnh song song Hình 1.1 Trong thực tế ta có thể gặp nhiều vấn đề mà có thể dùng mô hình đồ thị để biểu diễn, như sơ đồ một mạng máy tính, sơ đồ mạng lưới giao thông, sơ đồ thi công một công trình. 9Luận văn tốt nghiệp Ví dụ: Xét một mạng máy tính, có thể biểu diễn mạng này bằng một mô hình đồ thị, trong đó mỗi máy là một đỉnh, giữa các máy được nối với nhau bằng các dây truyền, chúng tương ứng là các cạnh của đồ thị. Một mô hình mạng máy tính như hình 1.2 trong đó có các máy tính A, B, C, D tương ứng là các đỉnh, giữa 2 máy được nối trực tiếp với nhau thì tương ứng với 1 cặp đỉnh kề nhau. A B C D Hình 1.2 Ví dụ về một đồ thị 2. Đồ thị đơn Đồ thị G = được gọi là đồ thị đơn nếu giữa hai đỉnh bất kỳ được nối với nhau bởi không quá một cạnh (cung), tức là đồ thị không có cạnh bội, không có khuyên. Hình 1.2 là một ví dụ về đồ thị đơn 3. Đa đồ thị Đồ thị G = được gọi là đa đồ thị nếu nó có ít nhất một cặp đỉnh được nối với nhau bởi hai cạnh (hai cung) trở lên. 4. Giả đồ thị Là đồ thị có ít nhất một khuyên, có thể chứa cạnh bội, cạnh đơn. Tóm lại đây là loại đồ thị tổng quát nhất. A B A B C C D D a) b) Hình 1.3 a. Đa đồ thị b. Giả đồ thị II. CÁC LOẠI ĐỒ THỊ 1. Đồ thị vô hướng 10Luận văn tốt nghiệp Đồ thị G= được gọi là đồ thị vô hướng nếu tất cả các cạnh e U mà cặp đỉnh thuộc nó e = (x,y) X không phân biệt thứ tự. Đồ thị vô hướng là đồ thị không có bất kỳ một cung nào. Ví dụ: như hình 1.3.a là biểu diễn của một đồ thị vô hướng. 2. Đồ thị có hướng Đồ thị G = được gọi là đồ thị có hướng nếu tất cả các cạnh e U mà cặp đỉnh thuộc nó e = (x, y) X có phân biệt thứ tự. Đồ thị có hướng là đồ thị mà mọi e = (x, y) X đều là cung. C A B Hình 2.1 Đồ thị có hướng 3. Đồ thị hỗn hợp Đồ thị G= vừa có cạnh vô hướng, vừa có cạnh có hướng thì nó được gọi là đồ thị hỗn hợp, loại đồ thị này rất ít khi được dùng tới. Chú ý rằng vấn đề phân chia đồ thị và các thuật ngữ về đồ thị chỉ mang tính tương đối, hiện nay vẫn còn chưa mang tính thống nhất chuẩn trên nhiều tài liệu. III. MỘT SỐ KHÁI NIỆM VÀ TÍNH CHẤT CƠ BẢN CỦA ĐỒ THỊ 1. Bậc đồ thị 1.1 Bậc đồ thị vô hướng Cho đồ thị vô hướng G = . Xét 1 đỉnh x X đặt m(x) là số cạnh thuộc đỉnh x khi đó m(x) được gọi là bậc của đỉnh x. Nếu x có một khuyên thì m(x) được cộng thêm 2. x x m(x) = 3 m(x) = 2 - Nếu m(x) = 0 thì đỉnh x được gọi là đỉnh cô lập - Nếu m(x) = 1 thì đỉnh x được gọi là đỉnh treo Ta đặt m(G) = ∑ m(x) x∈X thì m(G) được gọi là bậc của đồ thị vô hướng G = 11Luận văn tốt nghiệp 1.2 Bậc đồ thị có hướng Cho đồ thị có hướng G= xét 1 đỉnh x X, ta ký hiệu m+(x) là số các cung vào của đỉnh x, còn m-(x) là số các cung ra khỏi x. Khi đó ta gọi m+(x) là bậc vào của đỉnh x còn ...