tailieunhanh - Chương 4: Chu số và sắc số của đồ thị

Chu số của đồ thị Cho đồ thị G = (V, E) có n đỉnh, m cạnh, p thành phần liên thông. Định nghĩa : Đại lượng: c = m - n + p được gọi là chu số của đồ thị G. Trước hết, ta xét các tính chất của đại lượng này. Ví dụ : Xét đồ thị sau đây: Đồ thị trên có n = 7, m = 8 và p = 2. Vậy chu số c = 8 - 7 + 2 = 3. Định lý : Nếu thêm một cạnh mới vào đồ thị. | BÀI 06 Chương 4 Chu số và sắc số của đồ thị . Chu số của đồ thị Cho đồ thị G V E có n đỉnh m cạnh p thành phần liên thông. Định nghĩa Đại lượng c m - n p được gọi là chu số của đồ thị G. Trước hết ta xét các tính chất của đại lượng này. Ví dụ Xét đồ thị sau đây Hình . Đồ thị định hướng không liên thông Đồ thị trên có n 7 m 8 và p 2. Vậy chu số c 8 - 7 2 3. Định lý Nếu thêm một cạnh mới vào đồ thị G thì chu số tăng thêm 1 hoặc không thay đổi. Chứng minh Giả sử thêm cạnh mới a b vào đồ thị G. Khi đó m tăng thêm 1. i Nếu hai đỉnh a b thuộc cùng một mảng liên thông trong G thì n p không đổi do vậy chu số tăng thêm 1. ii Nếu hai đỉnh a b nằm ở hai mảng liên thông khác nhau trong G thì p giảm 1 do vậy chu số không đổi. Hệ quả Chu số của đồ thị là số nguyên không âm. Chứng minh Thật vậy đồ thị G được xây dựng từ đồ thị Go gồm n đỉnh và không có cạnh nào cả. Sau đó lần lượt thêm các cạnh vào đồ thị Go để được đồ thị G. Chu số của Go là c o - n n 0. Quá trình thêm cạnh không làm giảm chu số. Vậy chu số của G chu số của Go 0. Bây giờ ta đi tìm ý nghĩa của chu số. Ta đánh số các cạnh của đồ thị G theo một thứ tự nào đó 1 2 . m. Với mỗi chu trình vô hướng trong đồ thị G ta chọn một chiều thuận và biểu diễn nó bằng một vectơ m chiều q1 q2 . qm mà qi là số lần xuất hiện của cạnh thứ i trong chu trình theo chiều thuận trừ đi số lần xuất hiện của cạnh đó trong chu trình theo chiều ngược. Ví dụ Xét đồ thị định hướng sau đây. Hình . Đánh số các cạnh của đồ thị Đồ thị có 7 cạnh được đánh số như hình vẽ. Với chu trình vô hướng e1 e2 e7 ta chọn chiều thuận là chiều e e2 e7 khi đó vectơ tương ứng sẽ là -1 1 0 0 0 0 1 . Do vây ta có thể đồng nhất mỗi chu trình vô hướng với một vectơ biểu diễn nó. Các chu trình vô hướng ti t2 . tk được gọi là độc lập tuyến tính nếu các vectơ tương ứng với chúng lập thành một hệ độc lập tuyến tính. Hệ chu trình đơn vô hướng ti t2 . tk được gọi là độc lập tuyến tính cực đại nếu nó là độc lập tuyến tính và mỗi chu trình vô hướng