graph - Каковы различия между Embedded и Topological в Graph?

В Руководстве по проектированию алгоритмов на странице 178 описаны некоторые свойства графа, и одно из них является встроенным и топологическим:

Встроенные и топологические

Граф является вложенным, если вершинам и ребрам присвоены геометрические позиции. Таким образом, любой рисунок графа представляет собой вложение, которое может иметь или не иметь алгоритмического значения.

Иногда структура графа полностью определяется геометрией его вложения. Например, если нам дан набор точек на плоскости и мы ищем тур с минимальной стоимостью, посетив их все (т. е. задача коммивояжера), основная топология — это полный граф, соединяющий каждую пару вершин. Веса обычно определяются евклидовым расстоянием между каждой парой точек.

Сетки точек - еще один пример топологии из геометрии. Многие задачи на сетке n × m включают обход между соседними точками, поэтому ребра неявно определяются геометрией.

Я совсем не понимаю:

  1. Прежде всего, что именно здесь означает embedded? Если вершины имеют свои собственные геометрические позиции, могу ли я назвать граф вложенным?
  2. Что означает any drawing of a graph is an embedding? Означает ли это то, что я сказал в пункте 1?
  3. Что означает Topological? Я не думаю, что это объяснено в этом описании.
  4. Примеры в этом описании меня действительно сильно смутили. Может ли кто-нибудь использовать самые простые слова, чтобы дать мне понять эти два термина для графика?
  5. Действительно ли важно понимать эти два термина?

Спасибо


graph algorithm topology data-structures
person Jackson Tale    schedule 04.04.2012    source источник

Ответы (3)


arrow_upward
5
arrow_downward

  1. Напоминаю, что граф — это просто набор вершин и набор ребер, определенных на них, поэтому вершины не имеют собственного геометрического положения. Рисунок графа называется встраиванием, нарисованный граф называется вложенным.
  2. Это означает, что любой способ рисования графа называется вложением этого графа.
  3. Топологический граф — это граф, вершины и ребра которого являются точками и дугами соответственно.
person msj    schedule 04.04.2012

arrow_upward
1
arrow_downward

Скиена использует географический граф дружбы в качестве примера встроенного графа, потому что каждая вершина связана с географической точкой в ​​этом мире, где живут друзья.

Отрывок из книги - Живут ли рядом со мной мои друзья? – Социальные сети не оторваны от географии. Многие из ваших друзей являются вашими друзьями только потому, что они живут рядом с вами (например, соседи) или раньше жили рядом с вами (например, соседи по комнате в колледже).

Таким образом, для полного понимания социальных сетей требуется встроенный граф, где каждая вершина связана с точкой в ​​этом мире, где они живут. Эта географическая информация может быть не закодирована явно, но тот факт, что график по своей сути встроен в плоскость, определяет нашу интерпретацию любого анализа.

person nick w.    schedule 25.09.2016

arrow_upward
1
arrow_downward

В дополнение к ответу msj.

Граф = G(V, E), где V — набор вершин, а E — набор пар вершин из V. Это определение графа согласно Скиене. Обратите внимание, что нет упоминания о том, как этот граф выглядит визуально (т.е. нет упоминания о его топологии).

Пример (обратите внимание, что он не определяет, где a, b расположены, скажем, в системе координат X, Y)

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

Чтобы «нарисовать» график, вы назначаете ему геометрические позиции, например. в системах координат X,Y.

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

Рис. 1 — это просто вложение, в котором мы рисуем пары вершин, указанные в E.

Разница между встроенным и топологическим графом заключается в том, как возникает «топология». При любом «встраивании» вы вручную назначаете геометрические местоположения, как описано выше, но в топологическом графе вы определяете «правило», основанное на том, какая топология графа определяет себя. например вы указываете G(V,E) и определяете правило, скажем, «посетить каждый узел ровно один раз» определяет топологию, которая называется «полный граф».

person PnotNP    schedule 07.10.2016