Rừng dẫn xuất trong đồ thị phẳng -- induced forests in planar graphs

Mình (ở đây "mình" ý nói tất cả tác giả trong paper, không phải chỉ có chủ thớt) mới có paper mới được accept vào tạp chí Graphs and Combinatorics về bài toán rừng dẫn xuất (induced forest) trong đồ thị phẳng (planar graphs). Bản submit của paper (chưa phải bản final, sẽ link sau khi có) bạn có thể tìm trong trang web cá nhân của Melissa, một trong 3 tác giả của paper. Bài toán chủ đề của paper là một conjecture đề xuất bởi Albertson và Berman năm 1976 [1].

Albertson-Berman Conjecture: Có thể xóa không quá n/2 đỉnh từ một đồ thị phẳng có n đỉnh sao cho phần còn lại là một rừng.

 

Đồ thị phẳng là đồ thị mà ta có thể vẽ trên một mặt phẳng sao cho không có hai cạnh nào cắt nhau (tại điểm không phải là đầu mút). Rừng (forest) là đồ thị (có thể không liên thông) không có chu trình. Xem ví dụ minh họa Albertson-Berman Conjecture trong Figure 1.
AB-conjecture
Figure 1:(a) Một đồ thị phẳng với 11 đỉnh. Nếu xóa 5 đỉnh tô màu hồng từ đồ thị thì ta sẽ thu được (hình (b)) một rừng (hay chính xác hơn là một cây).

Một phát biểu tương đương khác của Conjecture trên là:

Albertson-Berman Conjecture (equivalent formulation): Luôn tồn tại một rừng dẫn xuất có ít nhất n/2 đỉnh trong một đồ thị phẳng có n đỉnh.

 

Conjecture phát biểu khá đơn giản như vậy nhưng cho đến nay chưa ai chứng minh được nó đúng hay không. Nếu bạn muốn thử sức thì còn chở gì nữa! Lời giải của bài toán này chắc chắn sẽ làm bạn nổi tiếng, ít nhất là trong giới lý thuyết đồ thị, và có thể bạn sẽ có được ngay tấm bằng Ph.D. trong tay. Mình chỉ có một lưu ý là nhiều người đã thử nhưng chưa có ai thành công.

Paper của mình cũng không giải quyết được Conjecture này mà chỉ chứng minh được nó cho một trường hợp đặc biệt: đồ thị phẳng 2 lớp (2-outerplanar graphs). Đồ thị phẳng một lớp (outerplanar) là đồ thị phẳng mà mọi đỉnh đều nằm trên biên của mặt vô hạn (infinite face) của đồ thị. Đồ thị hai lớp là đồ thị mà sau khi bạn xóa đi tất cả các đỉnh trên biên của mặt vô hạn, bạn thu được đồ thị một lớp. Xem minh họa trong Figure 2.

outer-planar
Figure 2: (a) Một đồ thị phẳng một lớp. Tất cả các đỉnh đều nằm trên biên của mặt vô hạn. (b) Một đồ thị phẳng hai lớp. Lớp ngoài cùng (các đỉnh tô màu hồng) là các đỉnh nằm trên biên mặt vô hạn. Sau khi xóa các đỉnh màu hồng đi thì phần còn lại là đồ thị một lớp.

Chứng minh Albertson-Berman Conjecture cho đồ thị phẳng một lớp khá dễ, và thực sự ta có thể chứng minh tính chất mạnh hơn. Đây cũng chính là kết quả của Hosono [2]. Chi tiết coi như bài tập cho bạn đọc.

Problem 1: Chứng minh rằng ta có thể xóa không quá n/3 đỉnh từ đồ thị phẳng một lớp n đỉnh sao cho phần còn lại là một rừng.

 

Paper của mình, như đã nói ở trên, chứng minh Albertson-Berman Conjecture cho đồ thị hai lớp. Thực ra khi mới bắt đầu, mình không tìm ra cách nào để chứng minh trực tiếp Conjecture trên. Sau đó mình phát hiện ra là chứng minh một tính chất mạnh hơn lại dễ hơn (và mình đã thành công):

