Cây (lý thuyết đồ thị)

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm
Một cây có dán nhãn với 6 đỉnh và 5 cạnh

Cây là khái niệm quan trọng trong lý thuyết đồ thị, cấu trúc dữ liệugiải thuật. Cây là một đồ thị mà trong đó hai đỉnh bất kì đều được nối với nhau bằng đúng một đường đi. Nói cách khác, đồ thị liên thông bất kỳ không có chu trình là một cây. Rừnghợp (disjoint union) của các cây. Cây được sử dụng rộng rãi trong các cấu trúc dữ liệu của ngành khoa học máy tính như cây nhị phân, đống, trie, cây Huffman cho nén dữ liệu, v.v...

Cây tự do[sửa | sửa mã nguồn]

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[sửa | sửa mã nguồn]

Cho đồ thị G=(V,E) có n đỉnh. Sáu mệnh đề sau là tương đương:

  1. G là một cây;
  2. G không có chu trình và có n-1 cạnh;
  3. G liên thông và có n-1 cạnh;
  4. 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;
  5. 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;
  6. 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)[sửa | sửa mã nguồn]

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à anh em, đỉnh không có con được gọi là lá hay đỉnh ngoài, đỉnh không là lá được gọi là đỉnh trong.

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[sửa | sửa mã nguồn]

Cây có gốc mỗi đỉnh có không quá hai con được gọi là cây nhị phân (binary tree).

Cây nhị phân mà mỗi đỉnh trong có đúng hai con được gọi là cây nhị phân đầy đủ(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 chỉnh (perfect binary tree). Một số tài liệu gọi cây loại này là cây đầy đủ.

Cây nhị phân mà mỗi đỉnh của nó đã có con phải thì cũng có con trái được gọi là cây nhị phân gần hoàn chỉnh (almost complete binary tree).

Cây nhị phân có mức lá chênh nhau không quá 1 mức(độ cao cây)thì gọi là cây nhị phân cân bằng.

Ứng dụng cây trong khoa học máy tính[sửa | sửa mã nguồn]

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ấu trúc cây được ứng dụng trong các giải thuật tìm kiếm, giải thuật sắp xếp và nhiều bài toán khác

Cây dùng để biểu diễn bài toán quyết định (cây quyết định), biểu diễn quá trình tính toán các biểu thức đại số.

Các cây đặc biệt[sửa | sửa mã nguồn]

Biểu diễn cây[sửa | sửa mã nguồn]

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ó.

Các thuật toán duyệt cây[sửa | sửa mã nguồn]

Cây bao trùm[sửa | sửa mã nguồn]

Mọi đơn đồ thị lê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 bao trùm của G. Đồ thị G có thể có nhiều cây bao trùm. Nếu G có trọng số trên các cạnh thì cây bao trùm có tổng trọng số trên các cạnh của nó là nhỏ nhất (/lớn nhất) được gọi là cây bao trùm nhỏ nhất (/lớn nhất).

Định lý[sửa | sửa mã nguồn]

  • Mọi đồ thị liên thông đều cso chứa ít nhất một cây bao trùm.
  • Định lý Carley: Số cây khung của đồ thị Gn là n mũ n-2

Các thuật toán tìm cây bao trùm[sửa | sửa mã nguồn]

  • Thuật toán tìm cây bao trùm theo chiều rộng
  • Thuật toán tìm cây bao trùm theo chiều sâu
  • Thuật toán Prim
  • Thuật toán Kruskal

Các thuật toán khác[sửa | sửa mã nguồn]

Xem thêm[sửa | sửa mã nguồn]