Đồ thị phẳng – Wikipedia tiếng Việt

Trong lý thuyết đồ thị, một đồ thị phẳng là một đồ thị có thể được nhúng vào mặt phẳng, tức là có thể được vẽ trên mặt phẳng sao cho các cạnh chỉ gặp nhau ở các đỉnh.

Từ thời xưa đã lưu truyền một bài toán cổ ” Ba nhà, ba giếng ” : Có ba nhà ở gần ba cái giếng, nhưng không có đường nối thẳng những nhà với nhau cũng như không có đường nối thẳng những giếng với nhau. Có lần bất hoà với nhau, họ tìm cách làm những đường khác đến giếng sao cho những đường này đôi một không giao nhau. Họ có triển khai được dự tính đó không ?
Bài toán ba nhà

Mạch in điện tử

Bài toán thực tiễn : Có 3 mái ấm gia đình, 3 nhà sản xuất điện, nước, gas. Các mái ấm gia đình đều cần điện, nước, gas và đều muốn đi dây riêng, do đó cần nối dây từ mái ấm gia đình đến những nhà sản xuất sao cho không dây nào cắt dây nào .Ngày nay cũng có những bài toán tựa như như bài toán đi dây trong mạch in .

Thiết lập bài toán[sửa|sửa mã nguồn]

Bài toán này có thể được mô hình bằng đồ thị phân đôi đầy đủ

K

3
,
3

{\displaystyle K_{3,3}}

{\displaystyle K_{3,3}}. Câu hỏi ban đầu có thể diễn đạt như sau: Có thể vẽ

K

3
,
3

{\displaystyle K_{3,3}}

trên một mặt phẳng sao cho không có hai cạnh nào cắt nhau (ở một điểm không phải là điểm mút của các cạnh)?

Tổng quát :

  • Có thể vẽ một đồ thị trên một mặt phẳng không? Có các cạnh nào cắt nhau không?
  • Khi nào có thể tìm được ít nhất một cách biểu diễn đồ thị không có cạnh cắt nhau?

Đồ thị phẳng[sửa|sửa mã nguồn]

Một đồ thị được gọi là một đồ thị phẳng nếu ta có thể vẽ nó trên mặt phẳng sao cho các cạnh của nó không cắt nhau ngoài ở đỉnh. Cách vẽ như vậy sẽ được gọi là biểu diễn phẳng của đồ thị. Ví dụ

K

4

{\displaystyle K_{4}}

{\displaystyle K_{4}} là một đồ thị phẳng.

Điều kiện cần và đủ để đồ thị là phẳng được chỉ ra trong định lý Kuratowski [ 1 ] :

Đồ thị là phẳng khi và chỉ khi nó không chứa đồ thị con đồng phôi với K 3, 3 { \ displaystyle K_ { 3,3 } }K 5 { \ displaystyle K_ { 5 } }{\displaystyle K_{5}}

Trong trong thực tiễn việc sử dụng định lý Kuratowski để kiểm tra đồ thị có phải là đồ thị phẳng hay không thì rất khó khăn vất vả. Tuy nhiên, sống sót thuật toán để kiểm tra yếu tố này. Xét đồ thị phẳng với n đỉnh và p cạnh, ta có :

Định lý 1. Nếu n ≥ 3 thì p ≤ 3n – 6.
Ðịnh lý 2. Nếu n ≥ 3 và không có chu trình có độ dài 3, thì p ≤ 2n – 4.

Công thức Euler cho đồ thị phẳng[sửa|sửa mã nguồn]

Euler đã chứng minh được rằng các biểu diễn phẳng khác nhau của một đồ thị đều chia mặt phẳng ra thành cùng một số miền qua định lý sau (thường được gọi là công thức Euler):

Giả sử một đồ thị phẳng liên thông có n đỉnh, m cạnh, r miền. Khi đó r=m-n+2.

Chứng minh : Cho G là đồ thị phẳng liên thông có n đỉnh, m cạnh và r miền. Ta bỏ 1 số ít cạnh của G để được một cây khung của G. Mỗi lần ta bỏ một cạnh ( m giảm 1 ) thì số miền của G cũng giảm 1 ( r giảm 1 ), còn số đỉnh của G không biến hóa ( n không đổi ). Như vậy, giá trị của biểu thức n – m + r không biến hóa trong suốt quy trình ta bỏ bớt cạnh của G để được một cây. Cây này có n đỉnh, do đó có n – 1 cạnh và cây chỉ có một miền, thế cho nên : n – m + r = n – ( n – 1 ) + 1 = 2 .

Hệ thức n – m + r = 2 thường gọi là hệ thức Euler cho hình đa diện, vì được Euler chứng minh đầu tiên cho hình đa diện có n đỉnh, m cạnh và r mặt.

