Bài giảng Toán rời rạc ứng dụng trong tin học - Chương 3: Đồ thị phẳng và bài toán tô màu đồ thị trình bày khái niệm đồ thị phẳng, tô màu đồ thị,. Tham khảo nội dung bài giảng để nắm bắt nội dung chi tiết. | TOÁN RỜI RẠC ỨNG DỤNG TRONG TIN HỌC ĐỒ THỊ PHẲNG VÀ CÁC BÀI TOÁN VỀ TÔ MÀU ĐỒ THỊ ĐỒ THỊ PHẲNG Bài toán Tìm cách làm cho các con đường đi dẫn từ 3 ngôi nhà tới 3 cái giếng sao cho không có 2 con đường nào cắt nhau? Mô hình bài toán Đỉnh: các gia đình và giếng nước Cạnh: đường đi từ nhà đến các giếng Có thể vẽ đồ thị mà không có 2 cạnh nào cắt nhau? ĐỒ THỊ PHẲNG Đồ thị phẳng Một đồ thị được gọi là phẳng nếu nó có thể vẽ được trên một mặt phẳng mà không có các cạnh nào cắt nhau ở điểm không phải là điểm mút của mỗi cạnh. Hình vẽ như vậy được gọi là một biểu diễn phẳng của đồ thị. ĐỒ THỊ PHẲNG Đồ thị phẳng Ví dụ Đồ thị sau có phải là đồ thị phẳng không? ĐỒ THỊ PHẲNG Đồ thị phẳng Ví dụ Đồ thị sau có phải là đồ thị phẳng không? ĐỒ THỊ PHẲNG Đồ thị phẳng Ví dụ Chứng minh K3,3 không phẳng. ĐỒ THỊ PHẲNG Đồ thị phẳng Công thức Euler Tất cả biểu diễn phẳng của cùng một đồ thị có số miền bằng nhau Định lý 1 Trong đơn đồ thị phẳng, liên thông thì r = e – v + 2 r: số miền e: số cạnh v: số đỉnh ĐỒ THỊ PHẲNG Công thức Euler Chứng minh Xây dựng dãy đồ thị con của G G1 e1 Gi = Gi-1 ei (i = 2,3, , e) G Ge Quy nạp Định lý đúng với G1 Giả sử Gn phẳng thỏa rn = en vn + 2 Xét đồ thị phẳng Gn+1 Gn+1 = Gn (an+1, bn+1) ĐỒ THỊ PHẲNG Công thức Euler Chứng minh Xét đồ thị phẳng Gn+1 Gn+1 = Gn (an+1, bn+1) Nếu an+1, bn+1 đều thuộc Gn an+1, bn+1 nằm trên miền biên của miền chung rn+1 = rn + 1 en+1 = en + 1 vn+1 = vn rn+1 = en+1 vn+1 + 2. ĐỒ THỊ PHẲNG Công thức Euler Chứng minh Xét đồ thị phẳng Gn+1 Gn+1 = Gn (an+1, bn+1) Nếu bn+1 (hoặc an+1) không thuộc Gn Chỉ có an+1 nằm trên miền biên của miền chung rn+1 = rn en+1 = en + 1 vn+1 = vn + 1 rn+1 = en+1 vn+1 + 2. ĐỒ THỊ PHẲNG Công thức Euler Ví dụ Tính số miền trong một đơn đồ thị phẳng liên thông có 8 đỉnh và mỗi đỉnh đều có bậc 3 ĐỒ THỊ PHẲNG Công thức Euler Hệ quả 1 Cho G là một đơn đồ thị phẳng liên thông với e cạnh và v đỉnh; v 3. Khi đó: e 3v 6. Chứng minh: Trong một đồ . | TOÁN RỜI RẠC ỨNG DỤNG TRONG TIN HỌC ĐỒ THỊ PHẲNG VÀ CÁC BÀI TOÁN VỀ TÔ MÀU ĐỒ THỊ ĐỒ THỊ PHẲNG Bài toán Tìm cách làm cho các con đường đi dẫn từ 3 ngôi nhà tới 3 cái giếng sao cho không có 2 con đường nào cắt nhau? Mô hình bài toán Đỉnh: các gia đình và giếng nước Cạnh: đường đi từ nhà đến các giếng Có thể vẽ đồ thị mà không có 2 cạnh nào cắt nhau? ĐỒ THỊ PHẲNG Đồ thị phẳng Một đồ thị được gọi là phẳng nếu nó có thể vẽ được trên một mặt phẳng mà không có các cạnh nào cắt nhau ở điểm không phải là điểm mút của mỗi cạnh. Hình vẽ như vậy được gọi là một biểu diễn phẳng của đồ thị. ĐỒ THỊ PHẲNG Đồ thị phẳng Ví dụ Đồ thị sau có phải là đồ thị phẳng không? ĐỒ THỊ PHẲNG Đồ thị phẳng Ví dụ Đồ thị sau có phải là đồ thị phẳng không? ĐỒ THỊ PHẲNG Đồ thị phẳng Ví dụ Chứng minh K3,3 không phẳng. ĐỒ THỊ PHẲNG Đồ thị phẳng Công thức Euler Tất cả biểu diễn phẳng của cùng một đồ thị có số miền bằng nhau Định lý 1 Trong đơn đồ thị phẳng, liên thông thì r = e – v + 2 r: số miền e: .
