Mít đặc
21-07-2012, 02:17 PM
Ta nhắc lại đn đỉnh tách: một đỉnh v của đồ thị phẳng liên thông G gọi là đỉnh tách nếu (G-v) không liên thông (ta đồng nhất G với thể hiện hình học của nó, tức là xem nó như một tập hợp trong mp).
Bài toán: Cho G là đồ thị phẳng liên thông không có đỉnh tách thỏa mãn hai điều kiên:
1) Mỗi đỉnh của nó là đầu mút của bốn cung
2) Tồn tại một cung nối hai đỉnh,gọi là v_1,\ v_2, mà nếu ta xóa phần trong cung đó (tức là ko xóa v_1,\ v_2) thì nhận được đồ thị mới có đỉnh tách.
Chứng minh khi đó nếu với G ta không xóa gì cả mà chỉ đồng nhất v_1,\ v_2 thì đồ thị mới nhận được sẽ không có đỉnh tách.
PS: Việc đồng nhất hai đỉnh v_1,\ v_2 sẽ thu đc đồ thị mới như sau: Bỏ đi một trong hai đỉnh, chẳng hạn là v_1. Xóa cung nối v_1,\ v_2 và dựng thêm một cung từ v_2 vào chính nó. Các cung nối các đỉnh khác v_1,\ v_2 giữ nguyên. Các cung nối một đỉnh khác với v_2 cũng giữ nguyên. Các cung nối một đỉnh khác với
v_1 bị xóa, thay vào đó dựng 1 cung nối đỉnh đó với
v_2.
Mình đang rất cần lời giải, mong ai đó trên 4rum giúp đỡ :)
Bài toán: Cho G là đồ thị phẳng liên thông không có đỉnh tách thỏa mãn hai điều kiên:
1) Mỗi đỉnh của nó là đầu mút của bốn cung
2) Tồn tại một cung nối hai đỉnh,gọi là v_1,\ v_2, mà nếu ta xóa phần trong cung đó (tức là ko xóa v_1,\ v_2) thì nhận được đồ thị mới có đỉnh tách.
Chứng minh khi đó nếu với G ta không xóa gì cả mà chỉ đồng nhất v_1,\ v_2 thì đồ thị mới nhận được sẽ không có đỉnh tách.
PS: Việc đồng nhất hai đỉnh v_1,\ v_2 sẽ thu đc đồ thị mới như sau: Bỏ đi một trong hai đỉnh, chẳng hạn là v_1. Xóa cung nối v_1,\ v_2 và dựng thêm một cung từ v_2 vào chính nó. Các cung nối các đỉnh khác v_1,\ v_2 giữ nguyên. Các cung nối một đỉnh khác với v_2 cũng giữ nguyên. Các cung nối một đỉnh khác với
v_1 bị xóa, thay vào đó dựng 1 cung nối đỉnh đó với
v_2.
Mình đang rất cần lời giải, mong ai đó trên 4rum giúp đỡ :)