Tham khảo tài liệu 'toán rời rạc ứng dụng trong tin học part 6', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Phẩn Hỉ. ĐỔ THỊ VẦ ƯNG DỤNG 205 đỉnh nào được tô cả hai màu xanh đỏ đồng thời vì nếu có điểu dó xảy ra thì sẽ có một chu trình độ dài lẻ đi qua X trái với giả thiết . Vậy s G 2. Điểu kiện cấn Giả sử s G 2. Dỗ thấy rằng nếu chỉ dùng 2 màu để tô các dỉnh cùa G thì trong G phải không có chu trình độ dài le 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ý dược chứng minh. Ví dụ 1 Cho Gj - Xj Uj không có chu trình độ dài lé còn G2 x2 u2 có chu trình dộ dài lẻ xem hình vẽ . Trong G nếu la tô X bởi màu xanh thì x2 và x3 tô màu dỏ. Vì x2 màu đỏ nên x4 x j tô màu xanh hay s G 2 ở đây G không có chu trình độ dài lẻ. Xét G2 có chu trình dộ 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. . Quan hệ giữa sắc số và số ổn định trong Định ý 12 Giả sử G - x u là đồ thị vô hướng với IXI n. Khi đó sô ổn định trong a G và sắc số s G của G thoả mãn bất đẳng thức a G .s G n. Chứng minh Đặt s 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. 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 Xj u x2 u . V Xs X với X n Xj - 0 i j ở dây nếu ta đánh sò các màu từ 1 2 . s thì Xj gồm các đỉnh được tô màu i i 1 . s . Mật khác theo định nghĩa sò ổn dịnh trong a G thì IXịl a G . Từ đó ta có đánh giá IXi n IX I IX2I . IXịl . XSI G Hay s G .ơ G n. Định lý dược chứng minh. 206 TOẨN rời rạc ứng dụng trong tin học . sác số của đồ thị cố chu trình Định ỉý Í3 Một chu trình độ dài lẻ chẵn luôn đó sắc số bằng 3 sắc số bằng 2 . Chứng minh Dùng quy nạp theo độ dài chu trình. . Sắc số của đồ thị đơn và đồ thị đơn phân dôi Đối với đồ thị dơn ta có thuật toán tổ màu đồ thị như sau Cho G x u là đồ thị đơn với X x x2 . xn . Tìm s G . Bước ỉ Sắp xếp bậc của các đỉnh theo thứ tự giảm dần. Không mất tính tổng quát giả sử m X m x2 . m xn . Bước 2 Gán màu 1 cho X và các đỉnh không liền kề với X . Sau đó tiếp gán
