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

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ể.

Đồ 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.

Công thức Euler

Tất cả các đồ thị phẳng chia mặt phẳng thành nhiều vùng khác nhau, được gọi là các mặt.

Khi so sánh các con số này, bạn sẽ nhận thấy rằng số cạnh luôn ít hơn mộtlớn hơnbằng số mặt cộng với số đỉnh. Hay nói cách khác, F + V = E + 1. Kết quả này được gọi là phương trình Euler đặt theo tên của nhà toán học đã giải bài toán những cây cầu ở Königsberg.

Đáng tiếc là có vô vàn các đồ thị và chúng ta không thể kiểm chứng hết tất cả để chứng minh phương trình của Euler. Thay vào đó chúng ta có thể cố gắng tìm ra một bằng chứng đơn giản có thể áp dụng cho bất kỳ đồ thị nào…

Bất kỳ đồ thị (có giới hạn) nào đều có thể bắt đầu từ một đỉnh và thêm từng đỉnh mới vào. Chúng ta đã thấy rằng dù thêm đỉnh vào theo cách nào, phương trình Euler vẫn đúng. Do đó phương trình Euler cũng đúng với mọi loại đồ thị. Euler’s equation is valid. Therefore it is valid for all graphs.

Quy trình chúng ta vừa sử dụng để chứng minh phương trình Euler được gọi là phương pháp quy nạp Toán học. Đây là kỹ năng rất hữu dụng sử dụng để chứng minh kết quả của nhiều bài toán khác nhau, đơn giản chỉ bằng khởi điểm từ trường hợp đơn giản nhất, chứng minh kết quả vẫn đúng với mỗi bước phát triển lên thành trường hợp phức tạp hơn. .svg-block: include svg/dominoes.svg

Rất nhiều đồ thị phẳng trông tương tự như mạng lưới của hình đa diện, là những hình không gian ba chiều với đa diện các mặt. Nếu ta xem hình đa diện được làm từ những sợi dây cao su, chúng ta có thể tưởng tượng ra việc kéo chúng về một mặt phẳng, thành các đồ thị phẳng:

Điều này có nghĩa là chúng ta không những có thể sử dụng công thức Euler cho đồ thị phẳng mà còn có thể dùng cho tất cả các hình đa diện - với một điểm khác biệt nhỏ. Khi chúng ta chuyển hình đa diện thành đồ thị, một trong các mặt sẽ biến mất: đó là mặt trên cùng trở thành "vòng ngoài" của đồ thị.

Nói cách khác, nếu bạn đếm số cạnh, mặt and đỉnh của bất kỳ hình đa diện nào, bạn sẽ thấy rằng F + V = E + .