![]() | ![]() | | ![]() |
|
|
![]() |
Ngoài một số quy định đã được nêu trong phần Quy định của Ghi Danh , mọi người tranh thủ bỏ ra 5 phút để đọc thêm một số Quy định sau để khỏi bị treo nick ở MathScope nhé ! * Quy định về việc viết bài trong diễn đàn MathScope * Nếu bạn muốn gia nhập đội ngũ BQT thì vui lòng tham gia tại đây |
![]() ![]() |
|
![]() | #1 |
+Thà nh Viên+ ![]() : Aug 2010 : 96 : 10 | 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 đỡ ![]() __________________ Äang há»c xác suất ![]() |
![]() | ![]() |