đồ thị phẳng và tô màu

... Trong đồ thị hình đây, đồ thị phẳng, đồ thị không phẳng? Nếu đồ thị phẳng kẻ thêm cạnh để đồ thị không phẳng? a f h b b a c g c b f f g g d f e G1 c d G2 e e d G3 Chứng minh đồ thị Peterson (đồ thị ... phải tô màu khác Do χ(G) ≥ Ngồi ra, dùng màu đánh số 1, 2, 3, để tô màu G sau: Như χ(G) = 4 7.3.3 Mệnh đề: Nếu đồ thị G chứa đồ thị đồng phôi với đồ thị đầy đủ Kn χ(G) ≥ n Chứng minh: Gọi H đồ thị ... minh rằng: a) Kn phẳng n ≤ b) Km,n phẳng m ≤ hay n ≤ Đồ thị đồ thị khơng phẳng sau có tính chất: Bỏ đỉnh cạnh liên thuộc tạo đồ thị phẳng a) K5; b) K6; c) K3,3 Cho G đơn đồ thị phẳng liên thơng...

Ngày tải lên: 30/07/2014, 06:20

... Chương Đồ thò phẳng Bài toán Tô màu 4.6 BÀI TOÁN TÔ MÀU ĐỒ THỊ 4.6.1 ĐỊNH NGHĨA Phép tô màu đồ thò phép gán màu cho đỉnh đồ thò cho hai đỉnh kề có màu khác Một cách hình thức đònh nghóa phép tô màu ... (KEMPE-HEAWOOD) Mọi đồ thò phẳng có 5-sắc tố Trương Mỹ Dung 51 Chương Đồ thò phẳng Bài toán Tô màu 4.6.6 BÀI TOÁN MÀU GIẢ THIẾT BÀI TOÁN MÀU Trên đồ bất kỳ, ta nói tô màu miền đồ tô màu xác đònh cho ... ĐỀ Giả sử H đồ thò G Khi : Nếu G phẳng H phẳng Nếu H không phẳng G không phẳng 4.4.3 BỔ ĐỀ Mọi đồ thò phẳng đồng dạng phẳng 4.5 ĐỊNH LÝ KURATOWSKI Đồ thò G phẳng G không chứa đồ thò đồng cấu với...

Ngày tải lên: 22/08/2012, 11:30

... miền kề có màu khác nhau” Ví dụ 9: Ta có đồ: Đối với đồ này, ta cần ba màu đủ (hai màu không đủ) Để tô màu đồ, chuyển đồ dạng đồ thị Mỗi đồ mặt phẳng biểu diễn đồ thị Trong đó: + Mỗi miền đồ biểu ... sau: Tô màu đồ thị 2.1 Định nghĩa TOP Tô màu đơn đồ thị việc gán màu cho đỉnh cho hai đỉnh liền kề có màu khác Mỗi đồ thị có nhiều cách tơ màu khác Số màu hay sắc số (Chromatic number) đồ thị ... III: ĐỒ THỊ PHẲNG VÀ BÀI TỐN TƠ MÀU ĐỒTHỊ 1) Xây dựng đồ thị đối ngẫu tô màu đồ sau: a D C B A E b c 2) Tìm sắc số đồ thị sau: a C A B F E H G D b c D C I H A J F G B E d e 3) Tìm sắc số đồ thị...

Ngày tải lên: 23/10/2013, 09:15

... Đồ thị phẳng tốn tơ màu đồ thị ĐỒ THỊ PHẲNG  Đồ thị phẳng  Ví dụ  Đồ thị sau có phải đồ thị phẳng không? Chương Đồ thị phẳng tốn tơ màu đồ thị ĐỒ THỊ PHẲNG  Đồ thị phẳng  Ví dụ  Đồ thị ... Chương Đồ thị phẳng tốn tô màu đồ thị 27 Tô màu đồ thị  Thuật tốn Welch Powell  Ví dụ 1: Tơ màu cho đồ thị sau với số màu v1 v6 v5 v2 v3 v4 G Chương Đồ thị phẳng tốn tơ màu đồ thị 28 Tơ màu đồ thị ... Chương Đồ thị phẳng toán tô màu đồ thị 10 ĐỒ THỊ PHẲNG  Công thức Euler  Ví dụ  Tính số miền đơn đồ thị phẳng liên thơng có đỉnh đỉnh có bậc Chương Đồ thị phẳng tốn tơ màu đồ thị 11 ĐỒ THỊ PHẲNG...

Ngày tải lên: 18/02/2014, 03:20

... Đồ thị phẳng tốn tơ màu đồ thị ĐỒ THỊ PHẲNG  Đồ thị phẳng  Ví dụ  Đồ thị sau có phải đồ thị phẳng không? Chương Đồ thị phẳng tốn tơ màu đồ thị ĐỒ THỊ PHẲNG  Đồ thị phẳng  Ví dụ  Đồ thị ... Chương Đồ thị phẳng tốn tô màu đồ thị 27 Tô màu đồ thị  Thuật tốn Welch Powell  Ví dụ 1: Tơ màu cho đồ thị sau với số màu v1 v6 v5 v2 v3 v4 G Chương Đồ thị phẳng tốn tơ màu đồ thị 28 Tơ màu đồ thị ... Chương Đồ thị phẳng toán tô màu đồ thị 10 ĐỒ THỊ PHẲNG  Công thức Euler  Ví dụ  Tính số miền đơn đồ thị phẳng liên thơng có đỉnh đỉnh có bậc Chương Đồ thị phẳng tốn tơ màu đồ thị 11 ĐỒ THỊ PHẲNG...