Theorem 1: Ta có thể phân hoạch tập đỉnh V của một đồ thị phẳng hai lớp thành hai phần A,B sao cho xóa toàn bộ tập đỉnh trong A hoặc toàn bộ tập đỉnh trong B, phần còn lại là một rừng.

 
Hai nói cách khác, ta có thể phân hoạch tập đỉnh thành hai phần A,B sao cho mỗi phần là một rừng dẫn xuất. Không khó để thấy Albertson-Berman Conjecture cho đồ thị phẳng hai lớp là hệ quả của Theorem 1 vì ít nhất một trong hai tập A,B có không quá n/2 đỉnh. Đôi khi làm bài toán khó hơn lại trở nên dễ giải hơn!

Phương pháp chứng minh trong paper của mình cũng không có gì cao siêu. Nó chỉ là một biến thể của phương pháp quy nạp mà bạn đã biết từ cấp 2 hoặc cấp 3. Cái khó là tìm ra quy luật để thực hiện quy nạp. Mình vẽ đồ thị có lẽ đến chục trang giấy trước khi tìm ra quy luật. Nếu bạn tò mò thì còn chờ gì nữa mà không đọc paper luôn thôi!!!!

Chứng minh Theorem 1 cho đồ thị phẳng một lớp cũng không quá khó và coi như bài tập cho bạn đọc.

Problem 2: Chứng minh Theorem 1 cho đồ thị phẳng một lớp.

 

Có thể bạn sẽ hỏi: liệu có thể tổng quát hóa Theorem 1 từ đồ thị 2 lớp lên đồ thì 3 lớp, 4 lớp, ..., nhiều lớp được không? Câu hỏi rất hay! Nhưng rất tiếc lời giải là không. Raspaud và Wang [3] tìm ra một đồ thị 3 lớp (Figure 3) mà ta không thể phân hoạch nó thành hai rừng dẫn xuất được.

3-outer-planar
Figure 3: Đồ thị phẳng 3 lớp mà ta không thể phân hoạch được thành hai rừng dẫn xuất. Hình được lấy từ paper của Raspaud và Wang [3].

Chuyện ngoài lề

Tác giả trong paper ngoài mình (chủ thớt) và advisor của mình (Glencora Borradaile), người thứ ba là Melissa. Tại thời điểm bắt đầu nghiên cứu về bài toán này, Melissa mới chỉ là một sinh viên đại học (undergraduate student) và là một bạn nữ. Melissa là visiting student trong lab mình thông qua chương trình REU (Research Experiences for Undergraduates) của quỹ khoa học quốc gia Mỹ (NSF). Thực sự đây là một chương trình rất hay cho undergraduate student và nếu Việt Nam mình có chương trình tương tự thì quá hay. (Nếu Việt Nam mình có mà mình không biết thì xin bạn đọc comment xuống dưới). Chương trình này là cơ hội để các sinh viên đại học tìm hiểu thế nào là research thực sự để họ có thể định hướng được sau khi tốt nghiệp có nên đi theo con đường research hay không. Nếu có định hướng nghiên cứu thì đây cũng là cơ hội để xin thư giới thiệu từ các mentor để apply các trường hàng đầu của Mỹ. Như trường hợp Melissa, bạn ấy đã apply thành công khoa toán của đại học UC Berkeley, và hiện đang làm nghiên cứu tiến sĩ tại trường này.

Tham khảo

[1] M. O. Albertson and D. M. Berman. A conjecture on planar graphs. Graph Theory and Related Topics (J. A. Bondy and U. S. R. Murty, eds.), (Academic Press, 1979), 357.
[2] K. Hosono. Induced forests in trees and outerplanar graphs. Proc. Fac. Sci. Tokai Univ. 25 (1990), 27--29.
[3] A. Raspaud and W. Wang. On the vertex-arboricity of planar graphs. European Journal of Combinatorics, 29:1064–1075, 2008.
[4] G. Borradaile, H. Le, M. Sherman-Bennett. Large induced acyclic and outerplanar subgraphs of low-treewidth planar graphs. Accepted to Graphs and Combinatorics.
[5] D. West. Induced Forest in Planar Graphs. Accessed 08/12/017.

Facebook Comments

Tags: , , , ,

Reply

Your email address will not be published. Required fields are marked *