Thuật toán mô hình cây

ứng dụng mô hình cây

Ngô Quốc Hoàn

Cây là đồ thị vô hướng liên thông và không có chu trình. Khái niệm cây lần đầu tiên được

Cayley đưa ra vào năm 1857, khi ông sử dụng chúng để thể hiện một số dạng cấu trúc

phân tử của các hợp chất hoá học hữu cơ. Cây còn có nhiều các ứng dụng rộng rãi trong

rất nhiều các lĩnh vực khác nhau. Đặc biệt trong tin học, cây được dùng để xây dựng các

thuật toán tổ chức thư mục, các thuật toán mã hoá, nén và giải nén dữ liệu, các thuật toán

tìm kiếm.. Trong bài viết này tôi xin trình bày với các bạn ứng dụng mô hình cây vào việc

giải một số bài toán tin học cụ thể.

Bài toán 1. Song liên thông

Cho một đồ thị vô hướng liên thông có N đỉnh và M cạnh, ta tạm định nghĩa nút cầu trong

một đồ thị liên thông là một nút mà nếu xoá nó khỏi đồ thị thì đồ thị sẽ bị tách thành các

thành phần liên thông khác nhau, đồ thị không có nút cầu được gọi là đồ thị song liên

thông. Hãy tìm đồ thị song liên thông với số đỉnh nhiều nhất và là con của đồ thị đã cho.

Dữ liệu vào file: slt.inp

- Dòng đầu tiên ghi hai số N, M (N<=100)

- M dòng tiếp theo mỗi dòng chứa 2 số (x,y) thể hiện một cạnh của đồ thị.

Dữ liệu ra file: slt.out

- Dòng đầu tiên ghi K (số đỉnh của đồ thị con).

- Dòng thứ 2 chứa K số thể hiện các đỉnh của đồ thị con.

Ví dụ:

Trong đồ thị trên thì các nút cầu là 1, 7, 8. Đồ thị trên có thành phần song liên thông với số

đỉnh nhiều nhất là 1 3 7 5 4 6

Tư tưởng thuật toán: