Chủ đề này có 3 trả lời

[supermember]

Bài Toán :

Trong $1$ graph đơn liên thông ( simple connected graph ) ; mỗi đỉnh có bậc ít nhất là $3$

Chứng minh rằng trong graph này tồn tại ít nhất $1$ chu trình ;

trong đó nếu ta xóa hết các cạnh ( giữ lại đỉnh) của chu trình này thì graph thu được vẫn liên thông .

Bài viết đã được chỉnh sửa nội dung bởi supermember: 12-08-2011 - 21:20

[Nguyễn Hoàng Lâm]

Bài Toán :

Trong $1$ graph đơn liên thông ( simple connected graph ) ; mỗi đỉnh có bậc ít nhất là $3$

Chứng minh rằng trong graph này tồn tại ít nhất $1$ chu trình ;

trong đó nếu ta xóa hết các cạnh ( giữ lại đỉnh) của chu trình này thì graph thu được vẫn liên thông .

Khái niệm này xuất hiện ở Đại học hay sao mà em chưa nghe nói. Anh cung cho em thông tin về cái này được không ?

[Peter Pan]

Khái niệm này xuất hiện ở Đại học hay sao mà em chưa nghe nói. Anh cung cho em thông tin về cái này được không ?

Khái niệm này với học sinh THPT bây h ko xa lạ nữa đâu anh, anh xem cuốn Graph của Vũ Đình Hòa có cả đấy

[linh2]

mình nghĩ có thể làm thế này
chú ý là đồ thị n đỉnh có ít nhất n-1 cạnh mà ko có đỉnh nào deg=0 thì sẽ liên thông,có thể chứng minh bằng quy nạp.Ngoài ra đồ thị n đỉnh n cạnh thì tồn tại ít nhất 1 chu trình. Đồ thị của ta có ít nhất n*3/2 cạnh vì bậc mỗi đỉnh nhỏ nhất là 3
Xét chu trình có độ dài nhỏ nhất của đồ thị ban đầu A_1...A_k neu k>n/2 thì trong n-k đỉnh còn lại mỗi đỉnh có nhiều nhất 1 cạnh nối với các cạnh trong A_1...A_k( nếu có 1 đỉnh X nối với A_i A_ j thì xét đồ thị tạo bởi X và phần đường đi nối A_i và A_ j ta có chu trình có độ dài nhỏ hơn , mâu thuẫn )
Vậy đồ thị con tạo bởi n-k đỉnh còn lại có bậc mỗi đỉnh ít nhất là 2 nên có ít nhất 2(n-k)/2=n-k cạnh,suy ra tồn tại 1 chu trình, mâu thuẫn vì n-k < k
Vậy k<=n/2. Xóa tất cả các cạnh của chu trình A_1..A_k. Số cạnh còn lại ít nhất là 3n/2-n/2=n và ko có đỉnh cô lập (vì bậc mỗi đỉnh ban đầu ít nhất là 3). vậy đồ thị còn lại vẫn liên thông

Bài viết đã được chỉnh sửa nội dung bởi linh2: 16-08-2011 - 08:19