Cây và Cấu trúc Bao trùm

Cây là một đồ thị liên thông không chu trình, và các cấu trúc bao trùm trích xuất các bộ khung liên thông tối thiểu như vậy từ các đồ thị lớn hơn.

Definition

Cây là một đồ thị liên thông không có chu trình; cây bao trùm của một đồ thị liên thông là một đồ thị con là một cây và bao gồm mọi đỉnh của đồ thị.

Scope

Chủ đề này bao gồm các đặc trưng tương đương của cây, cây có gốc và cây được gán nhãn, cây bao trùm và rừng bao trùm, cũng như cách đếm chúng thông qua công thức Cayley và định lý Ma trận-Cây. Nó cũng giới thiệu cây bao trùm tối thiểu như một bài toán tối ưu hóa, kết nối lý thuyết đồ thị với thiết kế thuật toán và đếm tổ hợp.

Core questions

• Những điều kiện tương đương nào đặc trưng cho một đồ thị là một cây?
• Có bao nhiêu cây được gán nhãn trên một số đỉnh nhất định?
• Một đồ thị cho trước chứa bao nhiêu cây bao trùm?
• Làm thế nào để tìm một cây bao trùm có tổng trọng số tối thiểu một cách hiệu quả?

Key concepts

• Đồ thị liên thông không chu trình
• Cây có gốc và cây được gán nhãn
• Cây bao trùm và rừng bao trùm
• Dãy Prufer
• Công thức Cayley
• Cây bao trùm tối thiểu

Key theories

Công thức Cayley

Có chính xác n^(n-2) cây được gán nhãn khác nhau trên n đỉnh, một kết quả liệt kê cổ điển có thể chứng minh bằng dãy Prufer, định lý Ma trận-Cây, hoặc một số phép song ánh thanh lịch.

Định lý Ma trận-Cây

Số lượng cây bao trùm của một đồ thị bằng bất kỳ phần bù đại số nào của ma trận Laplace của nó, liên kết việc đếm tổ hợp các cây bao trùm với đại số tuyến tính và định thức.

Clinical relevance

Cây bao trùm là nền tảng cho thiết kế mạng và định tuyến quảng bá, cây bao trùm tối thiểu giải quyết các bài toán kết nối chi phí thấp nhất, và cấu trúc cây tổ chức dữ liệu và hệ thống phân cấp trong toàn bộ khoa học máy tính.

History

Nghiên cứu mạng điện của Kirchhoff vào thế kỷ 19 đã tạo ra định lý Ma trận-Cây, trong khi công trình đếm cây được gán nhãn của Cayley năm 1889 đã trở thành một trong những công thức nổi tiếng nhất trong lý thuyết đồ thị liệt kê.

Key figures

• Arthur Cayley
• Gustav Kirchhoff
• Heinz Prufer

Seminal works

• diestel2017
• stanley2011

Frequently asked questions

Tại sao một cây trên n đỉnh lại có chính xác n-1 cạnh?

Một cây là liên thông, điều này đòi hỏi ít nhất n-1 cạnh, và không chu trình, điều này cấm nhiều hơn; hai điều kiện này cùng nhau xác định số cạnh chính xác là n-1.

Cây bao trùm được dùng để làm gì?

Cây bao trùm cung cấp một tập hợp tối thiểu các kết nối giữ cho mạng liên thông, đây là cơ sở cho việc quảng bá hiệu quả và thiết kế mạng với chi phí thấp nhất.