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
BÀI 07: Sắc số của đồ thị
TAILIEUCHUNG - BÀI 07: Sắc số của đồ thị
Khái niệm sắc số liên quan đến bài toán tô màu đồ thị như sau: Hãy tô màu các đỉnh của một đồ thị đã cho, sao cho hai đỉnh kề nhau phải được tô bằng hai màu khác nhau. Ta nói rằng, đồ thị G tô được bằng k màu nếu tồn tại hàm: m : V → {0, 1, 2, . , k-1} sao cho, nếu hai đỉnh x và y kề nhau thì m(x) ≠ m(y). Dễ thấy rằng, đồ thị G tô màu được khi và chỉ khi nó không có đỉnh nút. | BÀI 07 . Sắc số của đồ thị Khái niệm sắc số liên quan đến bài toán tô màu đồ thị như sau Hãy tô màu các đỉnh của một đồ thị đã cho sao cho hai đỉnh kề nhau phải được tô bằng hai màu khác nhau. Ta nói rằng đồ thị G tô được bằng k màu nếu tồn tại hàm m V 0 1 2 . k-1 sao cho nếu hai đỉnh x và y kề nhau thì m x m y . Dễ thấy rằng đồ thị G tô màu được khi và chỉ khi nó không có đỉnh nút. Định nghĩa Sắc số của một đồ thị chính là số màu ít nhất dùng để tô các đỉnh của đồ thị đó. Ta ký hiệu số s là sắc số của đồ thị G. Hiển nhiên s n số màu không vượt quá số đỉnh của đồ thị. Ví dụ Hãy tô màu đồ thị sau đây. Hình . Tô màu các đỉnh đồ thị Đồ thị trên có sắc số bằng 3. Nhận xét Mỗi cách tô màu m cho đồ thị G sẽ ứng với một cách phân hoạch tập đỉnh V thành các tập ổn định trong không giao nhau mỗi tập ứng với một màu. Ngược lại mỗi cách phân hoạch tập đỉnh V thành các tập ổn định trong không giao nhau sẽ cho ta một cách tô màu. Định lý Mọi chu trình độ dài lẻ luôn có sắc số bằng 3. Chứng minh Giả sử chu trình có độ dài là 2n 1. Ta chứng minh bằng quy nạp theo số n. n 1 Chu trình gồm 3 đỉnh mà hai đỉnh bất kỳ đều kề nhau. Vậy ta phải dùng đúng 3 màu để tô các đỉnh. n n 1 Giả sử a là một chu trình có độ dài 2 n 1 1 2n 3 với dãy các đỉnh là X1 X2 . X2n 1 X2n 2 X2n s . Nối X1 với X2n 1 ta được một chu trình a có độ dài 2n 1. Theo giả thiết quy nạp chu trình a có sắc số bằng 3. Lấy màu của X1 tô cho x2n 2 còn màu của X2n 1 tô cho x2n 3. Chu trình a đã được tô màu mà không phải thêm màu mới. Vậy chu trình a có sắc số bằng 3. ũ Định lý Đồ thị đầy đủ n đỉnh Kn có sắc số bằng n. Dưới đây là một tiêu chuẩn đơn giản để kiểm tra xem một đồ thị có hai sắc sắc số bằng 2 hay không. Định lý Konig Giả sử đồ thị G có ít nhất một cạnh. Đồ thị G là hai sắc khi và chỉ khi G không có chu trình đơn vô hướng độ dài lẻ. Chứng minh Giả sử G là đồ thị hai sắc. Theo Định lý thì G không thể có chu trình đơn vô hưóng độ dài lẻ. Ngược lại giả sử G không có chu trình đơn vô .
Thanh Vy
341
6
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
BÀI 07: Sắc số của đồ thị
6
317
2
Chương 4: Chu số và sắc số của đồ thị
5
116
0
Giáo trình đồ thị - Chu số và sắc số của đồ thị
5
73
0
Giáo trình đồ thị - Sắc số của đồ thị
6
82
0
Đồ thị và các thuật toán – Chương 2: Các số cơ bản của đồ thị
25
84
1
Sắc số, đa thức tô màu và tính duy nhất tô màu của đồ thị tách cực
6
76
1
Nhận xét một số đặc điểm tinh dịch đồ và nhiễm sắc thể của bệnh nhân vô sinh nam có mất đoạn AZFc đơn thuần hoặc phối hợp tại Bệnh viện Nam học và Hiếm muộn Hà Nội
4
26
1
Nghiên cứu một số độc tính của phác đồ FOLFOX 4 trên bệnh nhân ung thư biểu mô tuyến đại trực tràng giai đoạn di căn xa
7
27
1
Giáo trình photoshop - Chương 19: Thiết lập các thông số của máy tính cho việc quản lý màu sắc
14
61
0
Thủ tục Xem xét chấp thuận hoặc không chấp thuận hoạt động tôn giáo ngoài chương trình đăng ký của tổ chức cơ sở có sự tham gia của chức sắc nhà tu hành tín đồ trong Huyện – thị, Mã số hồ sơ 021187
5
87
0
TÀI LIỆU XEM NHIỀU
Một Case Về Hematology (1)
8
461887
55
Giới thiệu :Lập trình mã nguồn mở
14
22723
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
10906
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
8302
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
6713
253
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
5795
1391
TỪ KHÓA LIÊN QUAN
Toán học
Sắc số của đồ thị
bài toán tô màu đồ thị
chu trình độ dài chẵn
thuật toán
tìm sắc số đồ thị
đồ thị vô hướng
đồ thị
giáo trình đồ thị
tài liệu về đồ thị
ứng dụng của đồ thị
Chu số
Chu số của đồ thị
thành phần liên thông
đồ thị định hướng
Đồ thị tách cực
Đa thức tô màu
Đồ thị duy nhất tô màu
Lý thuyết đồ thị
Phân tích thuật toán
Thiết kế thuật toán
Ngôn ngữ C
Cách tìm sắc số
Số ổn định trong
Số ổn định ngoài
Nhân của đồ thị
hướng dẫn thủ tục
hành chính tỉnh bình phước
nội vụ
lao động thương binh và xã hội
thủ tục tài chính
Hội thảo khoa học Toán học
Đồ thị có hướng
Đồ thị đơn vô hướng hữu hạn đỉnh
Đồ thị lưỡng phân
Bài giảng Toán rời rạc
Toán rời rạc
Đơn đồ thị vô hướng
Đa đồ thị vô hướng
Đồ thị phẳng
định lý Kemple
định lý heawood
đồ thị Euler
đồ thị hamiton
bài giảng đồ thị phẳng
Bài giảng Toán tin
Đồ thị đặc biệt
Chu trình đồ thị
Đường đi đồ thị
đa đồ thị
đồ thị vô hạn
biểu đồ
đồ thị liên thông
tài liệu lý thuyết đồ thị
biểu diễn đồ thị
đồ thị hữu hạn
Bài giảng Lý thuyết đồ thị
Đồ thị Halmiton
Đồ thị vô hướng liên thông
Thuật toán Fleury
Cây khung của đồ thị
Cây khung nhỏ nhất
Đồ thị G
Bài giảng Toán học tổ hợp
Toán học tổ hợp
Đại cương về đồ thị
Đẳng cấu đồ thị
Phân tích thiết kế giải thuật
Bài giảng Phân tích thiết kế giải thuật
Giải thuật tìm kiếm trong đồ thị
Biểu diễn của một đồ thị
Biểu diễn một đồ thị vô hướng
Biểu diễn một đồ thị có hướng
Giáo trình Lý thuyết đồ thị
Chu trình Euler
Chu trình Hamilton
Tìm kiếm trên đồ thị
Đa đồ thị có hướng
Bài giảng Toán rời rạc 2
Toán rời rạc 2
Khái niệm về đồ thị
Đđồ thị vô hướng
Dạng đồ thị đặc biệt
Bài toán Clique lớn nhất
Tiếp cận Heuristic
Đồ thị vô hướng không có trọng số
Phân cụm điện não đồ
Thuật toán nhánh cận
Giáo dục đào tạo
giáo trình cao đẳng đại học
định nghĩa đồ thị
Discrete Mathematics
Biểu diễn đồ thị trên máy tính
Bậc của đỉnh
Cặp ghép
đồ thị hai phần
Tập đỉnh tựa
Bài toán đường đi ngắn nhất
thuật toán Dijkstra
đường đi trên đồ thị
đồ thị phi chu trình
Luận văn Thạc sĩ
Luận văn Thạc sĩ Toán học
Toán giải tích
Tính liên thông đỉnh
Tính liên thông cạnh
TÀI LIỆU MỚI ĐĂNG
Báo cáo khoa học: Loss of kinase activity in Mycobacterium tuberculosis multidomain protein Rv1364c
14
237
0
01-05-2024
CẤU TẠO HẠT NHÂN NGUYÊN TỬ-ĐỘ HỤT KHỐI-NĂNG LƯỢNG LIÊN KẾT-LK RIÊNG
12
270
0
01-05-2024
Management and Services Part 1
10
160
0
01-05-2024
Posted prices versus bargaining in markets_7
23
158
0
01-05-2024
Công nghiệp gang thép Việt Nam : Một giai đoạn phát triển và chuyển đổi chính sách mới part 5
6
196
0
01-05-2024
B2B Content Marketing: 2012 Benchmarks, Budgets & Trends
17
140
0
01-05-2024
Hướng dẫn sử dụng Quickoffice cho Ipad và Iphone
13
154
0
01-05-2024
Đóng mới oto 8 chỗ ngồi part 9
10
119
0
01-05-2024
Giáo trình CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT - Chương 1
5
127
0
01-05-2024
Báo cáo tốt nghiệp: Vận hành và bảo dưỡng trong MPLS
92
145
3
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
5795
1391
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
5334
1136
Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)
249
8302
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
10906
530
Giáo trình Sinh lí học trẻ em: Phần 1 - TS Lê Thanh Vân
122
3695
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.