Sự khác biệt giữa đồ thị có hướng và không có hướng

Đồ thị trực tiếp và vô hướng

Biểu đồ 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ạnh. Biểu đồ biểu thị một tập hợp các đối tượng (được biểu thị bằng các đỉnh) được kết nối thông qua một số liên kết (được biểu thị bằng các cạnh). Sử dụng các ký hiệu toán học, một biểu đồ có thể được biểu diễn bằng G, trong đó G = (V, E) và V là tập hợp các đỉnh và E là tập hợp các cạnh. Trong một đồ thị vô hướng không có hướng liên quan đến các cạnh kết nối các đỉnh. Trong đồ thị có hướng có một hướng liên kết với các cạnh kết nối các đỉnh.

Đồ thị vô hướng

Như đã đề cập trước đó, một đồ thị vô hướng là một đồ thị trong đó 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 hợp các đỉnh V = V1, V2, V3. Tập hợp các cạnh trong biểu đồ 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 hợp các cạnh như 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 được đặt theo cặp. Đâ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 các mối quan hệ đối xứng giữa các đối tượng được biểu thị 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 đồ không bị chặn. Các thành phố có thể được biểu thị bằng các đỉnh trong biểu đồ và các cạnh đại diện cho các đường hai chiều kết nối các thành phố.

Đồ thị có hướng

Biểu đồ có hướng là một biểu đồ trong đó các cạnh trong biểu đồ 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 hợp các đỉnh V = V1, V2, V3. Tập hợp các cạnh trong biểu đồ trên có thể được viết là V = (V1, V2), (V2, V3), (V1, V3). Các cạnh trong một đồ thị vô hướng là các cặp theo thứ tự. Chính thức, cạnh e trong đồ thị có hướng có thể được biểu diễn bằng cặp có thứ tự e = (x, y) trong đó x là đỉnh được gọi là gốc, nguồn hoặc điểm ban đầu của cạnh e và đỉnh y được gọi là đầu cuối , chấm dứt đỉnh hoặc điểm 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 đồ không bị chặn. 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 định hướng đại diện cho các đường kết nối các thành phố đang xem xét hướng mà giao thông lưu thông trên đường.

Sự khác biệt giữa đồ thị có hướng và đồ thị vô hướng?

Trong đồ thị có hướng, một cạnh là một cặp có thứ tự, trong đó cặp được sắp xếp 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 liên quan đến một cạnh. Đồ thị vô hướng có thể được sử dụng để thể hiện mối quan hệ đối xứng giữa các đối tượng. Mức độ và mức độ của mỗi nút trong một đồ 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 một đồ thị vô hướng, ma trận luôn trở thành một đồ thị đối xứng, nhưng điều này không đúng với đồ thị có hướng. Một đồ 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 định hướng ngược nhau. Tuy nhiên, không thể chuyển đổi một biểu đồ có hướng sang một biểu đồ vô hướng.