Khái quát về đồ thị¶

Tóm lược nội dung

Bài này trình bày một vài khái niệm chung về đồ thị.

Khái niệm¶

Đồ thị là một cấu trúc bao gồm tập hợp các đỉnh và tập hợp các cạnh nối giữa các đỉnh.

Ký hiệu: G = (V, E)

Trong đó:
- G: đồ thị
- V: tập hợp các đỉnh
- E: tập hợp các cạnh
Đỉnh

Là điểm trong đồ thị, thường dùng để biểu diễn các thực thể như địa điểm, người hoặc đối tượng.
Cạnh

Là kết nối giữa hai đỉnh, biểu diễn mối quan hệ hoặc sự tương tác giữa hai thực thể.

Cạnh có thể có hướng hoặc không có hướng.
Hai đỉnh kề nhau là hai đỉnh được nối với nhau bằng một cạnh.
Hai cạnh kề nhau là hai cạnh có chung một đỉnh.
Cạnh song song là những cạnh khác nhau nhưng kết nối cùng một cặp đỉnh.
Khuyên là cạnh đặc biệt mà đỉnh đầu và đỉnh cuối là một.
Đường đi là dãy các đỉnh nối với nhau bởi các cạnh.
Chu trình là đường đi bắt đầu và kết thúc tại cùng một đỉnh.
Đồ thị liên thông là đồ thị có đường đi giữa mọi cặp đỉnh.
Cây là đồ thị liên thông không có chu trình.

Đơn đồ thị

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

Là đồ thị có khuyên hoặc cạnh song song.
Đồ thị có hướng

Mỗi cạnh có một hướng xác định, nghĩa là nếu có cạnh từ đỉnh u đến v thì chỉ có thể đi từ u đến v, mà không thể đi ngược từ v đến u.
Đồ thị vô hướng

Các cạnh không có hướng, nghĩa là nếu có cạnh nối hai đỉnh u và v thì có thể đi từ u đến v và ngược lại.
Đồ thị có trọng số

Mỗi cạnh được gán một giá trị, thường gọi là trọng số, dùng để biểu diễn độ dài, chi phí hoặc khối lượng của mối quan hệ.
Đồ thị không trọng số

Các cạnh không có trọng số, chỉ đơn thuần thể hiện mối quan hệ giữa các đỉnh.

Duyệt đồ thị

Có hai phương pháp chính:
- Duyệt theo chiều sâu
- Duyệt theo chiều rộng
Tìm đường ngắn nhất

Để tìm đường đi ngắn nhất giữa hai đỉnh, ta sử dụng một số thuật toán phổ biến như:
- Dijkstra
- Bellman-Ford
- Floyd-Warshall
Kiểm tra liên thông

Là xác định xem các đỉnh có thể kết nối với nhau hay không.

Đồ thị đóng một vai trò quan trọng trong khoa học máy tính, đặc biệt trong việc biểu diễn và xử lý các mối quan hệ giữa các đối tượng.

Đồ thị giúp mô hình hóa nhiều vấn đề thực tế, chẳng hạn như:

Mô phỏng mạng lưới giao thông, mạng xã hội.
Giải các bài toán về tối ưu hóa như tìm đường đi ngắn nhất, giải quyết luồng mạng.
Xác định chu trình trong các quy trình hoặc công việc (sơ đồ Gantt, sơ đồ mạng).