Log in to Mathigon

Google
Create New Account

Reset Password     

Chia sẻ

Thay đổi ngôn ngữ

EnglishVietnamese

Send us Feedback

Please let us know if you have any feedback and suggestions, or if you find any errors and bugs in our content.

Sorry, your message couldn’t be submitted. Please try again!

Thanks for your feedback!

Reset Progress

Are you sure that you want to reset your progress, response and chat data for all sections in this course? This action cannot be undone.

Bảng chú giải

Select one of the keywords on the left…

Các bản dịch vẫn đang được phát triển và có thể không đầy đủ.

Đồ thị và Mạng lướiĐồ thị phẳng

Tiết lộ tất cả các bước

Sau đây là một bài toán khác liên quan đến lý thuyết đồ thị.

Trong một ngôi làng nhỏ có 3 nhà máy sản xuất nước, gas và điện. Trong làng cũng có 3 ngôi nhà là khách hàng tiềm năng. Do kết cấu xây dựng của làng, các ống dẫn không được phép cắt ngang nhau.

Hãy thử kết nối các nhà máy với nhà của khách hàng sao cho các đường dẫn không cắt ngang nhau:

Cũng như bài toán của thị trấn Königsberg ở trên, bạn nhận ra rằng không có cách nào là khả thi. Dường như một số đồ thị có các cạnh không cắt nhau – gọi là đồ thị phẳng – còn một số đồ thị khác như bài toán ở trên thì không thể.

K3 là đồ thị phẳng.

K4 là đồ thị phẳng không là đồ thị phẳng.

K5 là đồ thị phẳngkhông là đồ thị phẳng.

Đồ thị hoàn chỉnh K5 là đồ thị phẳng nhỏ nhất. Tất cả những đồ thị nào có đồ thị con là K5 thì không phải là đồ thị phẳng. Bao gồm K6, K7, và tất cả các đồ thị lớn hơn khác.

Đồ thị trong bài toán đố về các nhà máy ở trên là đồ thị hai phía K3,3. Hóa ra rằng tất cả các đồ thị không phẳng nào cũng có đồ thị con là K5 hoặc K3,3 hoặc có đồ thị con là đồ thị phân chia của hai đồ thị này.

Planarity

Đây là đồ thị phẳng nhưng ${n} đỉnh đã bị xáo trộn. Hãy sắp xếp lại các cạnh này sao cho chúng không cắt nhau.