Lý thuyết đồ thị — Đỉnh, cạnh và các khái niệm cơ bản

Lý thuyết đồ thị là ngành nghiên cứu đồ thị, tức các cấu trúc được tạo bởi đỉnh và cạnh. Một đỉnh là một đối tượng, còn một cạnh biểu diễn mối quan hệ giữa hai đối tượng.

Nếu bạn đang tìm kiến thức cơ bản về lý thuyết đồ thị, hãy bắt đầu từ ý tưởng này: đồ thị là một cách gọn gàng để mô hình hóa các kết nối. Người trong mạng xã hội, các thành phố nối với nhau bằng đường đi, và các trang web liên kết với nhau đều có thể được biểu diễn bằng đồ thị.

Đồ thị có ý nghĩa gì trong toán học

Trong đồ thị vô hướng, một cạnh cho biết hai đỉnh được nối với nhau, và mối nối đó không có hướng. Nếu $A$ nối với $B$ thì $B$ cũng nối với $A$.

Trong đồ thị có hướng, các cạnh có hướng, nên $A \to B$ và $B \to A$ là hai phát biểu khác nhau. Nhiều ví dụ nhập môn dùng đồ thị vô hướng đơn, nghĩa là không có khuyên và không có cạnh lặp giữa cùng một cặp đỉnh.

Điều kiện đó quan trọng vì các định nghĩa thường được giới thiệu trước trong bối cảnh đồ thị vô hướng đơn. Nếu loại đồ thị thay đổi, ý nghĩa của các thuật ngữ cũng có thể thay đổi theo.

Những thuật ngữ lý thuyết đồ thị cơ bản cần biết trước

Đỉnh và cạnh

Đỉnh là đối tượng bạn muốn theo dõi. Cạnh là kết nối bạn muốn theo dõi.

Nếu một đồ thị mô hình hóa các thành phố và đường đi, thì các thành phố là đỉnh và các con đường là cạnh.

Bậc

Trong đồ thị vô hướng, bậc của một đỉnh là số cạnh kề với nó.

Nếu một thành phố có đường nối tới ba thành phố khác thì bậc của nó là $3$.

Đường đi

Đường đi là một dãy đỉnh mà mỗi cặp đỉnh liên tiếp được nối với nhau bằng một cạnh.

Nếu tồn tại một đường đi từ đỉnh này đến đỉnh kia, bạn có thể đi từ đỉnh này sang đỉnh kia bằng cách lần theo các cạnh.

Chu trình

Chu trình là một đường đi bắt đầu và kết thúc tại cùng một đỉnh. Theo định nghĩa cơ bản thường dùng, không có đỉnh nào khác bị lặp lại.

Chu trình cho thấy trong đồ thị có một vòng khép kín.

Đồ thị liên thông và các thành phần liên thông

Một đồ thị vô hướng là liên thông nếu từ mọi đỉnh đều có thể đi đến mọi đỉnh khác bằng một đường đi nào đó.

Nếu điều này không đúng, đồ thị sẽ tách thành các thành phần liên thông. Mỗi thành phần là một phần liên thông của đồ thị.

Ví dụ có lời giải: Một đồ thị nhỏ

Giả sử một đồ thị có các đỉnh $A$, $B$, $C$, $D$ và $E$, với các cạnh

$$AB,\ AC,\ BC,\ CD$$

Điều này tạo thành một tam giác trên $A$, $B$ và $C$, thêm một cạnh từ $C$ đến $D$, và một đỉnh cô lập $E$.

Bây giờ các ý chính sẽ rất dễ thấy.

Các bậc là

$$\deg(A)=2,\ \deg(B)=2,\ \deg(C)=3,\ \deg(D)=1,\ \deg(E)=0$$

Có một đường đi từ $A$ đến $D$:

$$A-C-D$$

Có một chu trình:

$$A-B-C-A$$

Đồ thị không liên thông vì không thể đi từ các đỉnh khác đến $E$. Vậy đồ thị có hai thành phần liên thông: một thành phần chứa $A,B,C,D$ và một thành phần chỉ chứa $E$.

Ví dụ duy nhất này cho thấy bậc, đường đi, chu trình, đỉnh cô lập và thành phần liên thông gắn với nhau như thế nào.

Kiểm tra nhanh: Tổng các bậc

Với mọi đồ thị vô hướng hữu hạn,

$$\sum \deg(v) = 2|E|$$

Điều này đúng vì mỗi cạnh kề với đúng hai đầu mút, nên mỗi cạnh cộng thêm $1$ vào hai số đếm bậc.

Trong ví dụ trên, tổng các bậc là

$$2+2+3+1+0=8$$

và số cạnh là $4$, nên

$$2|E| = 2 \cdot 4 = 8$$

Đây là một cách kiểm tra hữu ích khi bạn tự đếm bậc bằng tay. Nếu các con số không khớp, chắc chắn có gì đó sai.

Những lỗi thường gặp trong lý thuyết đồ thị

Nhầm lẫn giữa đỉnh và cạnh

Đỉnh là các đối tượng. Cạnh là các mối quan hệ giữa chúng.

Quên mất bạn đang xét loại đồ thị nào

Một mệnh đề đúng với đồ thị vô hướng đơn có thể cần thay đổi khi áp dụng cho đồ thị có hướng hoặc đồ thị cho phép khuyên.

Xem đường đi như chu trình

Đường đi không nhất thiết phải quay lại điểm xuất phát. Chu trình thì phải.

Bỏ qua các đỉnh cô lập

Một đỉnh có bậc $0$ vẫn là một phần của đồ thị. Nó có thể làm thay đổi việc đồ thị có liên thông hay không.

Kiến thức cơ bản về lý thuyết đồ thị được dùng ở đâu

Những ý tưởng này xuất hiện trong mạng máy tính, lập kế hoạch lộ trình, lập lịch, hệ gợi ý và mạng xã hội. Bối cảnh có thể thay đổi, nhưng các câu hỏi vẫn lặp lại: cái gì được nối với nhau, cái gì có thể đi tới được, và các vòng lặp nằm ở đâu?

Đó là lý do lý thuyết đồ thị xuất hiện sớm trong cả toán rời rạc lẫn khoa học máy tính.

Hãy thử một đồ thị tương tự

Vẽ bốn đỉnh $P$, $Q$, $R$ và $S$. Thêm các cạnh $PQ$, $QR$, $RS$ và $SP$.

Sau đó trả lời ba câu hỏi: bậc của mỗi đỉnh là bao nhiêu, đồ thị có liên thông không, và đồ thị có chứa một chu trình không?