Список смежности для графа, для графа с петлями и мультиграфа , дискретная математика: графы и их представление

[FasterHarder]

Всем хай! Сходу к делу!

хочется понять основательно представление графа в виде списка смежности. ЛЮБОГО графа...
в целом, как устроен список смежности - понятно, в инете полно инфы по этому поводу, но все примеры какие-то тривиальные

вот пример для неориентированного помеченного невзвешенного графа, состоящего из 4-рех вершин:

Прикреплённая картинка

а теперь рассмотрим, наверное, самый тяжелый случай ( ну, сложнее не смог придумать)): граф смешанный помеченный с петлями ( обоих типов: петля-ребро и петля-дуга ) + есть кратные ребра ( мультиграфность )
и непонятно стало, как петли обозначать + кратные ребра( дуги ) в списке смежности.
в матрице смежности еще с горем пополам можно как-то вести учет петель и кратных ребер, считая их количество. В этом случае матрице смежности будет состоять не только из 0 и 1.

вот пример списка смежности для "сложного" ( относительно ) графа.

Прикреплённая картинка

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

спс за внимание

[AVA12]

А в чем смысл "ориентации" петель? Чем работа с "направленной" петлей отличается от работы с "ненаправленной"?

[Majestio]

Цитата FasterHarder @ 29.08.22, 08:48

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

Думаю, как-то так. Где в (*) указывает направленное ребро.

a: b, c, c, d
b: a, b, c, d
c: a(*), a, a, b
d: a, b, d(*)

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

При составлении списка смежности, у нас основная задача - по списку в точности воспроизвести исходный граф, чтобы ничего не терялось. Последний твой пример - смешанный невзвешанный мультиграф. А вот если бы был еще и взвешенный, то пришлось бы в списке еще указывать и веса. А если быть точнее - двойки типа:

N1: N2(наличие направления, вес), ...Nx(наличие направления, вес) ...

Частично-взвешенных графов не бывает, не используют такое. Но это ЕМПИП.

[Akina]

Для данного "сложного" графа (хотя что тут сложного? ну если не считать направления у некоторых рёбер, которое я проигнорирую) список смежности такой:

a: bcccd
b: abcd
c: aaab
d: abd

Длина списка для узла равна количеству уникальных рёбер с вершиной (для направленных графов - начальной) в этом узле. И соответственно элементы списка - это вторые узлы-вершины.

Сообщение отредактировано: Akina - 29.08.22, 18:53

[Majestio]

Цитата Akina @ 29.08.22, 18:51

которое я проигнорирую

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

Цитата Akina @ 29.08.22, 18:51

Длина списка для узла равна количеству уникальных рёбер с вершиной

И тут неверно. Длина списка равна просто количеству вершин. Ибо существуют еще такой тип, как "разорванные графы". Все вершины должны быть перечислены, даже просто отдельно стоящая несоединенная вершина.

[FasterHarder]

Цитата AVA12 @ 29.08.22, 16:59

А в чем смысл "ориентации" петель? Чем работа с "направленной" петлей отличается от работы с "ненаправленной"?

это ведь похоже на схему дорог, связывающих города, а направление петли показывает тип движение: одностороннее или двустороннее
тут вроде все ок

Цитата Majestio @ 29.08.22, 18:48

При составлении списка смежности, у нас основная задача - по списку в точности воспроизвести исходный граф, чтобы ничего не терялось.

я бы готов был согласиться с этим утверждением, если бы не одно НО(!): даже из названия "смежности" следует описание смежностей вершин ( соседство их ), а к весам это не имеет отношения, поэтому, если граф взвешенный, то необходимо добавлять весовую матрицу. С др. стороны эта информация может быть инкапсулирована каким-то образом в класс "Ребро" и пр., но это ладно...
Изолированные вершины, безусловно, также участвуют в списке смежности, но у них NULL-список соседей

Цитата Akina @ 29.08.22, 18:51

Для данного "сложного" графа (хотя что тут сложного? ну если не считать направления у некоторых рёбер, которое я проигнорирую) список смежности такой:

ну относительно сложного), т к здесь постарался показать все моменты. А вот насчет игнорирования направления - зря, т к оч. хотелось увидеть именно список смежности для такого графа...
-------------------------------------------------------------
в целом, только петли доставляют наибольшие неудобства
например, есть такой список смежности:
a: a - a

если буду считывать его, то понимаю, что, первая пара соседей: a - a

Прикреплённая картинка

затем снова пара: a - a
и здесь начинаются проблемы!
можно так построить:

Прикреплённая картинка

в результате можно заменить на неориентированную петлю ( вроде ), т е:

Прикреплённая картинка

а можно построить так:

Прикреплённая картинка

но, теперь я понимаю, что AVA12 абсолютно верно указал на бесполезность ориентации петли ( если она без веса, разумеется ). По-большему счету ведь по хрен, есть ориентация у петли или нет: добраться все равно можно.

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

еще пример ТОЛЬКО на петли:

Прикреплённая картинка

-------------------------------------------------
вывод: если петля имеет направление ( петля-дуга ), то 1 раз перечисляется, как сосед. Если не имеет - 2 раза.
А если 3 раза, например, то тогда будет одна петля-ребро и одна петля-дуга))
То есть, при считывании списка смежности, надо считать количество соседей, имеющих такую же метку, как и текущая вершина.

зы: какие же эти петли неудобные штуки!

[FasterHarder]

и все равно, вот этот момент надо окончательно прояснить:

Прикреплённая картинка

[Majestio]

Цитата FasterHarder @ 30.08.22, 03:55

еще пример ТОЛЬКО на петли:

a: a(*)
a: a
a: a(*), a(*)
a: a(*), a(*)

Последние две эквивалентны, ибо мы восстанавливаем только связи. Мы не занимаемся восстановлением географических координат вершин на плоскости, равно как и длину-кривизну ребер.

Добавлено 30.08.22, 04:10

Цитата FasterHarder @ 30.08.22, 03:59

и все равно, вот этот момент надо окончательно прояснить:

См выше. Два первых. Все со списка восстанавливается на отлично.

[Akina]

Цитата Majestio @ 29.08.22, 18:57

И тут неверно. Длина списка равна просто количеству вершин

Не списка, а списка для узла, т.е. длина списка смежных вершин в одной строке списка смежности.

[Majestio]

Цитата Akina @ 30.08.22, 04:36

Не списка, а списка для узла, т.е. длина списка смежных вершин в одной строке списка смежности.

А, ну тогда да, все верно.

[AVA12]

Взвешена петля или нет - в любом смысле наличие у нее ориентации не имеет смысла. Дуга A -> B означает, что из A можно перейти в B, но из B нельзя перейти в A. Что тогда означает петля A -> A? Что из A можно попасть в A, но из A нельзя попасть в A?

[FasterHarder]

насчет ориентации петли - согласен)
я об этом и писал раньше, что ты по делу заметил эту хрень с петлей

в общем всем спс. за науку

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