Một bài toán về đỉnh tách của đồ thị phẳng liên thông. 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 đỡ :) |
Múi giờ GMT. Hiện tại là 01:32 AM. |
Powered by: vBulletin Copyright ©2000-2024, Jelsoft Enterprises Ltd.