zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

Bài giảng Lý thuyết đồ thị (Graph theory) - Chương 3: Đồ thị phẳng

Chia sẻ: Xaydung K23 | Ngày: | Loại File: PDF | Số trang:9

Báo xấu

166
lượt xem 11
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nội dung chương này trình bày khái niệm và định nghĩa, công thức Euler, một số đồ thị không phẳng, bất đẳng thức EV, định lý Kuratowski, ứng dụng đồ thị phẳng trong bài toán tô màu đồ thị, bài toán lập lịch thi.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Lý thuyết đồ thị (Graph theory) - Chương 3: Đồ thị phẳng

24/10/2013 Bài giảng: Chương 3 LÝ THUYẾT ĐỒ THỊ ĐỒ THỊ PHẲNG (GRAPH THEORY) (Planar Graph) TRẦN QUỐC VIỆT 1 2 Nội dung 1. Khái niệm và định nghĩa Bài toán cổ: “Ba nhà, ba giếng”: Có ba nhà ở gần ba cái 1. Khái niệm và định nghĩa giếng, nhưng: 2. Công thức Euler - Không có đường nối trực tiếp giữa các nhà với nhau 3. Một số đồ thị không phẳng - Không có đường nối trực tiếp giữa các giếng với nhau 4. Bất đẳng thức EV 5. Định lý KURATOWSKI 6. Ứng dụng đồ thị phẳng trong: - Mỗi nhà đều có đường đi đến cả 3 giếng  Bài toán tô màu đồ thị  Bài toán lập lịch thi Có cách làm các đường này mà đôi một không giao nhau hay 3 không (ngoài các điểm là nhà hay giếng)? 1
24/10/2013 Khái niệm và định nghĩa Khái niệm và định nghĩa Biểu diễn bài toán bằng đồ thị: Định nghĩa đồ thị phẳng: - Mỗi nhà ↔ một đỉnh - Một đồ thị được gọi là đồ thị phẳng (Planar Graph) nếu ta - Mỗi giếng ↔ một đỉnh có thể vẽ nó trên một mặt phẳng sao cho không có hai cạnh - Một đường đi giữa một nhà và một giếng ↔ một cạnh nào cắt nhau ở một điểm không phải là đỉnh của đồ thị (việc 1 A vẽ đồ thị trên mặt phẳng gọi là biểu diễn phẳng của đồ thị)  2 Ví dụ: Đồ thị G: 2 2  B 1 5 K3,3 Vẽ lại G 3 3 4 5 C 3 “Tồn tại hay không cách vẽ đồ thị phân đôi đầy đủ K3,3 trên 4 1 một mặt phẳng sao cho không có hai cạnh nào cắt nhau?” G Một biểu diễn phẳng của G Khái niệm và định nghĩa 1 2  Biểu diễn phẳng của G và Q3 (Xem như bài tập) G  Gợi ý cách c/m K3,3 không phẳng: 4 3 Biểu diễn phẳng của G? - Ta thấy, trong mọi biểu diễn phẳng của K3,3, v1 và v2 E F luôn kề với v4, v5. v3 phải nằm trong các vùng F1 hoặc F2 A B Q3 v1 v5 H G C Biểu diễn phẳng của Q3? R1 D R2 v4 v2 K3,3 Biểu diễn phẳng của K3,3 7? 8 2
24/10/2013 v1 v5 R1 Cạnh (v3,v6) phải cắt ít v1 v5 Cạnh (v2,v6) phải cắt ít R22 nhất 1 trong 2 cạnh R11 v6 nhất 1 trong 2 cạnh (v4,v2), (v2,v5) v3 R2 v6 (v4,v3), (v3,v5) v4 v2 R12 R21 v5 TH1:v3 nằm trong R1 v4 v2 v1 v5 v1 v5 v3 v1 v5 R2 R11 R11 Cạnh (v1,v6) phải cắt ít TH2:v3 nằm trong R2 R1 v3 R2 v3 R2 nhất 1 trong 2 cạnh R22 Cạnh (v1,v6) phải cắt ít R12 R12 v6 (v4,v3), (v3,v5) v1 v5 v5 nhất 1 trong 2 cạnh v6 v4 v2 v4 R1 (v4,v2), (v2,v5) v2 v4 v2 v1 v5 R21 R2 R11 Cạnh (v3,v6) phải cắt ít v1 v3 v5 v3 R2 v4 v2 nhất 1 cạnh R12 R21 R1 v5 9 R22 Cạnh (v2,v6) phải cắt v4 v2 v3 R22 ít nhất 1 cạnh khác v6 R2 v4 v2 R21 v6 10 v6 v3 Khái niệm và định nghĩa Khái niệm và định nghĩa Cho G là đồ thị phẳng: Ví dụ:  Các cạnh của đồ thị chia mặt 5 6 1 2 miền 3 phẳng thành các miền (Region) 5 F2 6 miền 1 2  Phần giới hạn bởi một chu trình 1 Vẽ lại Miền 2 đơn không chứa bên trong một chu 8 F5 F1 F3 trình đơn khác được gọi là một 8 7 miền hữu hạn. F6 F4 7 miền 1, miền 2: hữu hạn  Mọi đồ thị phẳng luôn có một 4 3 4 Q3 3 miền 3: vô hạn miền vô hạn duy nhất. Q3 Q3 là đồ thị Phẳng (5,4),(4,2),(2,5):  Chu trình giới hạn miền gọi là Biên của miền 1 F1, F2, F3, F4, F5: các miền hữu hạn biên của miền F6: Miền vô hạn 3
24/10/2013 Bài tập Một số ứng dụng của đồ thị phẳng  Trong các đồ thị sau, đồ thị nào là phẳng? Nếu đồ thị là  Sản xuất bảng mạch điện tử: phẳng, hãy biểu diễn phẳng nó?  Biểu diễn bằng đồ thị:  Mỗi đỉnh ↔ mỗi thành phần của board mạch  Mỗi cạnh ↔ một nối giữa 2 thành phần Nếu biểu diễn được mạch bằng một đồ thị phẳng  có thể in trên một bảng mạch đơn (single board) G1 G2 G3 Nếu không biểu diễn được mạch bằng đồ thị phẳng  Có thể chia đồ thị thành các đồ thị con phẳng  sử dụng bảng mạch đa lớp (chi phí in mạch sẽ lớn hơn) 13 14 Một số ứng dụng của đồ thị phẳng 2. Công thức Euler (Euler’s Fomula)  Xây dựng mạng giao thông: Giả sử cần xây dựng một Cho G là đơn đồ thị phẳng liên thông với m cạnh, n đỉnh, r mạng giao thông kết nối một nhóm các thành phố miền (trên biểu diễn phẳng của G)  Biểu diễn bằng đồ thị: Khi đó: n–m+r=2  Mỗi đỉnh ↔ một thành phố  Mỗi cạnh ↔ một đường đi trực tiến giữa hai thành phố c/m: Ta bỏ một số cạnh của G để thu được cây khung G’ của G  Nếu biểu diễn được bằng một đồ thị phẳng  không cần - Khi bỏ 1 cạnh, số miền cũng giảm 1 phải xây các cầu vượt (hầm chui) 2 2 5 5 R2 R2,3 4 3 4 3 R1 R3 R1 15 1 1 4
24/10/2013 2. Công thức Euler 2. Công thức Euler - Biểu thức: Hệ quả 1: G là một đồ thị phẳng với n đỉnh, m cạnh, r miền, p là số thành phần liên thông. Khi đó (Số đỉnh – số cạnh + số miền) = n-(m-1)+(r-1) = m-n+r ta có: (Có giá trị không thay đổi khi bỏ bớt cạnh) n-m + r= p + 1 Cây khung G’ của G có số đỉnh vẫn là n, số cạnh là n-1, số miền là 1. Như vậy: n – m + r= n – (n-1) + 1 = 2 R1 R4 2 5 F2,3 R2 4 3 F1 R3 n–m+r=p+1 7–8+4=2+1 1 P=2; r=4; n=7; m=8 2. Công thức Euler 3. Một số đồ thị không phẳng  Ví dụ: Một đơn đồ thị liên thông, phẳng G có 20 đỉnh,  Các đồ thị K1, K2, K3, K4 là các đồ thị phẳng. Đồ mỗi đỉnh có bậc 3. Một biểu diễn phẳng của đồ thị G thị K5 không là đồ thị phẳng chia đồ thị G thành bao nhiêu miền?  Đồ thị Km,n (m,n≥3) không là đồ thị phẳng Ví dụ: K3,3 19 K3,3 không là đồ thị phẳng 20 5
24/10/2013 3. Một số đồ thi không phẳng 3. Một số đồ thi không phẳng Định lý: Cho H là đồ thị con của đồ thị G: Như vậy: Một đồ thi G không phẳng nếu nó đồ o Nếu G phẳng thì H phẳng thị con là K3,3 hoặc K5 o Nếu H không phẳng thì G không phẳng Ví dụ: Cho đồ thi G như sau G không phẳng vì K3,3≤G, K3,3 G không phẳng 4. Bất đẳng thức EV 5. Định lý KURATOWSKI 5.1. Phép phân chia sơ cấp: Bất đẳng thức EV (The Edges-Vertices Inequality): Cho đồ thị phẳng G = (V,E). Phép bỏ đi 1 cạnh (u, v) ∈ E Cho G là đồ thị liên thông có n đỉnh, m cạnh và đai và thêm vào đỉnh w và 2 cạnh (u,w), (w, v) được gọi là phép là g≥3. Nếu G phẳng thì ta có bất đẳng thức: phân chia sơ cấp (elementary subdivision). g m ( n  2) g 2 u w v 6
24/10/2013 5. Định lý KURATOWSKI 5. Định lý KURATOWSKI 5.2. Các đồ thị đồng phôi 5.3. Định lý Kuratowski: Đồ thị G’ được gọi là đồng phôi (homeomorphic) với đồ thị G Một đồ thị là đồ thị phẳng khi và chỉ khi nó không chứa đồ nếu G’ có đuộc từ G bằng một chuỗi các phép chia sơ cấp thị con đồng phôi với K3,3 và K5 Ví dụ: a b a b a b Ví dụ: Đồ thị G sau đây không phẳng vì chứa đồ thị con đồng phôi với K5 h i k f g g j d e c d e c d e G1 G2 G3 G2 , G2 và G3 là hai đồ thị đồng phôi G H≤G, H đồng phôi với K5 Trong các đồ thị sau, đồ thị nào phẳng, đồ thị nào không phẳng? Vẽ lại đồ thi nào là phẳng sao cho không có cạnh cắt nhau ngoài đỉnh G1 G2 G3 G4 27 28 7
24/10/2013 Tô màu đồ thị Tô màu đồ thị Bài toán: Để phân biệt các miền trên bản đồ ta phải tô màu Mô hình hoá bài toán: chúng bằng các màu khác nhau. + Mỗi miền tương ứng một đỉnh của đồ thị. Hỏi cần ít nhất bao nhiêu màu để tô một bản đồ bất kỳ sao + Hai đỉnh có cạnh nối nếu chúng là hai miền có chung biên cho các miền kề nhau không cùng một màu. Đồ thị nhận được gọi là đồ thị đối ngẫu của bản đồ. + Đồ thị đối ngẫu của bản đồ là đồ thị phẳng. B B D B B C G A C C A E F F E C A E D E D D Tô màu đồ thị Tô màu đồ thị Bài toán tương đương: tô màu các đỉnh của đồ thị sao cho Định nghĩa: số màu của một đồ thị G (kí hiệu :(G)) là số màu tối thiểu cần để tô màu đồ thị G hai đỉnh kề nhau thì được tô bởi hai màu khác nhau và số lượng màu sử dụng là ít nhất Ví dụ: Xét đồ thị G: R B Số màu của đồ Định nghĩa: Tô màu một đơn đồ thị là gán mỗi màu cho một thị G là 2 đỉnh của đồ thị sao cho không có 2 đỉnh kề được gán cùng R một màu . R B B Định lý 4 màu: số màu của một đồ thị phẳng bất kỳ là một số Ví dụ: không lớn hơn 4. R W Nhận xét: - Số màu của đồ thị lưỡng phân là 2 màu. R - Số màu của đồ thị đầy đủ Kn là n màu 8
24/10/2013 7. Ứng dụng của tô màu đồ thị trong bài toán Ví dụ: Tìm số màu của các đồ thị sau: lập lịch thi Hãy lập lịch thi trong trường đại học sao cho không có sinh viên nào phải thi đồng thời hai môn cùng một lúc Mô hình hoá bài toán: - Mỗi đỉnh là một môn thi - Hai đỉnh có cạnh nối nếu đó là hai môn mà một sinh viên K4,2 nào đó phải thi. K5 - Thời gian mỗi môn thi ứng với một màu. Bài toán trở thành bài toán tô màu cho đồ thị trên sao cho hai đỉnh kề nhau có màu khác nhau. G H 33 Ví dụ:  Giả sử có 7 môn cần xếp lịch thi, được đánh số từ 1 đến 7. G là đồ thị biểu diễn việc xếp lịch thi cho các sv Nhận xét: Số màu của đồ thị là 4  Sử dụng 4 thời gian khác nhau để xếp lịch Thứ tự thời gian Các môn I 1,6 II 2 II 3,5 35 36 IV 4,7 9

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.