Các Khái Niệm Cơ Bản và Tính Liên Thông của Đồ Thị

Các khái niệm cơ bản của lý thuyết đồ thị giới thiệu về đồ thị, các tham số cơ bản của chúng, và các khái niệm về tính liên thông và duyệt đồ thị mô tả cách một đồ thị được kết nối với nhau.

Definition

Một đồ thị bao gồm một tập hợp các đỉnh và một tập hợp các cạnh nối các cặp đỉnh; tính liên thông đo lường mức độ mà đồ thị vẫn còn nguyên vẹn khi các đỉnh hoặc cạnh bị loại bỏ.

Scope

Chủ đề này bao gồm các định nghĩa về đồ thị và đồ thị có hướng, bậc và bổ đề bắt tay, đồ thị con và đẳng cấu, đường đi, chu trình và chu trình, tính liên thông và các thành phần liên thông, và các đặc trưng cổ điển của đồ thị Euler và Hamilton. Nó thiết lập vốn từ vựng và các kết quả cấu trúc cốt lõi được sử dụng trong suốt lý thuyết đồ thị.

Core questions

• Các tham số cơ bản - bậc, kích thước và độ - của một đồ thị là gì?
• Khi nào một đồ thị được liên thông, và tính liên thông của nó bền vững đến mức nào khi bị xóa?
• Khi nào một đồ thị cho phép một đường đi đóng sử dụng mọi cạnh đúng một lần?
• Các đường đi và chu trình mã hóa khả năng tiếp cận và cấu trúc như thế nào?

Key concepts

• Đỉnh, cạnh và bậc
• Đường đi, chu trình và chu trình
• Các thành phần liên thông
• Tính liên thông đỉnh và cạnh
• Chu trình Euler
• Chu trình Hamilton

Key theories

Bổ đề bắt tay

Trong bất kỳ đồ thị nào, tổng tất cả các bậc đỉnh bằng hai lần số cạnh, điều này ngay lập tức ngụ ý rằng số đỉnh có bậc lẻ là chẵn.

Định lý Euler về chu trình Euler

Một đồ thị liên thông có một đường đi đóng đi qua mọi cạnh đúng một lần nếu và chỉ nếu mọi đỉnh có bậc chẵn, kết quả làm nền tảng cho lời giải của Euler về cầu Konigsberg.

Clinical relevance

Phân tích tính liên thông là trọng tâm của độ tin cậy mạng, định tuyến và thiết kế các hệ thống truyền thông và vận tải chịu lỗi, trong khi các cấu trúc Euler và Hamilton xuất hiện trong các vấn đề định tuyến và sắp xếp trình tự.

History

Bài báo Konigsberg năm 1736 của Euler đã giới thiệu việc duyệt đồ thị; định lý năm 1927 của Menger đã đưa ra tính đối ngẫu cơ bản giữa tính liên thông và các đường đi rời rạc, làm nền tảng cho lý thuyết hiện đại.

Key figures

• Leonhard Euler
• Karl Menger

Seminal works

• diestel2017

Frequently asked questions

Sự khác biệt giữa chu trình Euler và chu trình Hamilton là gì?

Một chu trình Euler sử dụng mọi cạnh đúng một lần, trong khi một chu trình Hamilton đi qua mọi đỉnh đúng một lần; chu trình trước có một đặc trưng bậc đơn giản, nhưng việc quyết định chu trình sau rất khó về mặt tính toán.

Một đồ thị k-liên thông có nghĩa là gì?

Một đồ thị là k-liên thông nếu nó vẫn liên thông bất cứ khi nào ít hơn k đỉnh bị loại bỏ, định lượng khả năng phục hồi của nó đối với các lỗi đỉnh.