Đồ thị (Graph) Phần 1: Các khái niệm cơ bản

Trong toán học và tin học, đồ thị (graph) là đối tượng nghiên cứu cơ bản của lý thuyết đồ thị. Một cách không chính thức, đồ thị là một tập các đối tượng gọi là đỉnh nối với nhau bởi các cạnh. Thông thường, đồ thị được vẽ dưới dạng một tập các điểm (đỉnh, nút) nối với nhau bởi các đoạn thẳng (cạnh). Tùy theo ứng dụng mà một số cạnh có thể có hướng.

Lưu ý: Bài đầu tiên giới thiệu tất cả các khái niệm nên sẽ gây khó hiểu nhưng đừng nản nhé, cứ đọc cho biết đã. Phần nào không hiểu có thể bỏ qua và đọc tiếp bài sau. Khi đọc kiến thức bài sau có khái niệm gì mà chưa biết thì có thể quay lại đọc nhé.

Mục lục

1. Định nghĩa đồ thị

Một cách không chính thức, đồ thị là một tập các đối tượng được gọi là các đỉnh nối với nhau bởi các cạnh.
Kí hiệu: G=(V,E)
Trong đó:
\(V\) là tập các đỉnh của đồ thị. Đặt \(|V| = n\) (số đỉnh).
\(E\) là tập các cạnh của đồ thị. Đặt \(|E| = m\) (số cạnh).

Hình 1: Đồ thị vô hướng

Hình 2: Đồ thị có hướng

2. Đỉnh

Đỉnh biểu diễn các đối tượng trong đồ thị, thường được đánh dấu bằng các số hoặc kí hiệu bằng các chữ cái in thường \(u,v,…\)
Ví dụ:

Trong hình 1 gồm các đỉnh: \(1, 2, 3, 4, 5, 6, 7 \)
Trong hình 2 gồm các đỉnh: \(v1, v2, v3, v4, v5, v6, v7\)

3. Cạnh

Cạnh nối đỉnh \(x\) với đỉnh \(y\) là một tập gồm hai phần tử \(x,y\), thường được vẽ dưới dạng một đoạn thẳng nối hai đỉnh.
Cạnh vô hướng: Không quan tâm đến hướng và coi hai đỉnh như nhau.
Ví dụ: Xét trong đồ thị vô hướng (hình 1) ta có cạnh \((1, 2), (2, 3)\)

Cạnh có hướng (cung): Là một cặp đỉnh có thứ tự. Trong mỗi cặp có thứ tự đó, đỉnh thứ nhất được gọi là đỉnh đầu, đỉnh thứ hai là đỉnh cuối.
Ví dụ: Xét trong đồ thị có hướng (hình 2) ta có cạnh \((v1, v6)\), cạnh \((v2, v1)\)

Khuyên: Là một cạnh nối một đỉnh với chính nó.
Ví dụ: Trong hình 2, ta có khuyên tại đỉnh \(v5, v7\)

Hai cạnh song song: Là hai cạnh cùng nối hai đỉnh \(u, v\).
Ví dụ: trong hình 1, ta có 2 cạnh nối hai đỉnh \(6\) và \(7\)

Cạnh không trọng số: Là các cạnh như trên hình 1 và 2, các cạnh đều có vai trò như nhau.

Cạnh có trọng số: Là cạnh được gán một giá trị thể hiện trọng số của cạnh
Ví dụ: Trong thực tế, đường đi từ địa điểm \(A\) đến \(B\) là \(5 \text{ km}\) thì ta có thể biểu diễn đường đi này là một cạnh \((A,B)\) với trọng số là \(5\).

4. Phân loại đồ thị

Đồ thị vô hướng: Là đồ thị mà tất cả các cạnh trong đồ thị đều vô hướng. (hình 1)

Đồ thị có hướng: Là đồ thị mà tất cả các cạnh trong đồ thị đều có hướng. (hình 2)

Đồ thị không trọng số: Là đồ thị mà tất cả các cạnh trong đồ thị đều không có trọng số.

Đồ thị có trọng số: Là đồ thị mà tất cả các cạnh trong đồ thị đều có trọng số.

