Đồ thị

1.1 Định nghĩa đồ thị và các thành phần của nó

Đồ thị — là một cấu trúc dữ liệu bao gồm nhiều đỉnh (hay còn gọi là node) và nhiều cạnh, kết nối các đỉnh. Đồ thị được sử dụng rộng rãi để mô hình hóa và trình bày các đối tượng khác nhau và các mối quan hệ giữa chúng.

Các thành phần chính của đồ thị:

Đỉnh (Vertex):

• Là những phần tử của đồ thị, đại diện cho các đối tượng.
• Được ký hiệu là V (tập hợp các đỉnh).
• Ví dụ, V = {A, B, C, D}.

Cạnh (Edge):

• Kết nối giữa các đỉnh, đại diện cho quan hệ hay kết nối.
• Được kí hiệu là E (tập hợp các cạnh).
• Ví dụ, E = {(A, B), (B, C), (C, D), (A, D)}.

Các đặc điểm chính của đồ thị:

Bậc của đỉnh:

• Số lượng cạnh liên quan đến một đỉnh nhất định.
• Trong đồ thị vô hướng, bậc của đỉnh là số cạnh nối đỉnh đó với các đỉnh khác.
• Trong đồ thị có hướng, phân biệt giữa bậc vào và bậc ra của đỉnh.

Đường đi trong đồ thị:

• Một dãy các cạnh kết nối một dãy các đỉnh lại với nhau.
• Ví dụ, đường đi từ A đến D: A → B → C → D.

Chu trình trong đồ thị:

• Một đường đi bắt đầu và kết thúc tại cùng một đỉnh.
• Ví dụ, chu trình: A → B → C → A.

1.2 Các loại đồ thị

Đồ thị có rất nhiều loại khác nhau, nhưng có vài loại đặc biệt như sau:

1. Đồ thị vô hướng:

Cạnh của đồ thị này không có hướng, tức là kết nối giữa hai đỉnh có thể đi qua lại hai phía.

Ví dụ:

Mạng xã hội, nơi mà các node đại diện cho con người, và cạnh là mối quan hệ bạn bè.

2. Đồ thị có hướng:

Cạnh của đồ thị có hướng (thường được đánh dấu bằng mũi tên), nghĩa là kết nối giữa các đỉnh chỉ có thể đi theo một hướng nhất định.

Ví dụ:

Đồ thị liên kết các trang web, node là các trang, cạnh là các liên kết giữa chúng.

3. Đồ thị có trọng số:

Cạnh có trọng số (số), có thể biểu thị khoảng cách, chi phí hoặc các thước đo khác.

Ví dụ:

Đồ thị về các con đường, node là các thành phố, cạnh là các con đường với độ dài hoặc chi phí.

4. Đồ thị hỗn hợp:

Có cả cạnh có hướng và cạnh vô hướng.

Ví dụ:

Hệ thống vận chuyển, một số đường có thể đi hai chiều, một số chỉ có một chiều.

5. Đồ thị phẳng:

Đồ thị có thể vẽ trên mặt phẳng sao cho các cạnh không giao nhau.

Ví dụ:

Đồ thị về các con đường trong thành phố (không có hầm).

6. Đồ thị liên thông:

Đồ thị có đường đi giữa bất kì cặp đỉnh nào.

Ví dụ:

Đồ thị đại diện cho mạng lưới các thành phố, trong đó mỗi cặp thành phố đều được kết nối qua đường đi.

7. Đồ thị không chu trình:

Đồ thị không có chu trình.

Ví dụ:

Cây đại diện cho cấu trúc hệ thống tập tin.

1.3 Ví dụ về ứng dụng của đồ thị

1. Mạng xã hội:

• Các node đại diện cho con người, và cạnh là mối quan hệ bạn bè.
• Được sử dụng để phân tích kết nối, tìm cộng đồng, ảnh hưởng của người dùng, v.v.

2. Internet và định tuyến:

• Các node đại diện cho bộ định tuyến hoặc máy tính, còn cạnh là kết nối giữa chúng.
• Được dùng để tìm đường đi tối ưu cho việc truyền dữ liệu.

3. Genomics:

• Các node đại diện cho gene hoặc protein, còn cạnh là những tương tác giữa chúng.
• Được dùng để phân tích dữ liệu gene, tìm kiếm mô hình, v.v.

4. Logistics và vận chuyển:

• Các node đại diện cho các thành phố hoặc điểm vận chuyển, còn cạnh là đường hoặc tuyến đường.
• Được sử dụng để tối ưu hóa tuyến đường giao hàng, giảm thiểu chi phí, v.v.

5. Mạng máy tính:

• Các node đại diện cho thiết bị hoặc máy chủ, còn cạnh là kết nối giữa chúng.
• Được sử dụng để thiết kế và quản lý mạng.

6. Phân tích dữ liệu và học máy:

Đồ thị được sử dụng để đại diện và phân tích dữ liệu, tìm kiếm các cụm, tạo hệ thống gợi ý, và nhiều hơn nữa.