Ngày tải lên: 31/07/2014, 09:41

... Đồ thị phẳng tốn tơ màu đồ thị ĐỒ THỊ PHẲNG  Đồ thị phẳng  Ví dụ  Đồ thị sau có phải đồ thị phẳng không? Chương Đồ thị phẳng tốn tơ màu đồ thị ĐỒ THỊ PHẲNG  Đồ thị phẳng  Ví dụ  Đồ thị ... sau có phải đồ thị phẳng khơng? Chương Đồ thị phẳng tốn tơ màu đồ thị ĐỒ THỊ PHẲNG  Đồ thị phẳng  v1  Chứng minh K3,3 không phẳng v1 v5 R2 R1 v4 v2 Chương Đồ thị phẳng tốn tơ màu đồ thị v1 R21 ... Chương Đồ thị phẳng tốn tơ màu đồ thị 27 Tơ màu đồ thị  Thuật tốn Welch Powell  Ví dụ 1: Tơ màu cho đồ thị sau với số màu v1 v6 v5 v2 v3 v4 G Chương Đồ thị phẳng tốn tơ màu đồ thị 28 Tơ màu đồ thị...

Ngày tải lên: 02/03/2015, 08:47

... diển phẳng đồ thị • Ví dụ 1: Đồ thị K4 với cạnh cắt có đồ thị phẳng khơng? • Giải: K4 đồ thị phẳng • I ĐỒ THỊ PHẲNG • Ví dụ Đồ thị Q3 có đồ thị phẳng khơng? • Chỉ đồ thị phẳng cách biểu diễn phẳng ... tơ màu đồ tương đương tốn tơ màu đồ thị đối ngẫu cho khơng có đỉnh liền kề màu II TƠ MÀU ĐỒ THỊ • ĐỊNH NGHĨA Tô màu đơn đồ thị gán màu cho đỉnh cho khơng có đỉnh liền kề gán màu • Một đồ thị tô ... phải tô màu đỏ; e- vàng; f – lam; g- đỏ II TÔ MÀU ĐỒ THỊ • G H thêm cạnh (a,g); Làm trước trừ đỉnh g phải tô màu thứ màu nâu a đỏ b lam • Ví dụ Tìm số màu tơ đồ thị Kn; • Giải: Có thể tô màu Kn...

Ngày tải lên: 09/06/2015, 01:04

... Số đỉnh đồ thị gọi bậc đồ thị, số cạnh số cung đồ thị gọi cỡ đồ thị Đồ thị hữu hạn đồ thị có bậc cỡ hữu hạn Đồ thị đơn đồ thị khơng có khun khơng có cạnh song song Đồ thị vô hướng đủ đồ thị mà ... 1.3 Đồ thị phẳng Trang Bài tốn tơ màu đồ thị ứng dụng 1.3.1 Đồ thị phẳng Định nghĩa 12: Một đồ thị gọi đồ thị hình học phẳng biểu diễn mặt phẳng cho cạnh không cắt Một đồ thị gọi đồ thị phẳng ... đồ tơ hai màu đỉnh đồ thị phẳng tương ứng có bậc chẵn lớn Chứng minh: Các mặt đồ thị phẳng tô hai màu đỉnh đồ thị đối ngẫu tô hai màu Suy chu trình đồ thị đối ngẫu có độ dài chẵn Do đỉnh đồ thị...

Ngày tải lên: 31/05/2014, 09:28

... THUYẾT ĐỒ THỊ ĐỒ THỊ PHẲNG Bài Trong đồ thị đây, đồ thị phẳng, đồ thị không phẳng? đồ thị phẳng kẻ thêm cạnh để đồ thị không phẳng? a) b) a’ a b b a c b’ d’ g d c h e d c’ Bài giải: a) Đồ thị cho phẳng ... Khi đồ thị đường chúng đẳng cấu với NHĨM 10_PHƯƠNG PHÁP TỐN SƠ CẤP Trang 10 LÝ THUYẾT ĐỒ THỊ ĐỒ THỊ PHẲNG CHƯƠNG II ĐỒ THỊ PHẲNG 2.1 ĐỒ THỊ PHẲNG • Đồ thị hình học phẳng Một đồ thị gọi đồ thị ... đồ thị gọi cỡ đồ thị • Đồ thị hữu hạn đồ thị có bậc cỡ hữu hạn • Đồ thị đơn: đồ thị khơng có khun khơng có cạnh song song • Đồ thị vô hướng đủ: đồ thị mà cặp đỉnh kề • Đồ thị có hướng đủ: đồ thị...

Ngày tải lên: 31/05/2014, 09:28