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

• Toán học
• Chu số
• sắc số của đồ thị
• Chu số của đồ thị
• thành phần liên thông
• đồ thị định hướng
• Chu kì kinh tế
• Chỉ số dẫn báo chu kì kinh tế
• Khái niệm chu kì kinh tế
• Cách xác định chu kì kinh tế
• Chỉ số dẫn báo tổng hợp
• Lựa chọn chỉ số dẫn báo
• Giáo trình dạy học lớp 3
• giáo án dạy học
• dạy học mẫu giáo
• dạy học mầm non
• tài liệu giảng dạy mầm non
• giáo án dạy học cho trẻ
• Chữ ký số
• Ứng dụng chữ ký số
• Công cụ tạo chữ ký số
• Mô hình của chữ ký số
• Hệ thống chữ ký số
• Cài đặt thử nghiệm chữ ký số
• Tìm chữ số tận cùng
• Bài tập tìm chữ số tận cùng
• Tính chất tìm chữ số tận cùng
• Phương pháp tìm chữ số tận cùng
• Giải toán tìm chữ số tận cùng
• Toán tìm chữ số tận cùng
• Lược đồ chữ ký số
• Thuật toán chữ ký số
• Chữ ký số tập thể
• Mô hình chữ ký số tập thể
• Thuật toán theo mô hình chữ ký số tập thể
• Y dược học
• Đái tháo đường týp 2
• Viêm nha chu
• Điều trị nha chu
• Chỉ số lâm sàng nha chu
• Xử lí bề mặt gốc răng
• Nghiên cứu chữ ký số
• Xây dựng lược đồ chữ ký
• Kỹ thuật chữ ký số
• Lược đồ chữ ký số mù
• Chữ ký số mù
• Chữ ký kỹ thuật số
• Chữ ký mù
• Chữ ký số mù DSA
• Chữ ký số mù Nyberg Rueppel
• Bài giảng Toán 3 Chương 2 bài 27
• Chia số có 2 chữ số
• Chia số 2 chữ số cho số 1 chữ số
• Phép chia số tự nhiên
• Bài giảng điện tử Toán 3
• Bài giảng điện tử lớp 3
• Bài giảng điện tử
• Bài giảng Toán 3 Chương 2 bài 28
• Chia số có 3 chữ số
• Chia số 3 chữ số cho số 1 chữ số
• Giáo án Toán 3 Chương 2 bài 27
• Giáo án điện tử Toán 3
• Giáo án điện tử lớp 3
• Giáo án điện tử
• Giáo án Toán 3 Chương 2 bài 28
• Giải bài tập Toán lớp 3
• Giải bài tập SGK Toán 3
• Chương 3 Các số đến 10 000
• Bài tập SGK trang 119 Toán 3
• Chia số có bốn chữ số cho số có một chữ số
• Chia số có bốn chữ số
• Đọc số có 3 chữ số
• Viết số có 3 chữ số
• Các số có 3 chữ số
• Số có 3 chữ số
• Bài giảng Toán 3
• Chương 2 Phép nhân chia trong phạm vi 1000
• Bài tập SGK Toán 3 trang 22
• Nhân số có hai chữ số với số có một chữ số
• Nhân số có hai chữ số
• Bài giảng môn Toán lớp 3
• Toán lớp 3
• Chia số có hai chữ số
• Số có một chữ số
• Phép chia số có hai chữ số
• Tìm hiểu chữ ký số tập thể
• Mô hình chữ ký số
• Chữ ký số tập thể đa thành phần
• Luận án Tiến sĩ
• Luận án Tiến sĩ Kỹ thuật
• Kỹ thuật máy tính
• Chữ ký số tập thể mù
• Chuẩn chữ ký số
• Luận văn tốt nghiệp Vật lí
• Chu kỳ hoạt động của mặt trời
• Chu kỳ thứ 24 của mặt trời
• Khảo sát chu kỳ hoạt động mặt trời
• Dự báo chu kỳ hoạt động mặt trời
• Thông số đánh giá hoạt động mặt trời
• Bài toán khai căn
• Cải biên chữ ký số Rabin
• Lược đồ chữ ký số Rabin
• Lược đồ chữ ký số Rabin William
• Giải bài tập Toán 1
• Giải bài tập SGK Toán 1
• Các số trong phạm vi 100
• So sánh các số có hai chữ số
• Số có hai chữ số
• Viết số có hai chữ số
• Khoanh vào số lớn nhất
• Khoanh vào số bé nhất
• Luận án Tiến sĩ Khoa học giáo dục
• Chu trình kiến tạo 5E
• Chu trình kiến tạo 5E trong dạy học
• Dạy học một số chủ đề toán
• Giáo dục đại học