Đơn đồ thị: Là đồ thị không có khuyên và không có cạnh song song.

Đa đồ thị: Là đồ thị không phải là đơn đồ thị.

5. Bậc

Trong đồ thị vô hướng, bậc của đỉnh \(v\) trong đồ thị \(G\), ký hiệu \(d_G (u)\), là số cạnh liên thuộc với \(v\), trong đó, khuyên được tính hai lần.

Ví dụ: Ở đồ thị 1:
Bậc của đỉnh \(1\) là \(3\) vì có \(3\) cạnh xuất phát từ \(1\) là \((1,2), (1,7), (1,3)\)
Bậc của đỉnh \(6\) là \(5\) vì có \(5\) cạnh xuất phát từ \(6\) là \((6,7), (6,7), (6,3), (6,5), (6,4)\)

Ta có định lí:
Giả sử \(G=(V,E)\) là đồ thị vô hướng, khi đó tổng các bậc đỉnh trong \(V\) sẽ bằng \(2\) lần số cạnh.
Hệ quả: Trong đồ thị vô hướng, số đỉnh bậc lẻ là chẵn.

Trong đồ thị có hướng, ta định nghĩa bán bậc ra của \(u\) là số cung đi ra khỏi nó, kí hiệu \(d^{+}_G (u)\), bán bậc vào của \(u\) là số cung đi ra khỏi nó, kí hiệu \(d^{–}_G (u)\).

Ví dụ: ở đồ thị 2:
\(d^{+}_G (v1) = 1\) vì chỉ có duy nhất \(1\) cạnh \((v1, v6)\) \(d^{–}_G (v6) = 2\) vì có \(2\) cạnh \((v5, v6), (v2, v6)\)

Giả sử \(G=(V,E)\) là đồ thị có hướng, khi đó tổng các bán bậc vào bằng tổng các bán bậc ra và bằng số cung của đồ thị

6. Đường đi và chu trình

Một dãy các đỉnh \(P = (p_0, p_1, …, p_k)\) sao cho \((P_{i-1}, P_i) ∊ E, ∀i: 1 \le i \le k\) được gọi là một đường đi.
Một đường đi là chu trình khi \(p_0 = p_k\).

Ví dụ: Xét đồ thị 1:
Ta có đường đi từ \(1\) tới \(7\) là \((7, 6, 4)\) hoặc \((7, 1, 3, 4)\) hoặc \((7, 2, 3, 5, 4)…\)
Chu trình: \((7, 2, 3, 6, 7)\) hoặc \((1, 2, 3, 1)…\)

7. Liên thông

Một đồ thị vô hướng là liên thông nếu tồn tại đường đi giữa hai cặp đỉnh bất kì thuộc đồ thị.
Một đồ thị có hướng là liên thông nếu phiên bản vô hướng của đồ thị đó là liên thông.
Ví dụ:

Đồ thị ở hình 1 là đồ thị liên thông
Đồ thị ở hình 2 là không liên thông vì đỉnh \(v4\) không có cạnh nối với các đỉnh còn lại khi đó, đồ thị chia thành 2 thành phần liên thông:Thành phần liên thông 1 gồm: \(v1, v2, v3, v5, v6, v7\). Thành phần liên thông 2 gồm: \(v4\)

8. Đồ thị phẳng

Đồ thị phẳng là đồ thị có thể được vẽ trên mặt phẳng sao cho không có hai đỉnh nào trùng nhau và các cạnh nào trùng nhau hoặc cắt nhau.

9. Công thức Euler

Giả sử đồ thị vô hướng liên thông \(G=(V,E)\) là đồ thị phẳng, với \(n\) đỉnh và \(m\) cạnh chia mặt phẳng thành \(e\) phần thì \(n – m + e = 2\)

Bài viết sau: Đồ thị (Graph) Phần 2: Tổ chức dữ liệu chúng ta hãy cùng nhau tìm hiểu về các cách để tổ chức, lưu trữ dữ liệu đồ thị trong lập trình nhé!

Xem thêm các kiến thức thú vị tại: https://www.facebook.com/codedreamedu