Định nghĩa: Cây là một đồ thị vô hướng liên thông, không chứa chu trình và có ít nhất hai đỉnh. Một đồ thị vô hướng không chứa chu trình và có ít nhất hai đỉnh gọi là một rừng. Trong một rừng, mỗi thành phần liên thông là một cây. | CÂY Một đồ thị liên thông và không có chu trình được gọi là cây. Dùng cây để xây dựng các thuật toán rất có hiệu quả để định vị các phần tử trong một danh sách Cây cũng dùng để xây dựng các mạng máy tính với chi phí rẻ nhất cho các đường điện thoại nối các máy phân tán Cây cũng được dùng để tạo ra các mã có hiệu quả để lưu trữ và truyền dữ liệu Dùng cây có thể mô hình các thủ tục mà để thi hành nó cần dùng một dãy các quyết định Định nghĩa: Cây là một đồ thị vô hướng liên thông, không chứa chu trình và có ít nhất hai đỉnh. Một đồ thị vô hướng không chứa chu trình và có ít nhất hai đỉnh gọi là một rừng. Trong một rừng, mỗi thành phần liên thông là một cây. Rừng sau có 3 cây Mệnh đề: Nếu T là một cây có n đỉnh thì T có ít nhất hai đỉnh treo. Định lý: Cho T là một đồ thị có n ≥ 2 đỉnh. Các điều sau là tương đương: T là một cây. T liên thông và có n−1 cạnh. T không chứa chu trình và có n−1 cạnh. T liên thông và mỗi cạnh là cầu. Giữa hai đỉnh phân biệt bất kỳ của T luôn có duy nhất một . | CÂY Một đồ thị liên thông và không có chu trình được gọi là cây. Dùng cây để xây dựng các thuật toán rất có hiệu quả để định vị các phần tử trong một danh sách Cây cũng dùng để xây dựng các mạng máy tính với chi phí rẻ nhất cho các đường điện thoại nối các máy phân tán Cây cũng được dùng để tạo ra các mã có hiệu quả để lưu trữ và truyền dữ liệu Dùng cây có thể mô hình các thủ tục mà để thi hành nó cần dùng một dãy các quyết định Định nghĩa: Cây là một đồ thị vô hướng liên thông, không chứa chu trình và có ít nhất hai đỉnh. Một đồ thị vô hướng không chứa chu trình và có ít nhất hai đỉnh gọi là một rừng. Trong một rừng, mỗi thành phần liên thông là một cây. Rừng sau có 3 cây Mệnh đề: Nếu T là một cây có n đỉnh thì T có ít nhất hai đỉnh treo. Định lý: Cho T là một đồ thị có n ≥ 2 đỉnh. Các điều sau là tương đương: T là một cây. T liên thông và có n−1 cạnh. T không chứa chu trình và có n−1 cạnh. T liên thông và mỗi cạnh là cầu. Giữa hai đỉnh phân biệt bất kỳ của T luôn có duy nhất một đường đi sơ cấp. T không chứa chu trình nhưng khi thêm một cạnh mới thì có được một chu trình duy nhất. Định nghĩa: Cây có hướng là đồ thị có hướng mà đồ thị vô hướng nền của nó là một cây. Cây có gốc là một cây có hướng, trong đó có một đỉnh đặc biệt, gọi là gốc, từ gốc có đường đi đến mọi đỉnh khác của cây. Cây sau có nút gốc là r Trong cây có gốc thì gốc r có bậc vào bằng 0, còn tất cả các đỉnh khác đều có bậc vào bằng 1. Một cây có gốc thường được vẽ với gốc r ở trên cùng và cây phát triển từ trên xuống, gốc r gọi là đỉnh mức 0. Các đỉnh kề với r được xếp ở phía dưới và gọi là đỉnh mức 1. Đỉnh ngay dưới đỉnh mức 1 là đỉnh mức 2, . Tổng quát, trong một cây có gốc thì v là đỉnh mức k khi và chỉ khi đường đi từ r đến v có độ dài bằng k. Mức lớn nhất của một đỉnh bất kỳ trong cây gọi là chiều cao của cây. Cho cây T có gốc r=v0. Giả sử v0, v1, ., vn-1, vn là một đường đi trong T. Ta gọi: − vi+1 là con của vi và vi là cha của vi+1. − v0, v1, ., vn-1 là các tổ tiên của vn và vn là dòng
