Khác biệt giữa bản sửa đổi của “Cây (lý thuyết đồ thị)”
Nội dung được xóa Nội dung được thêm vào
n Robot: Sửa đổi hướng |
|||
Dòng 1:
[[Tập tin:Tree_graph.svg|phải|khung|Một cây có dán nhãn với 6 đỉnh và 5 cạnh]]
{{otheruses|Cây (định hướng)}}
'''Cây''' là khái niệm quan trọng trong [[lý thuyết đồ thị]], [[cấu trúc dữ liệu]] và [[thuật toán|giả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 (lý thuyết đồ thị)|đường đi]]. Nói cách khác, đồ thị [[tập hợp liên thông|liên thông]] bất kỳ không có [[chu trình (lý thuyết đồ thị)|chu trình]] là một cây. '''Rừng''' là [[phép hợp|hợ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 (lý thuyết đồ thị)|cây nhị phân]], [[đống (cấu trúc dữ liệu)|đống]], [[trie]], [[mã hóa Huffman|cây Huffman]] cho [[nén dữ liệu]], v.v...
==Cây tự do==
'''Cây tự do''' là một [[đồ thị (lý thuyết đồ thị)|đơ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
Dòng 21:
'''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ị (lý thuyết đồ thị)|đồ 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.
Dòng 56:
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ó.
==[[Duyệt cây|Các thuật toán duyệt cây]]==
*[[Duyệt cây|Duyệt tiền thứ tự]]
*[[Duyệt cây|Duyệt trung thứ tự]]
*[[Duyệt cây|Duyệt hậu thứ tự]]
==Cây bao trùm==
Dòng 68:
==Các thuật toán khác==
*Thuật toán [[sắp xếp vun đống|vun đống]]
*Thuật toán xây dựng cây [[mã hóa Huffman|mã Huffman]]
==Xem thêm==
| |||