Chủ đề này có 2 trả lời

[thangde.]

Cho đồ thị liên thông G có 1998 đỉnh và mỗi đỉnh đều có bậc 3.Chứng minh có thể xóa được ít nhất 200 đỉnh và các cạnh nối với nó sao cho đồ thị còn lại vẫn liên thông

[lehoan]

Bổ đề: Với đồ thì gồm http://dientuvietnam...n/mimetex.cgi?n đỉnh chứa ít nhất http://dientuvietnam.net/cgi-bin/mimetex.cgi?\dfrac{4n}{3} đỉnh thì tồn tại hai chu trình có đỉnh chung.

Chứng minh:
Giả sử ngược lại. Gọi T là cây cơ bản của G. Khi đó T có n-1 cạnh và không có chu trình. Và mỗi lần thêm một cạnh vào T ( sao cho không có hai chu trình nào cắt nhau ) thì số chu trình tăng thêm 1.
Mà mỗi chu trình thì chứa ít nhất là 3 đỉnh nên ta thu được không có http://dientuvietnam.net/cgi-bin/mimetex.cgi?\dfrac{n}{3} chu trình ( không giao nhau). Do đó số cạnh tối đa là http://dientuvietnam.net/cgi-bin/mimetex.cgi?n-1+\dfrac{n}{3}<\dfrac{4n}{3}. ( mâu thuẫn)

Trở lại bài toán:

Giả sử G chứa hai chu trình giao nhau tại O thì dĩ nhiên ta có bậc của O không nhỏ hơn 3. Nhưng mà đồ thị là đều bậc 3 nên ta có bậc của O là 3. Khi đó ta xóa O và các cạnh OA;OB;OC xuất phát từ O thì hiển nhiên là đồ thị còn lại vẫn liên thông.
Cứ tiếp tục làm như thế nếu như đồ thị vẫn có hai chu trình cắt nhau.

Cuối cùng giả sử m là số đỉnh đã được xóa ta có đồ thị ban đầu chứa http://dientuvietnam.net/cgi-bin/mimetex.cgi?\dfrac{3n}{2} cạnh và cứ mỗi lần thì ta xóa đi 3 cạnh đo đó ta có
http://dientuvietnam.net/cgi-bin/mimetex.cgi?n=1998 thì ta có thể xóa đi http://dientuvietnam.net/cgi-bin/mimetex.cgi?&#091;\dfrac{1998}{10}]+1 là http://dientuvietnam...mimetex.cgi?200 đỉnh

[FDF]

Hơ lời giải của lehoan hay thật đấy;lời giải trong quyển Around vừa dài vừa loằng ngoằng đọc chẳng hiểu gì cả