Một hệ quả đơn thuần là :

Trong một đồ thị phẳng liên thông luôn tồn tại ít nhất một đỉnh có bậc không vượt quá 5.

Chứng minh : Trong đồ thị phẳng mỗi miền được bao bằng tối thiểu 3 cạnh. Mặt khác, mỗi cạnh hoàn toàn có thể nằm trên biên của tối đa hai miền. Gọi d là số miền, thì 3 d ≤ 2 p. Nếu trong đồ thị phẳng mà toàn bộ những đỉnh đều có bậc không nhỏ hơn 6 thì do mỗi đỉnh của đồ thị phải là đầu mút của tối thiểu 6 cạnh mà mỗi cạnh lại có hai đầu mút nên ta có 6 n ≤ 2 p hay 3 n ≤ p. Từ đó suy ra 3 d + 3 n ≤ 2 p + p hay d + n ≤ p, trái với hệ thức Euler d + n = p + 2 .

Đồ thị không phẳng[sửa|sửa mã nguồn]

Định lý: Đồ thị K 3, 3 { \ displaystyle K_ { 3,3 } }

Chứng minh : Giả sử K 3, 3 { \ displaystyle K_ { 3,3 } } là đồ thị phẳng. Khi đó ta có một đồ thị phẳng với 6 đỉnh ( n = 6 ) và 9 cạnh ( p = 9 ), nên theo hệ thức Euler đồ thị có số miền là d = p-n+2 = 5. Ở đây, mỗi cạnh chung cho hai miền. Bằng kiểm tra trực tiếp ta thấy không hề có miền tạo ra từ 3 cạnh, do đó mỗi miền có tối thiểu 4 cạnh. Do đó 4 d ≤ 2 p, tức là 4×5 ≤ 2×9, vô lý .Như vậy định lý này cho ta giải thuật của bài toán ” Ba nhà ba giếng “, nghĩa là không hề triển khai được việc làm những đường khác đến giếng sao cho những đường này đôi một không giao nhau .

Định lý: Đồ thị

K

5

{\displaystyle K_{5}}

Chứng minh : Giả sử K 5 { \ displaystyle K_ { 5 } } là đồ thị phẳng. Khi đó ta có một đồ thị phẳng với 5 đỉnh ( n = 5 ) và 10 cạnh ( p = 10 ), nên theo hệ thứcEuler đồ thị có số miền là d = p-n+2 = 7. Trong K 5 { \ displaystyle K_ { 5 } }, mỗi miền có tối thiểu 3 cạnh, mỗi cạnh chung cho 2 miền, thế cho nên 3 d ≤ 2 n, tức là 3×7 ≤ 2×10, vô lý .

Tô màu đồ thị[sửa|sửa mã nguồn]

Tô màu map[sửa|sửa mã nguồn]

Mỗi map hoàn toàn có thể coi là một đồ thị phẳng. Trong một map, ta coi hai miền có chung nhau một đường biên giới là hai miền kề nhau ( hai miền chỉ có chung nhau một điểm biên không được coi là kề nhau ). Một map thường được tô màu, sao cho hai miền kề nhau được tô hai màu khác nhau. Ta gọi một cách tô màu map như vậy là một cách tô màu đúng .Để bảo vệ chắc như đinh hai miền kề nhau không khi nào có màu trùng nhau, tất cả chúng ta tô mỗi miền bằng một màu khác nhau. Tuy nhiên việc làm đó nói chung là không hài hòa và hợp lý. Nếu map có nhiều miền thì sẽ rất khó phân biệt những màu gần giống nhau. Do vậy người ta chỉ dùng một số ít màu thiết yếu để tô map. Một bài toán được đặt ra là : xác lập số màu tối thiểu cần có để tô màu đúng một map .

Tô màu đồ thị[sửa|sửa mã nguồn]

Mỗi map trên mặt phẳng hoàn toàn có thể màn biểu diễn bằng một đồ thị, trong đó mỗi miền của map được màn biểu diễn bằng một đỉnh ; những cạnh nối hai đỉnh, nếu những miền được trình diễn bằng hai đỉnh này là kề nhau. Đồ thị nhận được bằng cách này gọi là đồ thị đối ngẫu của map đang xét. Rõ ràng mọi map trên mặt phẳng đều có đồ thị đối ngẫu phẳng. Bài toán tô màu những miền của map là tương tự với bài toán tô màu những đỉnh của đồ thị đối ngẫu sao cho không có hai đỉnh liền kề nhau có cùng một màu, mà ta gọi là tô màu đúng những đỉnh của đồ thị .

Định lý 4 màu của Appel-Haken: Mọi đồ thị phẳng đều có thể tô đúng bằng 4 màu.

