Tìm cây bao trùm

Nội dung chương này trình bày định nghĩa và các tính chất cơ bản của cây; tìm cây bao trùm theo phương pháp – DFS (Depth First Search); cây bao trùm nhỏ nhất và một số nội dung khác. Tham khảo nội dung bài giảng để nắm bắt nội dung chi tiết.

15p xaydungk23 19-04-2016 105 6   Download

Tìm cây bao trùm nhỏ nhất là bài tốn tối ưu có nhiều ứng dụng trong thực tế. Nó là bài tốn tìm hệ thống liên thông với chi phí nhỏ nhất. Hai thuật tốn tìm cây bao trùm nhỏ nhất thường được nhắc đến là thuật tốn Prim và thuật tốn Krusska. Nhằm giúp các bạn hiểu hơn về vấn đề này, mời các bạn cùng tham khảo đề tài "Tìm cây khung có trọng lượng nhỏ nhất bằng giải thuật Prim" dưới đây.

17p hploc9kd 10-12-2015 146 19   Download

Màn đêm yên ả bao trùm thành phố đang say giấc ngủ. Trời khuya tới nỗi đường phố vắng lặng không một tiếng người chỉ còn tiếng gió luồn qua những tán lá cây xào xạt. Từ đâu đó bỗng xuất hiện một đốm sáng màu xanh lam chập chờn, nó cứ bay lưỡng lờ hết nhà này đến nhà khác như muốn tìm một cái gì đó. Đốm sáng đó là gì nhỉ chẳng ai biết mà cũng chẳng ai thấy, nó cứ bay như thế kiên trì, lặng lẽ trong bóng đêm tĩnh mịt...

17p conmuachieunhoem15 31-05-2013 50 4   Download

Trong chương này ta xét một dạng đặc biệt nhưng có nhiều ứng dụng của đồ thị vô hướng. Đó là khái niệm cây. 11.1. Cây Khái niệm cây được Cayley đưa ra đầu tiên vào năm 1857. Định nghĩa 11.1: Giả sử T = (V, E) là đồ thị vô hướng. Ta nói rằng đồ thị T là một cây nếu nó liên thông và không có chu trình. Ví dụ 11.2: Đồ thị dưới đây là một cây. Kết quả dưới đây sẽ cho chúng ta một số tính chất lý thú và có thể dùng làm...

6p yeuthuong 01-12-2010 189 33   Download