zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

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

Chia sẻ: Vo Kiem | Ngày: | Loại File: PDF | Số trang:11

Báo xấu

201
lượt xem 22
download

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

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...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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ó thể dùng đồ thị làm cấu trúc dữ liệu cho thế cờ Carô, khi đó việc tính toán sẽ dễ dàng đi và tận dụng những tính chất đã nghiên cứu về đồ thị thì bài toán lập trình trò chơi carô sẽ trở nên thuận lợi hơn nhiều. a) Mô hình bằng đồ thị theo vị trí liền kề Ta xây dựng 1 đơn đồ thị theo nguyên tắc sau - Mỗi 1 quân "x" hoặc quân "o" thì tương ứng với một đỉnh - Hai đỉnh là kề nhau nếu tương ứng với 2 quân ở vị trí liên tiếp nhau - Mỗi một cạnh được gán một nhãn, nhãn cho biết 2 đỉnh kề nhau là kề đứng, kề chéo hay là kề ngang trong thế cờ. Ta gán tên nhãn như sau: thẳng ngang nhãn là 1, thẳng chéo trái là 2, thẳng dọc nhãn là 3, thẳng chéo phải là 4 (xem hình 1.3.a). 26
Luận văn tốt nghiệp x1 o1 4 2 3 2 3 4 x2 1 x4 1 4 x3 4 o3 o2 a) b) Hình 1.3 a) Cách đánh nhãn b) Đồ thị cho thế cờ hình 1.2.a Ví dụ đồ thị như hình 1.3.b là thể hiện cho thế cờ hình 1.2.a Trong luật chơi cờ carô nếu quân "x" đi trước thì ngay sau đó là quân "o" đi sau, tiếp tục lại "x" rồi lại "o"... Chính điều này ta có thể coi những quân "x" tương ứng là những đỉnh số lẻ, quân "o" tương ứng những đỉnh số chẵn hoặc ngược lại. Trong 1 thế cờ Carô nếu tồn tại 1 dãy 5 quân liên tiếp của "x" hoặc "o" được sắp thẳng hàng ngang, thẳng hàng dọc hoặc thẳng hàng chéo thì thắng. Với đồ thị nếu tồn tại một đường đi các cạnh cùng nhãn gồm 5 đỉnh số lẻ, hoặc số chẵn thì thế cờ thắng cho tương ứng quân "x" hoặc quân "o". Xét đồ thị hinh 1.3.b đã có 1 đường đi cùng nhãn 4 gồm 3 đỉnh cùng quân x1, x2, x3. Nếu ta thêm 1 đỉnh x6 kề với đỉnh o2 sao cho cạnh (o2, x6) có nhãn 4, sau cùng ta thay đỉnh o2 bằng đỉnh x5 thì bây giờ ta có 1 đường đi cùng nhãn 4 gồm 5 đỉnh quân "x" (x1, x2, x3, x5, x6) và ta có 1 thế cờ thắng cho quân x. Nhận xét: - Với mô hình này ta sẽ không thể thấy được đầy đủ mối quan hệ giữa các đỉnh, như đồ thị hình 1.3.b đỉnh o3 là đỉnh cô lập, trong thế cờ hình 1.2.a o1 có mối quan hệ thẳng hàng với x1 và x3 nhưng trong đồ thị tương ứng ta không nhìn thấy được mối quan hệ này nên khó tính toán được nước đi cho lần sau. Mà mối quan hệ "thẳng hàng" giữa các quân là quan trọng trong bài toán lập trình trò chơi carô. - Mô hình này chỉ thích hợp cho việc lập trình khi mà chỉ chơi giữa người với người, lúc này bài toán chỉ là tìm đường đi cùng nhãn gồm 5 đỉnh cùng quân, không phải là bài toán tính nước đi cho các bước tiếp theo. b) Mô hình bằng đồ thị theo mối quan hệ thẳng hàng. Cách xây dựng này tương tự như cách thứ nhất nhưng có những đặc điểm sau: 27
Luận văn tốt nghiệp - Hai đỉnh x và o là kề nhau nếu tương ứng với 2 quân x và o mà chúng có mối quan hệ là thẳng hàng với nhau. - Trên mỗi cạnh ngoài nhãn thể hiện mối quan hệ thẳng hàng, ta thêm 1 trọng số đường đi, trọng số của cạnh (x, o) là số ô đi thẳng hàng từ quân x đến quân o trong thế cờ. - Hai đỉnh x và o chỉ được kề nhau khi trọng số cạnh (x, o) không quá 4. x1 o1 x1 x2 x2 x3 x3 x4 o2 o3 x5 a) b) Hình 1.4 Ví dụ xét thế cờ như hình 1.4.a và hình 1.4.b thì đồ thị tương ứng của nó như hình 1.5.a và hình 1.5.b x1 o1 x1 x2 x5 x2 o3 x3 o2 x3 x4 a) b) Hình 1.5 Mỗi cạnh của đồ thị, nhãn đặt trước trọng số, trọng số đứng sau cách nhãn bởi dấu phẩy. Xét thế cờ 1.4.a từ quân x1 đến quân x2 cách nhau 1 ô nếu tính từ x1 nên trọng số cạnh (x1, x2) là 1, quân x1 cách x3 2 ô nên trọng số (x1, x3) là 2. Ta thấy x1, x2, x3 đều thẳng hàng dọc nên nhãn là 3, và tương tự đánh nhãn và trọng số cho các cạnh còn lại ta có đồ thị như hình 1.5.a. Như vậy nếu tồn tại 1 đường đi cùng nhãn và có trọng số 1 gồm 5 đỉnh cùng quân thì thế cờ thắng, ở đồ thị hình 4.a đường đi thắng cho quân x là (x1, x2, x3, x4, x5) Trong kỹ thuật chơi cờ Ca rô, nước đi có lợi nhất là nước có tạo được nhiều khả năng dẫn đến thế cờ thắng, ví dụ thế cờ như hình 1.4.b thì ví trí của o1 là 1 28
Luận văn tốt nghiệp trong những nước có lợi nhất, vì nếu ta thay o1 bằng x4 thì quân x có thêm 3 khả năng phát triển nước dẫn đến thế cờ thắng như (x4, x2); (x4, x1); ( x4, x3), nếu với đồ thị tương ứng thì x4 là phần tử thống trị tập {x1, x2, x3}. Nếu vẫn giữ vị trí o1 như ban đầu thì quân "o" đã ngặn chặn đối phương có hiệu quả vì o1 đã thống trị {x1, x2, x3}, và ta thấy còn có o2 thống trị {x1, x2, x3} ngăn chặn được thế sắp thắng theo thẳng chéo {x1, x2, x3} (xem đồ thị hình 1.5.b). Như vậy ở góc độ đồ thị thì ta tìm tập thống trị (tập ổn định ngoài cực tiểu), ở đồ thị này {o1, o2} là 1 tập thống trị. Nhận xét: - Với mô hình này ta có ưu điểm là nhìn rõ trước được mối quan hệ giữa các đỉnh, tuy vậy nếu có 2 đỉnh không thẳng hàng thì chúng cô lập nhau, nhưng điều thường xảy ra khi số đỉnh là nhỏ ta dễ dàng kiểm soát được thế cờ. Hơn nữa hầu như ta chỉ quan tâm những quân có mối quan hệ thẳng hàng, để khắc phục nhược điểm ta có thể dựa vào mối quan hệ "tay ba" bằng cách đưa thêm đỉnh "ảo". - Khi số đỉnh càng lớn, càng thêm những đỉnh có mối quan hệ thẳng hàng thì số bậc của mỗi đỉnh tăng, nhưng quy luật cờ ca rô nên chỉ những đỉnh thẳng hàng mà cách nhau không quá 4 ô mới ảnh hưởng lẫn nhau, nên 2 đỉnh kề nhau nếu trọng số của chúng 4. Có 8 hướng thẳng hàng (xem hình 1.3.a), nên một đỉnh có tối đa là 8.4 = 32 bậc. - Khi một đỉnh có số bậc là 32 thì có thể loại bỏ khỏi đồ thị, vì nó không còn ảnh hưởng đến những đỉnh khác. Nhãn và trọng số của cạnh có thể là khoá phục vụ cho việc xử lý và tìm kiếm, tra cứu thông tin khi cần thiết. II. TÔ MÀU ĐỒ THỊ 1. Sắc số đồ thị Sắc số đồ thị G là số màu tối thiểu cần dùng để tô màu các đỉnh của đồ thị sao cho hai đỉnh kề nhau phải có màu khác nhau. Ta ký hiệu sắc số của đồ thị G là (G). Định lý 1: Cho đồ thị n đỉnh G = . Nếu đồ thị là đầy đủ thì sắc số của nó bằng số đỉnh của đồ thị, tức là (G) = n. Chứng minh: Với n = 1 thì (G) = 1 Giả thiết đúng với n k cần chứng minh đúng với n = k +1 Xét đồ thị k + 1 đỉnh X = {x1, x2,....., xk, xk+1} Nếu trong đồ thị G ta bỏ đỉnh xk+1 còn lại là 1 đồ thị với k đỉnh. Đối với phần còn lại theo giả thiết quy nạp ta cần k màu. 29
Luận văn tốt nghiệp Xét đỉnh xk +1, vì đồ thị là đầy đủ nên đỉnh xk+1 nối với các đỉnh còn lại, cho nên để tô đỉnh xk+1 cần màu khác với màu đã tô nên số màu sẽ là k + 1 màu. Hệ quả: Nếu đồ thị G chứa một đồ thị con đẳng cấu với Km thì (G) m Định lý 2: Giả sử G = là đồ thị vô hướng (G) = 2 khi và chỉ khi trong G không có chu trình độ dài lẻ. - Điều kiện đủ: Giả sử G không có chu trình độ dài lẻ. Ta chỉ ra (G) = 2. Thật vậy, ta tô màu các đỉnh của G theo nguyên tắc sau: Nếu x X được tô màu xanh thì các đỉnh kề của x là y, z ... lại tô màu đỏ. Tiếp theo các đỉnh kề của y, z,... lại tô màu xanh. Cứ như vậy, do số đỉnh hữu hạn và G liên thông nên tất cả các đỉnh trong X sẽ được tô hoặc xanh hoặc đỏ và không có một đỉnh nào được tô cả hai màu xanh, đỏ đồng thời, vì nếu có điều đó xảy ra thì sẽ có một chu trình độ dài lẻ đi qua x (trái với giả thiết). Hay (G) = 2. - Điều kiện cần: Giả sử (G) = 2. Dễ thấy rằng chỉ dùng 2 màu để tô các đỉnh của G thì trong G phải không có chu trình độ dài lẻ, vì nếu có chu trình độ dài lẻ thì tô màu các đỉnh theo quy tắc trên sẽ có ít nhất một đỉnh được tô đồng thời cả 2 màu. Định lý được chứng minh. a c a c b e b d d G1 G2 Hình 2.1 Ví dụ: Hình 2.1 đồ thị G1 không có chu trình độ dài lẻ, còn G2 có chu trình độ dài lẻ. Trong G1 nếu ta tô đỉnh a bởi màu xanh thì đỉnh b, c tô màu đỏ. Vì b màu đỏ nên d, e tô màu xanh. Ta thấy G1 không có chu trình lẻ và (G) = 2. Xét G2 có chu trình độ dài lẻ nên không thể tô bằng 2 màu, mà phải dùng 3 màu: xanh, đỏ và vàng. Định lý 3: Giả sử G = là đồ thị vô hướng với số đỉnh là n. Khi đó số ổn định trong (G) và sắc số (G) thoả mãn bất đẳng thức: (G) . (G) n. Chứng minh: Đặt (G) = s, theo định nghĩa của sắc số thì dùng s màu để tô các đỉnh trong X theo nguyên tắc hai đỉnh kề phải tô bằng 2 màu khác nhau. 30
Luận văn tốt nghiệp Cách tô màu như trên lập nên một phân hoạch tương đương trên tập X: X1 X2 ... Xs, Xi Xj = (i j), ở đây nếu ta đánh số các màu từ 1, 2,...,s thì Xi gồm các đỉnh cũng được tô màu i (i = 1,2,...,s). Mặt khác theo định nghĩa số ổn định trong thì Xi (G) (i = 1,....,s). Từ đó ta có đánh giá: X n = X1 + X2 + ... + Xi +...+ Xs s. (G) Hay (G) . (G) n. Định lý được chứng minh. 2. Tô màu đồ thị phẳng 2.1 Đồ thị phẳng Xét đồ thị G = được gọi là phẳng nếu có thể biểu diễn được trên mặt phẳng sao cho bất kỳ hai cạnh nào cũng không cắt nhau ngoài đỉnh (nếu có) Ví dụ: Xét đồ thị như hình 2.2.a1 là đồ thị phẳng vì nó được biểu diễn cách khác ở dạng mặt phẳng không có cạnh cắt nhau như hình 2.2.a2 Tương tự đồ thị ở hình 2.2.b1 là đồ thị phẳng vì nó có thể biểu diễn ở dạng mặt phẳng như hình 2.2.b2 a b a b d c d c a1) a2) a b e f a b d c e d f h c h g g b1) b2) Hình 2.2 * Các cạnh của đồ thị phẳng chia mặt phẳng thành nhiều miền, mỗi miền gọi là một mặt của G. Những cạnh nằm bên trong mặt f nào đó hoặc là cạnh giới hạn của mặt f với một mặt khác gọi là cạnh biên của mặt f. 2.2 Định lý 5 màu (Kempe - Heawood) Mọi đồ thị phẳng đều có sắc số không lớn hơn 5. 31
Luận văn tốt nghiệp Chứng minh: Xét một đồ thị G có n đỉnh. Dùng phép chứng minh quy nạp trên n ta có: Trường hợp G có một đỉnh hiển nhiên đúng. Giả sử mọi đồ thị phẳng có n đỉnh (n 1) đều có thể tô bằng 5 màu. Coi một đồ thị phẳng có n + 1 đỉnh. Có thể giả sử G là đơn đồ thị. Vì G phẳng nên có một đỉnh bậc 5. Loại bỏ đỉnh x này khỏi G, ta nhận được một đồ thị phẳng mới có n đỉnh. Tô màu cho đồ thị mới này bằng năm màu, do giả thiết qui nạp trên điều này thực hiện được. Bây giờ đưa đỉnh x vào lại đồ thị. Nếu các đỉnh kề với x được tô bằng ít hơn 5 màu thì tô màu x bằng một trong 5 năm khác màu các đỉnh kề với x là xong : đồ thị G đã được tô bằng 5 màu. Vậy chỉ xét trường hợp m(x) = 5 và 5 đỉnh kề với x được tô bằng 5 màu như hình 2.3 sau: e 5 4 d x a 1 c 3 b 2 Hình 2.3 Xét tất cả các đường trong G bắt đầu từ a và gồm các đỉnh chỉ tô bằng màu 1 và màu 3, trong các đường này nếu không có đường nào đi qua đỉnh c thì ta có thể thày đổi màu các đỉnh trên, tất cả các đường nói trên theo cách đổi màu 1 thành màu 3 và có thể tô đỉnh x màu 1. Nếu có một đường từ a đên c gồm toàn các đỉnh chỉ tô bằng màu 1 và màu 3 thì đường này cộng thêm hai cạnh e1 = (x, a) và e2 = (c, x) sẽ tạo thành một chu trình. Hai đỉnh b, d không thể nằm cùng bên trong hoặc cùng bên ngoài chu trình này được. Suy ra không có đường nào từ b đến d gồm các đỉnh chỉ tô màu 2 và màu 4 theo cách đổi màu 2 thành màu 4 và ngược lại. Lúc này, b và d có cùng màu 4 và ta có thể tô đỉnh x bằng màu 2. 2.3 Bài toán 4 màu (Appel - Haken) Phát biểu: Mọi đồ thị phẳng đều có sắc số không lớn hơn 4. Bài toán 4 màu được phát biểu như trên được chứng minh bằng phép thử trên máy tính trong nỗ lực nhằm thay thế cho định lý 5 màu. 3. Ví dụ ứng dụng Vấn đề tô màu đồ thị cũng có nhiều ứng dụng thực tế như tô màu bản đồ, công tác lập lịch. Với đồ thị phẳng ta có thể mô hình cho một bản đồ, trong đó mỗi miền bản đồ thì tương ứng là một đỉnh, hai miền có chung đường biên thì tương 32
Luận văn tốt nghiệp ứng với 2 đỉnh kề nhau. Khi tô màu bản đồ thì 2 miền kề nhau (chỉ chung đường biên không kể chung điểm biên) phải có màu khác nhau. Như vậy vấn đề tìm số màu tối thiểu để tô bản đồ, tương ứng với việc tìm sắc số cho đồ thị phẳng. Vào năm 1850 người ta đã chỉ ra 1 cách tô bản đồ nước Anh chỉ cần 4 màu, điều này là 1 thể hiện cho bài toán 4 màu. * Trong nhiều bài toán tin học, ta hay bắt gặp bài toán lập lịch. Vấn đề tô màu đồ thị có thể ứng dụng để giải quyết bài toán này. Ta xét một ví dụ ứng dụng, trong một phòng về phần mềm có các nhóm lập trình như sau: 1 - Hệ thống: A, B, C 2 - Multimedia: A, F, G 3 - Thương mại: B, D, E 4 - Về mạng: C, F, A. Các chữ cái là tên cho các thành viên, mỗi thành viên có thể tham gia nhiều nhóm khác nhau. Hàng tháng mỗi nhóm họp một lần để thảo luận các dự án mới và phân chia công việc, hãy lập lịch họp cho các nhóm để sao cho không ai họp trùng nhiều nhóm trong cùng 1 thời gian. Như vậy sắp lịch sao cho những nhóm nào có chung ít nhất một thành viên thì không thể họp cùng một thời điểm. Gọi mỗi nhóm là một đỉnh của đồ thị, những nhóm nào cùng chung ít nhất một thành viên thì tương ứng 2 đỉnh kề nhau, ví dụ như nhóm 1 và 2 cùng chung thành viên A thì đỉnh 1 và 2 kề nhau, ta biểu diễn đồ thị như hình 2.4 X 1 Đ 2 4 V Đ 3 Hình 2.4 Ta có thể tô màu đồ thị như trên với X: xanh; Đ: đỏ; V: vàng. Từ đồ thị ta có lịch sắp xếp các cuộc họp như sau: 33
Luận văn tốt nghiệp Đợt họp Tên nhóm I 1 II 2, 3 III 4 Mỗi màu tương ứng cho 1 đợt họp, những nhóm được tô cùng màu có thể họp trong cùng một đợt. 34

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.