ứ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:
Bài toán có thể được giải theo mô hình cây như sau:
- Mỗi đỉnh của cây là một tập đỉnh thể hiện cho một đồ thị con. Gốc là tập đỉnh thể hiện đồ
thị ban đầu.
- Giả sử có một đỉnh x={x1...xK}. Ta cần tìm một nút cầu xi trong đồ thị có tập đỉnh
{x1. ..xK} và bỏ nút cầu xưi đi thì đồ thị có tập đỉnh {x1...xK} sẽ bị phân thành những
thành phần liên thông có các tập đỉnh là y1</SUB>={Y1.1...y1.L} ..
yP</SUB>={YP.1..yP.M}, với k, L, M ≥ 1, L + M = k - 1, p >1. Lúc đó ta xây dựng p nút:

diễn đa giác p1, X2 biểu diễn đa giác p2.
- Nếu không có đoạn thẳng nào chia đa giác thành 2 phần thì nút X là nút lá và đa giác p là
một mắt lưới.
- Lúc này bài toán trở thành tìm một nút lá biểu diễn đa giác có dịên tích lớn nhất.
Hình vẽ cây nhị phân mô tả ví dụ trên:
Dựa trên tư tưởng trên ta có thể xây dựng một chương trình con đệ quy để giải bài toán
trên như sau:
Procedure chiăp:poligon; i:integer);
{ thủ tục chia đa giác P bởi đoạn thẳng có số hiệu từ i trở đi}
var j:integer;
p1,p2:poligon;
begin
for j:=i to n do
if chiaduoc(p,j,p1,p2) then
{thủ tục chiaduoc có nhiệm vụ: kiểm tra xem đoạn thẳng j có chia đựơc đa giác p thành hai
đa giac con p1 và p2 không }
begin
chiăp1,j+1);
chiăp2,j+1);
exit;
end;
s:=dientich(p); {hàm dientich để tính diện tích đa giác P}
if s>smax then smax:=s; {cập nhật kỉ lục }
end;