Bạn muốn xem những bài viết hay và ngắn, đừng quên checkout và like facebook page: https://www.facebook.com/thietkegiaithuat/
Bài viết mới: phép chèn trong cây cây AVL.

Bài viết mới: Giới thiệu về cây nhị phân cân bằng.

Bài viết mới: Quy hoạch động trên cây.

Bài viết mới: Mảng mở rộng và ứng dung trong thực thi ngăn xếp/hàng đợi.

Bài viết mới: Danh sách liên kết đơn và các biến thể.

Bài viết mới: Một số bài toán NP-complete khi đầu vào là các số nguyên lớn.

Bài viết mới: Một số bài toán NP-complete trên đồ thị.

Bài viết mới: NP-complete. Bài viết bao gồm lời giải cho bài toán domino-tiling dựa trên bài toán cặp ghép hoàn hảo.

Bài viết mới: P vs NP, bài toán triệu đô của viện Clay.

Bài viết mới: Thuật toán Kosaraju tìm thành phần liên thông mạnh trong đồ thị có hướng.

Bài viết mới: Thuật toán Stoer-Wagner tìm lát cắt cực tiểu trong đồ thị.

Bài viết mới: Một số ứng dụng của bài toán luồng cực đại: cặp ghép cực đại, làm tròn ma trận và phân vùng ảnh.

Bài viết mới: Một số biến thể của bài toán luồng cực đại: luồng với nhiều đỉnh phát-thu, luồng với định mức cạnh và luồng cực đại có chi phí nhỏ nhất.

Bài viết mới: Thuật toán Edmonds-Karp.
Bài viết mới: Thuật toán FordFulkerson. Đây là bài viết đầu tiên trong chuỗi bài về luồng trong mạng.

Bài viết mới: Lý thuyết phổ đồ thị IV Phổ của ma trận kề và bài toán tô màu. Bài thứ 4 trong loạt bài về lý thuyết phổ.
Bài viết mới: Lý thuyết phổ đồ thị III. Bài thứ 3 trong loạt bài về lý thuyết phổ.

Bài viết mới: Lý thuyết phổ đồ thị II. Bài thứ 2 trong loạt bài về lý thuyết phổ.

Bài viết mới: Lý thuyết phổ đồ thị I. Bài đầu tiên trong loạt bài về lý thuyết phổ.

Bài viết mới: Thuật toán KKT, thuật toán cuối cùng trong loạt bài cây khung nhỏ nhất

Bài viết mới trên facebook: Phát triển giải thuật cho hệ thống gợi ý cho dữ liệu lớn. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: Bài toán User Hashing và cách chọn Collision Resistant Hash Functions. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: Tìm một phần tử trong ma trận và lời giải. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: Puzzle màu mắt dân trên đảo và lời giải. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới: thuật toán Boruvka tìm cây khung nhỏ nhất. Xem tại đây.

Bài viết mới trên facebook: xóa các dòng giống nhau trong file và lời giải. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: tìm phần tử trội. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: lời giải bài toán tìm một số nguyên không xuất hiện trong file. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới: Thuật toán Prim tìm cây khung nhỏ nhất: Xem tại đây.

Mình sẽ start một series các posts nhỏ về giải thuật cho Big-Data trên facebook. Mình có lẽ sẽ repost lại một số bài viết trên facebook tại đây nhưng facebook vẫn là kênh chính để chúng ta thảo luận các topics kiểu này. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: tìm 3 điểm nằm trên cùng một đường thẳng. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: hiểu đúng về độ phức tạp. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới Thuật toán Kruskal cho bài toán cây khung nhỏ nhất.

Bài viết mới trên facebook: bình chọn thuật toán tìm cây khung nhỏ nhất mà bạn yêu thích. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới: lời giải bài bug bug bug Xem tại đây.

Bài viết mới: Cơ sở toán học của băm địa chỉ mở và băm hoàn hảo: Xem tại đây.

Bài viết mới trên facebook: tìm bugs. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: bài toán mở cửa và lời giải: Check out at: https://www.facebook.com/thietkegiaithuat/.

Bài viết mới: Cơ sở toán học của xích ngăn cách trong phép băm: Xem tại đây.

Bài viết mới trên facebook: lời giải bài toán chọn quân bài: Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: Bài toán chọn quân bài: Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: Bài toán thả trứng và lời giải: Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: Một chút về dynamic memory allocation: Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: ArrayList trong Java. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: Nghịch lí ngày sinh và ứng dụng trong bài toán phân tích thành
nhân tử.

Bài toán mới: Balls into Bins đã được upload lên facebook page. Check out!!!

Mình vừa up một bài toán khá hay về ứng dụng của Heap nhị phân lên trang facebook. Check it out!!!!

Mình vừa tạo một facebook page: https://www.facebook.com/thietkegiaithuat/. Mình sẽ dùng page này để cập nhật những bài viết mới nhất. Ngoài ra, mình cũng sẽ cập nhật những nghiên cứu mới nhất về giải thuật và cấu trúc dữ liệu thông qua page này. Những bài viết trong blog sẽ chỉ là những bài viết về kiến thức cơ bản. Like ngay nếu bạn quan tâm.

tsp

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.

Tags: , , , ,

« Older entries