Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[44.192.95.161] |
|
Сообщ.
#1
,
|
|
|
Всем хай! Сходу к делу!
хочется понять основательно представление графа в виде списка смежности. ЛЮБОГО графа... в целом, как устроен список смежности - понятно, в инете полно инфы по этому поводу, но все примеры какие-то тривиальные вот пример для неориентированного помеченного невзвешенного графа, состоящего из 4-рех вершин: Прикреплённая картинка
а теперь рассмотрим, наверное, самый тяжелый случай ( ну, сложнее не смог придумать)): граф смешанный помеченный с петлями ( обоих типов: петля-ребро и петля-дуга ) + есть кратные ребра ( мультиграфность ) и непонятно стало, как петли обозначать + кратные ребра( дуги ) в списке смежности. в матрице смежности еще с горем пополам можно как-то вести учет петель и кратных ребер, считая их количество. В этом случае матрице смежности будет состоять не только из 0 и 1. вот пример списка смежности для "сложного" ( относительно ) графа. Прикреплённая картинка
подскажите, плиз, где ошибся в списке смежности для этого графа + как должно быть правильно, буду признателен. спс за внимание |
Сообщ.
#2
,
|
|
|
А в чем смысл "ориентации" петель? Чем работа с "направленной" петлей отличается от работы с "ненаправленной"?
|
Сообщ.
#3
,
|
|
|
Цитата FasterHarder @ подскажите, плиз, где ошибся в списке смежности для этого графа + как должно быть правильно, буду признателен. Думаю, как-то так. Где в (*) указывает направленное ребро. a: b, c, c, d b: a, b, c, d c: a(*), a, a, b d: a, b, d(*) Дело в том, что если почитать про Теорию Графов, можно просто утонуть в "непричесанности" терминологии. Каждая прикладная область применения Теории Графов имеет свою специфику и свою терминологию. При составлении списка смежности, у нас основная задача - по списку в точности воспроизвести исходный граф, чтобы ничего не терялось. Последний твой пример - смешанный невзвешанный мультиграф. А вот если бы был еще и взвешенный, то пришлось бы в списке еще указывать и веса. А если быть точнее - двойки типа: N1: N2(наличие направления, вес), ...Nx(наличие направления, вес) ... Частично-взвешенных графов не бывает, не используют такое. Но это ЕМПИП. |
Сообщ.
#4
,
|
|
|
Для данного "сложного" графа (хотя что тут сложного? ну если не считать направления у некоторых рёбер, которое я проигнорирую) список смежности такой:
a: bcccd b: abcd c: aaab d: abd Длина списка для узла равна количеству уникальных рёбер с вершиной (для направленных графов - начальной) в этом узле. И соответственно элементы списка - это вторые узлы-вершины. |
Сообщ.
#5
,
|
|
|
Цитата Akina @ которое я проигнорирую Так низя. По такому списку не воспроизведешь в точности тот граф, который был описан. Цитата Akina @ Длина списка для узла равна количеству уникальных рёбер с вершиной И тут неверно. Длина списка равна просто количеству вершин. Ибо существуют еще такой тип, как "разорванные графы". Все вершины должны быть перечислены, даже просто отдельно стоящая несоединенная вершина. |
Сообщ.
#6
,
|
|
|
Цитата AVA12 @ А в чем смысл "ориентации" петель? Чем работа с "направленной" петлей отличается от работы с "ненаправленной"? это ведь похоже на схему дорог, связывающих города, а направление петли показывает тип движение: одностороннее или двустороннее тут вроде все ок Цитата Majestio @ При составлении списка смежности, у нас основная задача - по списку в точности воспроизвести исходный граф, чтобы ничего не терялось. я бы готов был согласиться с этим утверждением, если бы не одно НО(!): даже из названия "смежности" следует описание смежностей вершин ( соседство их ), а к весам это не имеет отношения, поэтому, если граф взвешенный, то необходимо добавлять весовую матрицу. С др. стороны эта информация может быть инкапсулирована каким-то образом в класс "Ребро" и пр., но это ладно... Изолированные вершины, безусловно, также участвуют в списке смежности, но у них NULL-список соседей Цитата Akina @ Для данного "сложного" графа (хотя что тут сложного? ну если не считать направления у некоторых рёбер, которое я проигнорирую) список смежности такой: ну относительно сложного), т к здесь постарался показать все моменты. А вот насчет игнорирования направления - зря, т к оч. хотелось увидеть именно список смежности для такого графа... ------------------------------------------------------------- в целом, только петли доставляют наибольшие неудобства например, есть такой список смежности: a: a - a если буду считывать его, то понимаю, что, первая пара соседей: a - a Прикреплённая картинка
затем снова пара: a - a и здесь начинаются проблемы! можно так построить: Прикреплённая картинка
в результате можно заменить на неориентированную петлю ( вроде ), т е: Прикреплённая картинка
а можно построить так: Прикреплённая картинка
но, теперь я понимаю, что AVA12 абсолютно верно указал на бесполезность ориентации петли ( если она без веса, разумеется ). По-большему счету ведь по хрен, есть ориентация у петли или нет: добраться все равно можно. то есть можно делать вывод: если нет весов, то направление петли мало на что влияет. с др.стороны, как заметил Majestio, должна быть возможность восстановить взаимосвязи между вершинами графа при считывании списка смежности еще пример ТОЛЬКО на петли: Прикреплённая картинка
------------------------------------------------- вывод: если петля имеет направление ( петля-дуга ), то 1 раз перечисляется, как сосед. Если не имеет - 2 раза. А если 3 раза, например, то тогда будет одна петля-ребро и одна петля-дуга)) То есть, при считывании списка смежности, надо считать количество соседей, имеющих такую же метку, как и текущая вершина. зы: какие же эти петли неудобные штуки! |
Сообщ.
#7
,
|
|
|
Сообщ.
#8
,
|
|
|
Цитата FasterHarder @ еще пример ТОЛЬКО на петли: a: a(*) a: a a: a(*), a(*) a: a(*), a(*) Последние две эквивалентны, ибо мы восстанавливаем только связи. Мы не занимаемся восстановлением географических координат вершин на плоскости, равно как и длину-кривизну ребер. Добавлено Цитата FasterHarder @ и все равно, вот этот момент надо окончательно прояснить: См выше. Два первых. Все со списка восстанавливается на отлично. |
Сообщ.
#9
,
|
|
|
Цитата Majestio @ И тут неверно. Длина списка равна просто количеству вершин Не списка, а списка для узла, т.е. длина списка смежных вершин в одной строке списка смежности. |
Сообщ.
#10
,
|
|
|
Цитата Akina @ Не списка, а списка для узла, т.е. длина списка смежных вершин в одной строке списка смежности. А, ну тогда да, все верно. |
Сообщ.
#11
,
|
|
|
Взвешена петля или нет - в любом смысле наличие у нее ориентации не имеет смысла. Дуга A -> B означает, что из A можно перейти в B, но из B нельзя перейти в A. Что тогда означает петля A -> A? Что из A можно попасть в A, но из A нельзя попасть в A?
|
Сообщ.
#12
,
|
|
|
насчет ориентации петли - согласен)
я об этом и писал раньше, что ты по делу заметил эту хрень с петлей в общем всем спс. за науку зы: со списком смежности надо разбираться конкретно с каждой задачей, адаптируя под данные - к такому выводу пришел...может это ошибочно, но пока такой вывод |