Đồ thị có hướng so với Đồ thị vô hướng
Đồ thị là một cấu trúc toán học được tạo thành từ tập hợp các đỉnh và các cạnh. Đồ thị biểu diễn một tập hợp các đối tượng (biểu diễn bằng các đỉnh) được kết nối với nhau thông qua một số liên kết (biểu diễn bằng các cạnh). Sử dụng các ký hiệu toán học, một đồ thị có thể được biểu diễn bằng G, trong đó G=(V, E) và V là tập các đỉnh và E là tập các cạnh. Trong một đồ thị vô hướng không có hướng liên kết với các cạnh nối các đỉnh. Trong một đồ thị có hướng, có một hướng liên kết với các cạnh nối các đỉnh.
Đồ thị vô hướng
Như đã đề cập trước đó, đồ thị vô hướng là đồ thị không có hướng trong các cạnh liên kết các đỉnh trong đồ thị. Hình 1 mô tả một đồ thị vô hướng với tập các đỉnh V={V1, V2, V3}. Tập hợp các cạnh trong đồ thị trên có thể được viết là V={(V1, V2), (V2, V3), (V1, V3)}. Cũng có thể lưu ý rằng không có gì ngăn cản việc viết tập các cạnh là V={(V2, V1), (V3, V2), (V3, V1)} vì các cạnh không có hướng. Do đó các cạnh trong một đồ thị vô hướng không phải là các cặp có thứ tự. Đây là đặc điểm chính của đồ thị vô hướng. Đồ thị vô hướng có thể được sử dụng để biểu diễn mối quan hệ đối xứng giữa các đối tượng được biểu diễn bằng các đỉnh. Ví dụ: mạng lưới đường hai chiều kết nối một tập hợp các thành phố có thể được biểu diễn bằng biểu đồ vô hướng. Các thành phố có thể được biểu thị bằng các đỉnh trong biểu đồ và các cạnh thể hiện hai con đường nối các thành phố.
Đồ thị được hướng dẫn
Đồ thị có hướng là đồ thị trong đó các cạnh trong đồ thị liên kết các đỉnh có hướng. Hình 2 mô tả một đồ thị có hướng với tập các đỉnh V={V1, V2, V3}. Tập hợp các cạnh trong đồ thị trên có thể được viết là V={(V1, V2), (V2, V3), (V1, V3)}. Các cạnh trong một biểu đồ vô hướng là các cặp có thứ tự. Về mặt hình thức, cạnh e trong đồ thị có hướng có thể được biểu diễn bằng cặp thứ tự e=(x, y) trong đó x là đỉnh được gọi là điểm gốc, điểm gốc hoặc điểm ban đầu của cạnh e và đỉnh y được gọi là điểm cuối., đỉnh kết thúc hoặc điểm đầu cuối. Ví dụ: mạng lưới đường kết nối một tập hợp các thành phố sử dụng đường một chiều có thể được biểu diễn bằng biểu đồ vô hướng. Các thành phố có thể được biểu thị bằng các đỉnh trong biểu đồ và các cạnh có hướng đại diện cho các con đường nối các thành phố xem xét hướng lưu thông trên đường.
Sự khác biệt giữa Đồ thị có hướng và Đồ thị không có hướng là gì?
Trong đồ thị có hướng, một cạnh là một cặp có thứ tự, trong đó cặp có thứ tự biểu thị hướng của cạnh liên kết hai đỉnh. Mặt khác, trong một đồ thị vô hướng, một cạnh là một cặp không có thứ tự, vì không có hướng nào được liên kết với một cạnh. Đồ thị vô hướng có thể được sử dụng để biểu diễn mối quan hệ đối xứng giữa các đối tượng. Độ trong và độ ngoài của mỗi nút trong đồ thị vô hướng là bằng nhau nhưng điều này không đúng với đồ thị có hướng. Khi sử dụng ma trận để biểu diễn đồ thị vô hướng, ma trận luôn trở thành đồ thị đối xứng, nhưng điều này không đúng với đồ thị có hướng. Đồ thị vô hướng có thể được chuyển đổi thành đồ thị có hướng bằng cách thay thế mỗi cạnh bằng hai cạnh có hướng đi ngược hướng. Tuy nhiên, không thể chuyển đổi đồ thị có hướng thành đồ thị vô hướng.