Định lý Bốn màu tiên phong được đưa ra như một phỏng đoán vào năm 1850 bởi một sinh viên người Anh tên là F. Guthrie và ở đầu cuối đã được hai nhà toán học Mỹ là Kenneth Appel và Wolfgang Haken chứng tỏ vào năm 1976. Trước năm 1976 cũng đã có nhiều chứng tỏ sai, mà thường thì rất khó tìm thấy chỗ sai, đã được công bố. Hơn thế nữa đã có nhiều nỗ lực một cách vô ích để tìm phản thí dụ bằng cách cố tìm map mà cần hơn bốn màu để tô nó .Có lẽ một trong những chứng tỏ sai nổi tiếng nhất trong toán học là chứng tỏ sai bài toán bốn màu được công bố năm 1879 bởi luật sư, nhà toán học nghiệp dư Luân Đôn tên là Alfred Kempe. Nhờ công bố giải thuật của ” bài toán bốn màu “, Kempe được công nhận là hội viên Hội Khoa học Hoàng gia Anh. Các nhà toán học gật đầu cách chứng tỏ của ông ta cho tới 1890, khi Percy Heawood phát hiện ra sai lầm đáng tiếc trong chứng tỏ của Kempe. Mặt khác, dùng chiêu thức của Kempe, Heawood đã chứng tỏ được ” bài toán năm màu ” ( tức là mọi map hoàn toàn có thể tô đúng bằng 5 màu ) .

Định lý 5 màu của Kempe-Heawood: Mọi đồ thị phẳng đều có thể tô đúng bằng 5 màu.

Chứng minh : Cho G là một đồ thị phẳng. Không mất đặc thù tổng quát hoàn toàn có thể xem G là liên thông và có số đỉnh n ≥ 5. Ta chứng tỏ G được tô đúng bởi 5 màu bằng quy nạp theo n .Trường hợp n = 5 là hiển nhiên. Giả sử định lý đúng cho toàn bộ những đồ thị phẳng có số đỉnh nhỏ hơn n. Xét G là đồ thị phẳng liên thông có n đỉnh .

Theo Hệ quả ở trên, trong G tồn tại đỉnh a với deg(a) ≤ 5. Xoá đỉnh a và các cạnh liên thuộc với nó, ta nhận được đồ thị phẳng G’ có n−1 đỉnh. Theo giả thiết quy nạp, có thể tô đúng các đỉnh của G’ bằng 5 màu. Sau khi tô đúng G’ rồi, ta tìm cách tô đỉnh a bằng một màu khác với màu của các đỉnh kề nó, nhưng vẫn là một trong 5 màu đã dùng. Điều này luôn thực hiện được khi deg(a) < 5 hoặc khi deg(a)=5 nhưng 5 đỉnh kề a đã được tô bằng 4 màu trở xuống.

Chỉ còn phải xét trường hợp deg ( a ) = 5 mà 5 đỉnh kề a là b, c, d, e, f đã được tô bằng 5 màu rồi. Khi đó trong 5 đỉnh b, c, d, e, f phải có 2 đỉnh không kề nhau, vì nếu 5 đỉnh đó đôi một kề nhau thì b c d e f là đồ thị rất đầy đủ K5 và đây là một đồ thị không phẳng, do đó G không phẳng, trái với giả thiết. Giả sử b và d không kề nhau ( Hình 1 ) .Xoá 2 đỉnh b và d và cho kề a những đỉnh trước đó kề b hoặc kề d mà không kề a ( Hình 2 ), ta được đồ thị mới G ’ ’ có n − 2 đỉnh. Theo giả thiết quy nạp, ta hoàn toàn có thể tô đúng G ’ ’ bằng 5 màu. Sau khi những đỉnh của G ’ ’ được tô đúng rồi ( Hình 2 ), ta dựng lại 2 đỉnh b và d, rồi tô b và d bằng màu đã tô cho a ( màu 1, Hình 3 ), còn a thì được tô lại bằng màu khác với màu của b, c, d, e, f. Vì b và d không kề nhau đã được tô bằng cùng màu 1, nên với 5 đỉnh này chỉ mới dùng hết nhiều lắm 4 màu .. Do đó G được tô đúng bằng 5 màu .Như vậy, Heawood mới giải được bài toán năm màu, còn bài toán bốn màu vẫn còn đó và là một thách đố so với những nhà toán học trong suốt gần một thế kỷ. Việc tìm giải thuật của bài toán bốn màu đã tác động ảnh hưởng đến sự tăng trưởng theo khunh hướng khác nhau của triết lý đồ thị .Mãi đến năm 1976, khai thác chiêu thức của Kempe và nhờ công cụ máy tính điện tử, Appel và Haken đã tìm ra giải thuật của ” bài toán bốn màu “. Chứng minh của họ dựa trên sự nghiên cứu và phân tích từng trường hợp một cách cẩn trọng nhờ máy tính. Họ đã chỉ ra rằng nếu ” bài toán bốn màu ” là sai thì sẽ có một phản thí dụ thuộc một trong gần 2000 loại khác nhau và đã chỉ ra không có loại nào dẫn tới phản thí dụ cả. Trong chứng tỏ của mình họ đã dùng hơn 1000 giờ máy. Cách chứng tỏ này đã gây ra nhiều cuộc tranh cãi vì máy tính đã đóng vai trò quan trọng trong chứng tỏ này. Chẳng hạn, liệu hoàn toàn có thể có sai lầm đáng tiếc trong chương trình và điều đó dẫn tới hiệu quả sai không ? Lý luận của họ có thực sự là một chứng tỏ hay không, nếu nó phụ thuộc vào vào thông tin ra từ một máy tính không đáng an toàn và đáng tin cậy ?
Những ứng dụng của bài toán tô màu đồ thị :

  • 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 có hai môn thi cùng một lúc.

