|
|
|
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 |
| Ðiều Chỉnh | Xếp Bài |
21-07-2012, 02:17 PM | #1 |
+Thành Viên+ Tham gia ngày: Aug 2010 Bài gởi: 96 Thanks: 10 Thanked 37 Times in 22 Posts | 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 thay đổi nội dung bởi: Mít đặc, 22-07-2012 lúc 10:30 AM |
Bookmarks |
Ðiều Chỉnh | |
Xếp Bài | |
|
|