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

[NDTPX]

*Mình được bạn cho biết 1 bài toán (bài toán 2) ..trong quá trình giải thấy nảy sinh 2 bài toán cùng loại cũng hay và gợi mở cách nghĩ cho truờng hợp tổng quát ; nhưng mình cũng chưa nghĩ cho trường hợp tổng quát nên đưa ra để mọi người cùng thảo luận xem sao.
BT1:Cho một đồ thị đủ n đỉnh .Mỗi lần lấy ra 1 chu trình tam giác rồi xóa đi 1 cạnh của chu trình đó.Tính số cạnh tối đa có thể còn lại sau khi ko thể tiếp tục lấy ra chu trình tam giác nữa.

BT2: cũng giống bài toán trên chỉ khác là thay chu trình tam giác thành chu trình tứ giác.

BT3: tiếp tục như 2 bài toán trên chỉ thay chu trình 3.4 bằng chu trình ngũ giác.

[lovePearl_maytrang]

Chà cuối cùng thì cũng có người có cùng ý tưởng với mình
Cách đây khoảng 1 tháng tớ có đọc bài toán 2 (bài dự tuyển) và thấy cách giải cực hay. Tớ cũng đã suy nghĩ đến bài toán thứ nhất (bài này có chung ý tưởng với bài 2, nhưng dễ hơn một chút). Tớ nghĩ rằng tác giả bài toán 2 đã nghĩ ra nó sau khi giải xong bài 1. Về trường hợp tổng quát LPm chưa thể nói gì nhiều nhưng tính chẵn lẻ cạnh của đa giác xóa đi có 1 vai trò quan trọng.
Để suy nghĩ típ

[NDTPX]

Hura,cuối cùng thì tôi cũng chinh phục được bài toán này nên lập tức lên mạng công bố kết quả cho bà con xem ngay(còn lời giải chi tiết thì đợi tui soạn thảo ở nhà cái đã).
Gọi số cạnh của chu trình lấy ra là n.Kí hiệu S(t,n) là số cạnh nhỏ nhất còn lại với đồ thị đủ t đỉnh.
Trong trường hợp :
*n chia hết cho 2 thì S(t,n)=t(t>=n)
*n lẻ : S(n,n)=n.
S(t,n)=n-1(mọi t >n)
*(Một gợi ý cho bài toán tổng quát là phải quan sát kĩ trường hợp 3,4 và 5).
*Hướng giải thì hoàn toàn cuất phát từ các trường hợp nhỏ mà đi lên thôi.
*(Tôi ko biết lời giải của tôi trường hợp nhỏ n=4 có giống đáp án ko ,nhưng lại rất có lợi trong việc giait quyết bài toán tổng quát )

[lovePearl_maytrang]

          S(t,n)=n-1(mọi t >n)

S(t,n)= t-1 chứ nhỉ????

[NDTPX]

Yes sir,thế you đã kiểm tra kết quả của tôi chưa,đúng hoàn toàn đó.

[lovePearl_maytrang]

Cho đồ thị đầy đủ n đỉnh. Mỗi lần chọn một chu trình 3 cạnh và xóa đi một cạnh bất kì cho đến khi không còn thể típ tục được nữa. Tìm số cạnh lớn nhất của đồ thị còn lại khi đó.

[NDTPX]

Vấn đề này thì không khó : Kết quả là phần nguyên của n^2/4.
Tuy nhiên bài toán thay 3 bởi k thì tôi chưa có ý kiến gì.

[gadget]

Bởi việc xóa chu trình không làm thay đổi tính liên thông của đồ thị nên đồ thị cuối liên thông nên S(t;n)>=t-1
Nếu n chẵn thì việc xóa chu trình từ đồ thị ko lưỡng phân sẽ cho 1 đồ thị ko lưỡng phân vậy đồ thị cuối ko lưỡng phân và liên thông,nói riêng nó ko phải là 1 cây vì thế S(t;n)>=t với n chẵn
chỉ ra thuật toán theo quy nạp
khi t>n ta chọn ra 1 đỉnh A và xét các cạnh AA_1...AA_{t-1}
xét các đồ thị đầy đủ AA_1;AA_i(i=2->t-i) và n-2 đỉnh trong các đỉnh còn lại->ta xóa được các cạnh AA_i
Lặp lại thuật toán trên ta thấy chỉ cần chỉ ra thuật toán cho đồ thị n đỉnh là đủ
Để về nhà nghĩ thêm đã

Bài viết đã được chỉnh sửa nội dung bởi gadget: 11-07-2006 - 20:46

[tanlsth]

Theo mình bài giải quyết dựa trên khái niệm về cây
một đồ thị khi không còn chu trình thì sẽ là một cây mà một cây n đỉnh thì có n-1 cạnh
Mặt khác một cây khi thêm một cạnh bất kì thì sẽ có chu trình