На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Список смежности для графа, для графа с петлями и мультиграфа , дискретная математика: графы и их представление
    Всем хай! Сходу к делу!

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

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


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

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


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

    спс за внимание
      А в чем смысл "ориентации" петель? Чем работа с "направленной" петлей отличается от работы с "ненаправленной"?
        Цитата FasterHarder @
        подскажите, плиз, где ошибся в списке смежности для этого графа + как должно быть правильно, буду признателен.

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

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

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

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

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

        Частично-взвешенных графов не бывает, не используют такое. Но это ЕМПИП.
          Для данного "сложного" графа (хотя что тут сложного? ну если не считать направления у некоторых рёбер, которое я проигнорирую) список смежности такой:
          ExpandedWrap disabled
            a: bcccd
            b: abcd
            c: aaab
            d: abd

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

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

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

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

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

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

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

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

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

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


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


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


              а можно построить так:
              Прикреплённая картинка
              Прикреплённая картинка


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

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

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

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

              зы: какие же эти петли неудобные штуки!
                и все равно, вот этот момент надо окончательно прояснить:
                Прикреплённая картинка
                Прикреплённая картинка
                  Цитата FasterHarder @
                  еще пример ТОЛЬКО на петли:

                  ExpandedWrap disabled
                    a: a(*)
                    a: a
                    a: a(*), a(*)
                    a: a(*), a(*)

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

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

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

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

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

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

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


                          Рейтинг@Mail.ru
                          [ Script execution time: 3,3337 ]   [ 21 queries used ]   [ Generated: 6.12.22, 00:22 GMT ]