- Sự khác biệt giữa Embedded và Topology trong Graph là gì?

Question

Trong Algorithm Design Manual, trang 178 mô tả một số tính chất của đồ thị, và một trong số họ được nhúng và tôpô:

Embedded vs tôpô

Một biểu đồ được nhúng nếu các đỉnh và cạnh được giao vị trí hình học . Do đó, bất kỳ bản vẽ nào của biểu đồ là sự nhúng, có thể có hoặc không có ý nghĩa thuật toán.

Thỉnh thoảng, cấu trúc của biểu đồ được xác định hoàn toàn bằng cách nhúng hình học . Ví dụ: nếu chúng tôi được cung cấp một bộ sưu tập điểm trên mặt phẳng và tìm kiếm chuyến tham quan chi phí tối thiểu truy cập tất cả chúng (nghĩa là vấn đề người bán hàng), cấu trúc liên kết cơ bản là đồ thị hoàn chỉnh kết nối từng cặp đỉnh. Trọng số thường được xác định bởi khoảng cách Euclide giữa mỗi cặp điểm.

Lưới điểm là một ví dụ khác về cấu trúc liên kết từ hình học. Nhiều vấn đề trên lưới n × m liên quan đến việc đi bộ giữa các điểm lân cận, do đó các cạnh được xác định ngầm từ hình học.

tôi khá không hiểu nó:

1. Trước hết, những gì chính xác không embedded nghĩa đây? Miễn là các đỉnh có vị trí hình học riêng của chúng, thì tôi có thể gọi đồ thị được nhúng không?
2. any drawing of a graph is an embedding có nghĩa là gì? Nó có nghĩa là những gì tôi đã nói ở điểm 1?
3. Topological có nghĩa là gì? Tôi không nghĩ rằng nó được giải thích trong mô tả này.
4. Các ví dụ trong mô tả này thực sự làm tôi bối rối. Ai đó có thể vui lòng sử dụng các từ đơn giản nhất để tôi hiểu hai thuật ngữ này cho biểu đồ?
5. Có thực sự quan trọng để hiểu hai thuật ngữ này không?

Cảm ơn

Answer 1

1. tôi nhắc nhở bạn rằng một đồ thị chỉ là một tập hợp các đỉnh và một tập các cạnh được định nghĩa trên chúng, vì vậy các đỉnh không có một vị trí hình học của riêng mình. Bản vẽ biểu đồ được gọi là nhúng, biểu đồ được vẽ được gọi là nhúng.
2. Điều đó có nghĩa là bất kỳ cách nào để vẽ biểu đồ được gọi là nhúng biểu đồ đó.
3. Biểu đồ tôpô là biểu đồ có đỉnh và cạnh là điểm và cung, tương ứng.

Answer 2

Skiena sử dụng biểu đồ tình bạn địa lý làm ví dụ cho biểu đồ được nhúng bởi vì mỗi đỉnh được liên kết với một điểm địa lý trong thế giới này nơi bạn bè sinh sống.

Trích từ sách - Bạn bè của tôi có sống gần tôi không? - Mạng xã hội không bị ly dị khỏi địa lý. Nhiều bạn bè của bạn là bạn của bạn chỉ vì họ sống gần bạn (ví dụ: hàng xóm) hoặc sống gần bạn (ví dụ: bạn cùng phòng đại học).

Do đó, hiểu biết đầy đủ về mạng xã hội yêu cầu biểu đồ được nhúng, trong đó mỗi đỉnh được liên kết với điểm trong thế giới này nơi chúng sống. Thông tin địa lý này có thể không được mã hóa rõ ràng, nhưng thực tế là đồ thị vốn đã được nhúng vào trong mặt phẳng tạo nên sự giải thích của chúng ta về bất kỳ phân tích nào.

Answer 3

Ngoài câu trả lời của msj.

Đồ thị = G(V, E), trong đó V được đặt là đỉnh và và E được đặt cặp đỉnh V. Đây là định nghĩa biểu đồ theo Skiena. Lưu ý làm thế nào không có đề cập đến cách đồ thị này trực quan xuất hiện (tức là không đề cập đến cấu trúc liên kết của nó).

Ví dụ (lưu ý rằng nó không xác định nơi a, b được đặt tại nói X, Y hệ tọa độ)

V = { a, b, c, d, e, f } và E = { (a,b), (b,c), (a,e) }

Để 'vẽ' một đồ thị bạn gán nó vị trí hình học ví dụ trong các hệ tọa độ X, Y.

| 
|   b (2,3) 
| a(1,2) 
| 
| 
|____________________________ 
Fig 1 

Hình 1 chỉ đơn giản là một nhúng nơi chúng tôi đang vẽ cặp đỉnh quy định tại E

Sự khác nhau giữa nhúng và topo đồ thị là làm thế nào để "tô pô" đến được. Trong bất kỳ "nhúng" nào bạn gán các vị trí hình học theo cách thủ công như đã giải thích ở trên, nhưng trong biểu đồ tôpô, bạn xác định "quy tắc" dựa trên cấu trúc liên kết của biểu đồ. ví dụ. bạn chỉ định một số G(V,E) và xác định quy tắc, giả sử "truy cập từng nút một lần" xác định cấu trúc liên kết được gọi là "biểu đồ hoàn chỉnh".