Có thể giải bài toán lập lịch thi bằng quy mô đồ thị, với những đỉnh là những môn thi, có một cạnh nối hai đỉnh nếu có sinh viên phải thi cả hai môn được màn biểu diễn bằng hai đỉnh này. Thời gian thi của mỗi môn được biểu lộ bằng những màu khác nhau. Như vậy việc lập lịch thi sẽ tương ứng với việc tô màu đồ thị này .Chẳng hạn, có 7 môn thi cần xếp lịch. Giả sử những môn học được đánh số từ 1 tới 7 và những cặp môn thi sau có chung sinh viên : 1 và 2, 1 và 3, 1 và 4, 1 và 7, 2 và 3, 2 và 4, 2 và 5, 2 và 7, 3 và 4, 3 và 6, 3 và 7, 4 và 5, 4 và 6, 5 và 6, 5 và 7, 6 và 7. Hình dưới đây màn biểu diễn đồ thị tương ứng. Việc lập lịch thi chính là việc tô màu đồ thị này. Vì số màu của đồ thị này là 4 nên cần có 4 đợt thi .

  • Phân chia tần số: Các kênh truyền hình từ số 1 tới số 12 được phân chia cho các đài truyền hình sao cho không có đài phát nào cách nhau không quá 240 km lại dùng cùng một kênh. Có thể chia kênh truyền hình như thế nào bằng mô hình tô màu đồ thị.

Ta thiết kế xây dựng đồ thị bằng cách coi mỗi đài phát là một đỉnh. Hai đỉnh được nối với nhau bằng một cạnh nếu chúng ở cách nhau không quá 240 km. Việc phân loại kênh tương ứng với việc tô màu đồ thị, trong đó mỗi màu biểu lộ một kênh .

  • Các thanh ghi chỉ số: Trong các bộ dịch hiệu quả cao việc thực hiện các vòng lặp được tăng tốc khi các biến dùng thường xuyên được lưu tạm thời trong các thanh ghi chỉ số của bộ xử lý trung tâm (CPU) mà không phải ở trong bộ nhớ thông thường. Với một vòng lặp cho trước cần bao nhiêu thanh ghi chỉ số? Bài toán này có thể giải bằng mô hình tô màu đồ thị. Để xây dựng mô hình ta coi mỗi đỉnh của đồ thị là một biến trong vòng lặp. Giũa hai đỉnh có một cạnh nếu các biến biểu thị bằng các đỉnh này phải được lưu trong các thanh ghi chỉ số tại cùng thời điểm khi thực hiện vòng lặp. Như vậy số màu của đồ thị chính là số thanh ghi cần có vì những thanh ghi khác nhau được phân cho các biến khi các đỉnh biểu thị các biến này là liền kề trong đồ thị.

Đồ thị phẳng có nhiều ứng dụng quan trọng trong công nghệ chế tạo mạch in. Biểu diễn phẳng của đồ thị sẽ chia mặt phẳng ra làm các miền, bao gồm cả miền không bị chặn.

Ngoài ra, một trong những ứng dụng là ánh xạ từ ảnh số 2 chiều sang một đồ thị phẳng. Trong đó, ảnh số được màn biểu diễn dưới dạng ma trận lưới ô vuông ; mỗi ô đặc trưng cho 1 px .

  1. ^

    Adams, Colin; Franzosa, Robert (2008). Topology, pure and applied. Prentice-Hall.

  • Adams and Franzosa, Topology, pure and applied, 2008.
  • Đỗ Văn Nhơn, Toán rời rạc, Nhà xuất bản ĐHQG Thành phố Hồ Chí Minh, 2006.

Source: https://tmsquynhon.com.vn
Category: CRYPTO

Trả lời

Email của bạn sẽ không được hiển thị công khai.