Diễn Đàn MathScopeDiễn Đàn MathScope
  Diễn Đàn MathScope

  Diễn Đàn MathScope > Đại Học Và Sau Đại Học/College Playground > Logic, Tập Hợp, Toán Rời Rạc

News & Announcements

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é !

* Nội quy MathScope.Org

* Một số quy định chung !

* 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

* Những câu hỏi thường gặp

* Về việc viết bài trong Box Đại học và Sau đại học


 
21-07-2012, 02:17 PM   #1
Mít đặc
+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 đỡ
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
Đang học xác suất

 


« | »







- -

Inactive Reminders By mathscope.org
[page compression: 39.36 k/42.30 k (6.96%)]