Rate this post

Đồ thị không có chu trình được gọi là đồ thị mạch hở. Tree là một đồ thị xoay chiều hoặc đồ thị không có chu trình.

Các bài viết liên quan:

Tree hay các General Tree được định nghĩa là một tập hợp hữu hạn không rỗng của các phần tử được gọi là đỉnh hoặc nút có đặc tính là mỗi nút có thể có bậc nhỏ nhất là bậc 1 và bậc lớn nhất là n. Nó có thể được phân chia thành n + 1 tập con rời rạc sao cho tập con đầu tiên chứa gốc của Tree và n tập con còn lại bao gồm các phần tử của n Tree con.

Directed Trees – Cây có hướng 

Tree có hướng là một đồ thị có hướng xoay chiều. Nó có một nút với Tree thời hạn 1, trong khi tất cả các nút khác có Tree số không xác định 1 như được hiển thị trong hình:

Nút có độ lớn hơn 0 được gọi là nút bên ngoài hoặc nút đầu cuối hoặc lá. Các nút có độ lớn hơn hoặc bằng một được gọi là nút bên trong.

Ordered Trees – cây có thứ tự

Nếu trong một Tree ở mỗi cấp, một thứ tự được xác định, thì một Tree như vậy được gọi là Tree có thứ tự.

Ví dụ: Các Tree trong hình vẽ là cùng một Tree nhưng có thứ tự khác nhau.

Thuộc tính của Tree

  • Chỉ có một đường đi giữa mỗi cặp đỉnh của Tree.
  • Nếu một đồ thị G thì có một và chỉ một đường đi giữa mỗi cặp đỉnh G là một Tree.
  • Một Tree T với n đỉnh có n-1 cạnh.
  • Biểu đồ là một Tree nếu và chỉ khi nó là một Tree tối thiểu được kết nối.

Rooted Trees

Nếu một Tree có hướng có chính xác một nút hoặc đỉnh được gọi là gốc có độ tới là 0 và tất cả các đỉnh khác có bậc tới là một, thì Tree được gọi là Tree có gốc.

Lưu ý:

  • Tree không có nút là Tree có gốc (Tree rỗng)
  • Một nút đơn không có nút con là Tree có gốc.

Độ dài cạnh của một Đỉnh

Độ dài đường đi của một đỉnh trong Tree gốc được định nghĩa là số cạnh trong đường đi từ gốc đến đỉnh.

Ví dụ: Tìm độ dài đường đi của các nút b, f, l, q như trong hình:

Giải:

  • Độ dài đường đi của nút b là một.
  • Độ dài đường đi của nút f là hai.
  • Chiều dài đường đi của nút l là ba
  • Chiều dài đường đi của nút q là bốn.

Leave a Reply

Call now
%d bloggers like this: