wykres - Jakie są różnice między osadzonymi i topologicznymi na wykresie?

Question

W Algorithm Design Manual, strona 178 opisuje pewne właściwości wykres, a jeden z nich jest osadzony i topologiczne:

wbudowania w porównaniu topologiczne

wykres jest osadzony gdy wierzchołki i krawędzie są przyporządkowane pozycji geometrycznych . Zatem każdy rysunek wykresu jest osadzeniem, które może mieć znaczenie algorytmiczne lub nie.

Sporadycznie struktura wykresu jest całkowicie zdefiniowana przez geometrię jego osadzania w postaci . Na przykład, jeśli otrzymamy kolekcję punktów na płaszczyźnie, i wyszukujemy dla nich minimalną opłatę kosztową odwiedzającą wszystkie (tj. Problem komiwojażera), podstawową topologią jest kompletny wykres łączący każdą parę wierzchołków. Wagi są zwykle określane przez odległość euklidesową między każdą parą punktów .

Siatki punktów to kolejny przykład topologii z geometrii. Wiele problemów na siatce n × m obejmuje chodzenie między sąsiadującymi punktami , więc krawędzie są niejawnie zdefiniowane z geometrii.

I zupełnie nie rozumiem:

1. Przede wszystkim, co dokładnie ma embedded tu na myśli? Dopóki wierzchołki mają swoje własne pozycje geometryczne, to czy mogę wywołać wykres osadzony?
2. Co oznacza any drawing of a graph is an embedding? Czy to oznacza to, co powiedziałem w punkcie 1?
3. Co oznacza Topological? Nie sądzę, że jest to wyjaśnione w tym opisie.
4. Przykłady w tym opisie bardzo mnie bardzo zdezorientowały. Czy ktoś mógłby użyć najprostszych słów, aby pozwolić mi zrozumieć te dwa terminy na wykres?
5. Czy naprawdę ważne jest zrozumienie tych dwóch terminów?

Dzięki

Answer 1

1. Przypominam, że wykres jest tylko zbiór wierzchołków oraz zestaw krawędzi zdefiniowanych na nich, więc wierzchołki nie mają geometryczny pozycję własnych. Rysunek wykresu nazywany jest osadzaniem, a wykreślony wykres nazywany jest osadzonym.
2. Oznacza to, że każdy sposób narysowania wykresu nazywany jest osadzeniem tego wykresu.
3. Wykres topologiczny to wykres, którego wierzchołkami i krawędziami są odpowiednio punkty i łuki.

Answer 2

Skiena wykorzystuje geograficzną wykres przyjaźń jako przykład dla osadzonego wykresu, ponieważ każdy wierzchołek jest związany z geograficznego punktu w tym świecie, w którym żyją przyjaciele.

Fragment książki - Czy moi przyjaciele mieszkają blisko mnie? - Sieci społecznościowe nie są rozłączone z geografią. Wielu znajomych to Twoi przyjaciele tylko dlatego, że mieszkają w pobliżu Ciebie (np. Sąsiedzi) lub mieszkali w pobliżu (np. Współlokatorzy w college'ach).

W ten sposób pełne zrozumienie sieci społecznościowych wymaga osadzonego wykresu, w którym każdy wierzchołek jest powiązany z punktem w tym świecie, w którym mieszka. Ta informacja geograficzna może nie być jawnie zakodowana, ale fakt, że wykres jest z natury osadzony w płaszczyźnie, kształtuje naszą interpretację jakiejkolwiek analizy.

Answer 3

Oprócz odpowiedzi msj.

wykres = G(V, E) gdzie V jest wierzchołków ii E jest para wierzchołków z V. jest określenie wykresu według Skiena. Zwróć uwagę, że nie ma żadnej wzmianki o tym, jak ten graf wizualnie się pojawia (tj. Nie wspomina o swojej topologii).

Przykład (zauważyć, że nie określają, a, b znajdują powiedzmy X, Y układu współrzędnych)

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

do „zwrócić” wykres ją przypisać pozycji geometrycznych np w układach współrzędnych X, Y.

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

Rys 1 jest po prostu osadzanie gdzie jesteśmy rysunek pary wierzchołków określone w E

Różnica między osadzone i topologiczna wykres jest w jaki sposób „topologia” pochodzi być. W każdym "osadzaniu" ręczne przypisywanie lokalizacji geometrycznych jest opisane powyżej, ale w topologicznym wykresie definiuje się "regułę", na podstawie której definiuje się topologia wykresu. na przykład określasz G(V,E) i definiujesz regułę, powiedz "odwiedzaj każdy węzeł dokładnie jeden raz", definiując topologię, która nazywa się "pełnym wykresem".