Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Sức khỏe - Y tế
Văn bản luật
Nông Lâm Ngư
Kỹ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Tài liệu HOT
Tìm
Danh mục
Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Y tế sức khỏe
Văn bản luật
Nông lâm ngư
Kĩ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Thông tin
Điều khoản sử dụng
Quy định bảo mật
Quy chế hoạt động
Chính sách bản quyền
0
Trang chủ
Khoa Học Tự Nhiên
Toán học
Chương 4: Chu số và sắc số của đồ thị
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
Cẩm Thúy
129
5
pdf
Báo lỗi
Trùng lắp nội dung
Văn hóa đồi trụy
Phản động
Bản quyền
File lỗi
Khác
Upload
Tải xuống
đang nạp các trang xem trước
Bấm vào đây để xem trước nội dung
Tải xuống
TÀI LIỆU LIÊN QUAN
Chu kì kinh tế và chỉ số dẫn báo chu kì kinh tế
5
104
0
Giáo án môn Toán lớp 3 :Tên bài dạy : Chia số có năm chữ số cho số có một chữ số( tChia số có năm chữ số cho số có một chữ số( tiếp) A-Mục tiêu - HS biết thực hiện phép chia số có năm chữ số cho số có một chữ số( Trường hợp có dư). Vận dụng để giải toán có lời văn. - Rèn KN tính chia và giải toán. - GD HS chăm học toán B-Đồ dùng GV : Bảng phụ- Phiếu HT HS : SGK C-Các hoạt động dạy học chủ yếu Hoạt động dạy 1/Tổ chức: 2/Kiểm tra: Đặt tính rồi tính - Hát Hoạt động họciếp)
4
249
0
Đề tài: Chữ ký số và ứng dụng
17
237
15
Tìm chữ số tận cùng
11
96
0
Phát triển thuật toán chữ ký số tập thể
9
119
0
Đánh giá kết quả lâu dài của điều trị nha chu đối với chỉ số nha chu và đường huyết ở bệnh nhân đái tháo đường týp 2
7
20
1
Nghiên cứu xây dựng lược đồ chữ ký số tập thể
11
147
5
Phát triển lược đồ chữ ký số mù
7
66
3
Bài giảng Chia số có 2 chữ số cho 1 số có 1 chữ số - Toán 3 - GV.Ng.P.Hùng
13
215
0
Bài giảng Chia số có 3 chữ số cho số có 1 chữ số - Toán 3 - GV.Ng.P.Hùng
11
124
0
TÀI LIỆU XEM NHIỀU
Một Case Về Hematology (1)
8
461886
55
Giới thiệu :Lập trình mã nguồn mở
14
22719
61
Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh
13
10905
530
Câu hỏi và đáp án bài tập tình huống Quản trị học
14
10083
447
Phân tích và làm rõ ý kiến sau: “Bài thơ Tự tình II vừa nói lên bi kịch duyên phận vừa cho thấy khát vọng sống, khát vọng hạnh phúc của Hồ Xuân Hương”
3
9540
104
Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)
249
8301
1127
Tiểu luận: Nội dung tư tưởng Hồ Chí Minh về đạo đức
16
8248
423
Mẫu đơn thông tin ứng viên ngân hàng VIB
8
7867
2220
Đề tài: Dự án kinh doanh thời trang quần áo nữ
17
6711
253
Vật lý hạt cơ bản (1)
29
5793
88
TỪ KHÓA LIÊN QUAN
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
TÀI LIỆU MỚI ĐĂNG
Giáo án mầm non chương trình đổi mới: Đề tài: Ôn xác định vị trí trên – dưới, trước- sau của đối tượng khác.
8
355
3
01-05-2024
Đánh giá hao mòn và độ tin cậy của chi tiết và kết cấu trên đầu máy diezel part 3
12
314
0
01-05-2024
Động cơ đốt trong và máy kéo công nghiêp tập 1 part 7
23
260
0
01-05-2024
BeginningMac OS X Tiger Dashboard Widget Development 2006 phần 2
34
215
0
01-05-2024
Báo cáo nghiên cứu khoa học " KẾT QUẢ NGHIÊN CỨU BƯỚC ĐẦU VỀ THIÊN ĐỊCH CHÂN KHỚP TRÊN CÂY THANH TRÀ Ở THỪA THIÊN HUẾ "
7
176
0
01-05-2024
Đóng mới oto 8 chỗ ngồi part 9
10
118
0
01-05-2024
GIÁO TRÌNH VI XỬ LÝ 1 - CHƯƠNG 5. LẬP TRÌNH CHO VI ĐIỀU KHIỂN 80C51
23
108
1
01-05-2024
Fecal Incontinence Diagnosis and Treatment - part 8
35
103
0
01-05-2024
MẪU GIẤY PHÉP VẬN TẢI LOẠI C
2
110
0
01-05-2024
MẪU CHỨNG CHỈ QUẢN LÝ VŨ KHÍ, VẬT LIỆU NỔ, CCHT
1
120
0
01-05-2024
TÀI LIỆU HOT
Mẫu đơn thông tin ứng viên ngân hàng VIB
8
7867
2220
Giáo trình Tư tưởng Hồ Chí Minh - Mạch Quang Thắng (Dành cho bậc ĐH - Không chuyên ngành Lý luận chính trị)
152
5790
1388
Ebook Chào con ba mẹ đã sẵn sàng
112
3772
1233
Ebook Tuyển tập đề bài và bài văn nghị luận xã hội: Phần 1
62
5333
1136
Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)
249
8301
1127
Giáo trình Văn hóa kinh doanh - PGS.TS. Dương Thị Liễu
561
3518
644
Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh
13
10905
530
Giáo trình Sinh lí học trẻ em: Phần 1 - TS Lê Thanh Vân
122
3694
525
Giáo trình Pháp luật đại cương: Phần 1 - NXB ĐH Sư Phạm
274
4071
516
Bài tập nhóm quản lý dự án: Dự án xây dựng quán cafe
35
4136
480
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.