Cây tự do là một đơn đồ thị, liên thông, không có chu trình.
Định lý sau cho biết các điều kiện tương đương với định nghĩa cây
Định lý - Các điều kiện cần và đủ để đồ thị là một cây
Cho đồ thị G=(V,E) có n đỉnh. Sáu mệnh đề sau là tương đương:
G là một cây;
G không có chu trình và có n-1 cạnh;
G liên thông và có n-1 cạnh;
G không có chu trình và nếu bổ sung vào một cạnh nối hai đỉnh không kề nhau thì xuất hiện một chu trình duy nhất;
G liên thông và nếu bỏ đi một cạnh bất kỳ thì G mất tính liên thông;
Mỗi cặp đỉnh trong G được nối với nhau bằng đường đi duy nhất.
Cây (có gốc)
Cây (có gốc) là cây trong đó có một đỉnh được chọn là gốc và mỗi cạnh được định hướng trùng với hướng đi của đường đi đơn duy nhất từ gốc tới mỗi đỉnh.
Trong một cây có gốc, nếu có một cạnh đi từ đỉnh x đến đỉnh y thì đỉnh x được gọi là cha của đỉnh y, y là con của x (xem đồ thị (toán học)).
Hai đỉnh cùng cha được gọi là đỉnh anh em, các đỉnh không có con tức nằm ngoài rìa cây được gọi là (đỉnh)lá hay đỉnh ngoài, các đỉnh còn lại gọi là đỉnh trong (kể cả đỉnh gốc).
Số cạnh trên đường đi từ gốc tới mỗi đỉnh được gọi là mức của đỉnh ấy.
Cây nhị phân và các biến thể của nó
Định nghĩa:
Cây mà mỗi đỉnh có không quá hai con được gọi là cây nhị phân (binary tree).
Biến thể: có 4 loại cơ bản
Về tên gọi tiếng Việt cho chúng: thực tế, các tài liệu Việt Nam không thống nhất cách gọi tên các cây, mỗi kiểu tài liệu lại ghi khác nhau, cách diễn giải định nghĩa cũng khác nhau,... nên chúng tôi khuyên bạn nên sử dụng tiếng Anh để gọi tên cây, trong bài này, tên của các cây được dịch theo giáo trình Toán học tổ hợp của Trường Đại học Khoa học Tự Nhiên - ĐHQG TP.HCM và định nghĩa cũng sẽ được ghi đơn giản nhất có thể
Cây nhị phân mà mỗi đỉnh chỉ có 0hoặc2 con được gọi là cây nhị phân đủ (full binary tree)
Cây nhị phân đầy đủ mà tất cả các lá có cùng một mức được gọi là cây nhị phân hoàn hảo (perfect binary tree).
Cây nhị phân mà từ mức 0 xuống mức h - 1 là cây nhị phân hoàn hảo, ở mức h thì các đỉnh được sắp từ trái sang phải được gọi là cây nhị phânhoàn thành (complete binary tree) (h là độ cao cây)
Cây nhị phân có mức lá là hhoặch - 1 (h là độ cao cây) thì gọi là cây nhị phân cân bằng (hoặc cân đối).
Ứng dụng cây trong khoa học máy tính
Trong khoa học máy tính cây là một cấu trúc dữ liệu không tuyến tính.
Có thể biểu diễn cây bằng mảng hoặc bằng danh sách kề. Khi biểu diễn bằng danh sách kề, mọi cây có thể chuyển sang một cây nhị phân tương đương với nó.
Mọi đơn đồ thị liên thông G có ít nhất một đồ thị con là cây và chứa tất cả các đỉnh của G. Đồ thị con này được gọi là cây khung (hoặc cây bao trùm) của G (thuật ngữ cây khung được sử dụng phổ biến hơn). Đồ thị G có thể có nhiều cây khung. Nếu G có trọng số trên các cạnh thì cây khung có tổng trọng số trên các cạnh của nó là nhỏ nhất (hoặc lớn nhất) được gọi là cây khung nhỏ nhất (hoặc lớn nhất).
Định lý
Mọi đồ thị liên thông đều có chứa ít nhất một cây bao trùm.