Luận văn tốt nghiệp - Sự ổn định và tô màu đồ thị

Số ổn định trong Cho đồ thị vô hướng G = và A X. a) Tập A gọi là tập ổn định trong của đồ thị nếu hai đỉnh bất kỳ trong A là không kề nhau, tức là không có một cạnh nào của đồ thị chứa hai đỉnh x và y. b) Tập A gọi là tập ổn định trong cực đại của đồ thị G nếu: - A là tập ổn định trong - Nếu thêm vào A một đỉnh ngoài A thì A không phải là ổn định trong. Gọi L là tập hợp...
Nội dung trích xuất từ tài liệu:
Luận văn tốt nghiệp - Sự ổn định và tô màu đồ thị Luận văn tốt nghiệp Chương 2 SỐ ỔN ĐỊNH VÀ TÔ MÀU ĐỒ THỊ I. SỐ ỔN ĐỊNH TRONG, SỐ ỔN ĐỊNH NGOÀI, NHÂN ĐỒ THỊ 1. Số ổn định trong Cho đồ thị vô hướng G = và A X. a) Tập A gọi là tập ổn định trong của đồ thị nếu hai đỉnh bất kỳ trong A là không kề nhau, tức là không có một cạnh nào của đồ thị chứa hai đỉnh x và y. b) Tập A gọi là tập ổn định trong cực đại của đồ thị G nếu: - A là tập ổn định trong - Nếu thêm vào A một đỉnh ngoài A thì A không phải là ổn định trong. Gọi L là tập hợp các tập ổn đỉnh trong của của G = . Khi đó ký hiệu (G) = Max { A / A L} và (G) được gọi là số ổn định trong của đồ thị G. Như vậy (G) là số phần tử của 1 tập ổn định trong cực đại nào đó. 2. Số ổn định ngoài Cho đồ thị vô hướng G = và B X a) Tập B được gọi là tập ổn định ngoài của đồ thị nếu với mỗi phần tử y X \ B đều tồn tại x B sao cho có cạnh nối giữa x và y, B còn được gọi là tập thống trị của đồ thị. b) Tập B được gọi là tập ổn định ngoài cực tiểu nếu: - B là tập ổn định ngoài - Nếu bớt 1 phần tử bất kỳ của B thị B không còn là tập ổn định ngoài. Gọi M là tập của tất cả các tập ổn định ngoài của G = . Khi đó ký hiệu (G) = Min { / B M} và (G) được gọi là số ổn định ngoài của đồ thị G. Đối với các tập ổn định ngoài, ta thường quan tâm đến tập ổn định ngoài có số phần tử ít nhất vì lực lượng của nó liên quan tới số ổn định ngoài của đồ thị. 3. Nhân đồ thị Cho đồ thị vô hướng G = . Nếu tập A X vừa là tập ổn định trong vừa là tập ổn định ngoài của đồ thị G thị A được gọi là nhân của đồ thị. Đối với nhân của đồ thị, ta quan tâm tới nhân có số phần tử ít nhất. 24 Luận văn tốt nghiệp 4 1 7 2 6 5 3 Hình 1.1 Ví dụ: xét đồ thị hình 1.1 ta có: Các tập ổn định trong của đồ thị là: A1 = {1, 5, 7} A6 = {2, 6, 7} A2 = {1, 6, 7} A7 = {4, 5, 7} A3 = {3, 5, 7} A8 = {4, 6, 7} A4 = {3, 6, 7} A9 = {2, 4, 5, 7} A5 = {2, 5, 7} A10 = {2, 4, 6, 7} Tập A9 và A10 là các tập ổn định trong cực đại có 4 phần tử vì nếu thêm 1 đỉnh mới nữa vào các tập đó thì chúng không còn là tập ổn định trong nữa. Số ổn định trong của đồ thị trên là (G) = 4. Với đồ thị trên các tập ổn định ngoài cực tiểu là B1 = A1; B2 = A2; B3 = A3; B4 = A4. Vì các tập này nếu bớt đi 1 trong các phần tử của chúng thì tập còn lại không là tập ổn định ngoài nữa. Số ổn đỉnh ngoài của đồ thị này là (G) = 3. Nhân của đồ thị trên là B1, B2, B3, B4 vì các tập này là tập ổn định trong và đồng thời cũng là tập ổn định ngoài. 4. Các thuật toán tìm các tập ổn định trong cực đại, ổn định ngoài cực tiểu. 4.1 Thuật toán tìm số ổn định trong - Bước 1: Tìm các tập ổn định trong có 2 phần tử bằng cách xét tất cả tổ hợp chập 2 của n phần tử (n số các đỉnh), kiểm tra những tập nào mà phần tử của ma trận kề tương ứng bằng 0 thì tập đó là ổn định trong. - Bước 2: Duyệt từng tập có 2 phần tử và bổ sung thêm phần tử thứ 3 và kiểm tra từng cặp như bước 1, tập nào thoả ta được tập ổn định trong 3 phần tử. ........ - Bước k: Giả sử đã tìm được m tập con ổn định trong có k + 1 phần tử + Duyệt từng tập và bổ sung vào các tập đó thêm 1 phần tử + Nếu không có tập nào bổ sung được nữa thì dừng 4.2 Thuật toán tìm số ổn định ngoài Xét G = với X = {x1, x2,....,xn} 25 Luận văn tốt nghiệp - Bước 1: Xác định các tập xi) i = 1..n với xi) = {xi và các đỉnh kề với xi} - Bước 2: Từ các tập x1), x2),..., xn) ta tìm tập B B = {xk1 , xk2 ,..., xkm} sao cho xk1) xk2) ... xkm) = X Khi đó B là tập ổn định ngoài cực tiểu 5. Ứng dụng đồ thị trong lập trình chơi cờ Ca rô Ta xét một ứng dụng của đồ thị cho bài toán lập trình chơi cờ Ca rô trên máy tính. Cờ carô là loại cờ mà rất nhiều bạn trẻ đặc biệt giới sinh viên học sinh ưa thích. Quy tắc và cách thức chơi đơn giản, nhưng nó thực sự là bài toán tin rất hay, là bài lập trình thể hiện nhiều tư duy thuật toán, cũng như cơ sở về trí tuệ nhân tạo cho việc lập trình trò chơi giữa người và máy. Ta xét ứng dụng của đồ thị phục vụ cho bài toán lập trình trò chơi Carô. Xét một thế cờ Carô như hình 1.2.a o1 x1 0 1 0 2 x2 x4 A = 0 0 2 2 x3 0 2 0 0 1 0 0 1 o2 o3 a) b) Hình 1.2 Cấu trúc dữ liệu cho thế cờ này có thể dùng bảng ma trận như hình 1.2.b, với 0 là vùng trắng, 1 là quân o và 2 là quân x. Nhưng như vậy việc tính toán sẽ rất khó khăn, ta c ...