Sự khác biệt giữa đồ thị Directed và Undirected

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

Biểu đồ là một cấu trúc toán học bao gồm các đỉnh và cạnh. Một biểu đồ đại diện cho một tập hợp các đối tượng (đại diện bởi các đỉnh) được kết nối thông qua một số liên kết (đại diện bởi các cạnh). Sử dụng các ký hiệu toán học, đồ thị có thể được biểu diễn bởi 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 kết nối các đỉnh. Trong một biểu đồ trực tiếp có một hướng kết hợp với các cạnh kết nối các đỉnh.

Biểu đồ không hướng dẫn

Biểu đồ không hướng dẫn

Như đã đề cập ở trên, một đồ thị không định hướng là một đồ thị không có hướng ở các cạnh liên kết các đỉnh trong đồ thị. Hình 1 miêu tả một đồ thị vô hướng với tập các đỉnh V = {V1, V2, V3}. Tập các cạnh của biểu đồ trên có thể được viết như 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 các 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. Vì vậy các cạnh trong một đồ thị không được định hướng không phải là các cặp được sắp xếp. Đây là đặc tính chính của một đồ thị vô hướng. Các đồ thị không chuyển 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 diễn bằng các đỉnh. Ví dụ: một 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 sử dụng đồ thị không hướng. Các thành phố có thể được đại diện bởi các đỉnh trong biểu đồ và các cạnh biểu diễn hai con đường kết nối các thành phố.

Đồ thị trực tiếp

Đồ thị trực tiếp là một đồ thị trong đó các cạnh của biểu đồ liên kết các đỉnh có một hướng. Hình 2 mô tả đồ thị trực tiếp với tập các đỉnh V = {V1, V2, V3}. Tập các cạnh của biểu đồ trên có thể được viết như V = {(V1, V2), (V2, V3), (V1, V3)}. Các cạnh trong một đồ thị vô hướng được đặt hàng. Về mặt chính thức, cạnh e trong một đồ thị có hướng có thể được biểu diễn bởi cặp trật tự e = (x, y) trong đó x là đỉnh mà được gọi là nguồn 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 đầu cuối. Ví dụ: một mạng lưới đường kết nối một tập hợp các thành phố sử dụng một con đường có thể được biểu diễn sử dụng đồ thị không được định hướng. Các thành phố có thể được đại diện bởi các đỉnh trong biểu đồ và các cạnh được chỉ dẫn đại diện cho các con đường kết nối các thành phố xem xét hướng lưu lượng giao thông trên đường.

Sự khác biệt giữa Đồ thị trực tiếp và Đồ thị Không được Định hướng là gì?

Trong một đồ thị trực tiếp, một cạnh là một cặp được sắp xếp, trong đó cặp thứ tự đại diện cho hướng cạnh mà 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 kết với một cạnh.Các đồ thị không hướng dẫn 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. Mức độ và mức độ out-of của mỗi nút trong một đồ thị không được định hướng bằng nhau nhưng điều này không đúng đối với đồ thị trực tiếp. Khi sử dụng một 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 cho một đồ thị trực tiếp. Một đồ thị vô hướng có thể được chuyển đổi sang đồ thị có hướng bằng cách thay thế mỗi cạnh bằng hai cạnh được định hướng theo chiều ngược lại. Tuy nhiên, không thể chuyển đổi đồ thị trực tiếp sang đồ thị không được định hướng.