Построить граф онлайн по матрице смежности: Матрица смежности | Вики справка Graph Online

Построение графов для чайников: пошаговый гайд / Хабр

Ранее мы публиковали пост, где с помощью графов проводили анализ сообществ в Точках кипения из разных городов России. Теперь хотим рассказать, как строить такие графы и проводить их анализ.

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

1. Выбор гипотезы

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

Для этого разберитесь, какие данные у вас уже есть, что из них можно представить «объектами», а что – «связями» между ними. Обычно объектов значительно меньше, чем связей — можно таким образом проверять себя.

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

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

Во втором случае мы решили узнать, как соотносится принадлежность участников к одному из «нетов» (наших ключевых направлений) с интересующими их сквозными технологиями. Равномерно ли распределение, есть ли «горячие темы»? Для этого анализа мы взяли данные по участникам мероприятий из 200 томских технологических компаний.

В принципе, даже таких первичных формулировок гипотез достаточно, чтобы перейти ко второму шагу.

2. Подготовка данных

Теперь, когда вы определились с тем, что хотите узнать, возьмите весь массив данных, посмотрите, какая информация об «объектах» хранится, выкиньте все лишнее и добавьте недостающее. Если данные распределены по нескольким источникам, предварительно соберите все в одну кучу, убрав дубли.

Поясню на примере. У нас были данные об участниках 650 мероприятий. Это, условно говоря, 650 эксель-таблиц с ~23000 записей в них, содержащих поля «Leader ID», «Должность», «Организация». Для постройки графа достаточно одного уникального идентификатора (тут, к счастью, такой есть – это Leader ID) и признака, привязывающего каждого участника к одной из трех рассматриваемых сфер: власти, бизнесу или университетам. И этой информации у нас еще нет.

Чтобы получить ее, можно пойти напролом: в каждом из 650 файлов убрать лишние столбцы и добавить новое поле, заполнить его значениями для каждой строки, например: «1» для власти, «2» для бизнеса и «3» для образования и науки. А можно сначала объединить все 650 файлов в один большой список, убрать дубли и только после этого добавлять новые значения. В первом случае такая работа займет 1-2 месяца. Во втором — 1-2 недели.

Вообще при добавлении новых атрибутов старайтесь предварительно группировать данные.

Например, можно отсортировать участников по компаниям/организациям и скопом выставлять признак.

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

Файл вершин в нашем случае содержал два столбца: Id — номер вершины и Label — тип. Файл ребер содержал также два столбца: Source — id начальной вершины, Target — id конечной вершины.

Как превратить данные о том, что участники 1, 2, 5 и 23 посетили одно мероприятие, в ребра? Необходимо создать шесть строк и отметить связь каждого участника с каждым: 1 и 2, 1 и 5, 1 и 23, 2 и 5, 2 и 23, 5 и 23.

Во втором нашем примере таблицы выглядели так:

В качестве вершин перечислены как рынки, так и сквозные технологии. Если, скажем, представитель компании, относящейся к рынку «Технет» (ID=4), посетил мероприятие по теме «Большие данные и ИИ» (ID=17), в таблицу ребер заносим ребро (строку), соединяющее эти вершины (Source=4, Target=17).

Этап подготовки данных – это самая трудоемкая часть процесса, но наберитесь терпения.

3. Визуализация графа

Итак, таблицы с данными подготовлены, можно искать средство для их представления в виде графа. Для визуализации мы использовали программу Gephi — мощный опенсорсный инструмент, способный обрабатывать графы с сотнями тысяч вершин и связей. Скачать его можно с официального сайта.

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

Первым делом нам надо загрузить таблицы с вершинами и ребрами. Для этого выбираем пункт «Импортировать из CSV» из меню раздела «Лаборатория данных».

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

На третьей форме «Отчет об импорте» важно указать тип графа. У нас он не ориентирован.

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

Важный момент ждет нас в третьем окне «Отчет об импорте». Тут важно указать не только то, что граф не ориентирован, но и подгрузить ребра в то же рабочее пространство, что и вершины. Поэтому выбираем пункт «Append to existing workplace».

В результате перед нами предстанет граф примерно вот в таком виде (закладка «Обработка»):

Итак, ребра имеют разную толщину в зависимости от количества связей между вершинами. Посмотреть, какой вес стал у каждого ребра, можно на закладке «Лаборатория данных» в свойствах ребер в столбце Weight.

Что здесь плохо: все вершины имеют один размер и расположены абсолютно произвольно. На закладке «Обработка» мы это исправим. Сначала в верхнем левом окне выбираем Nodes и жмем на пиктограммку с кругами («Размер»). Далее выбираем пункт Ranking — он позволяет задать размер вершины в зависимости от какого-либо параметра. У нас есть возможность выбрать только один параметр — Degree (степень), который показывает, сколько ребер выходят из вершины. Выбираем минимальный и максимальный размер кружочка и жмем кнопку «Применить». Здесь же, если выбрать другие пиктограммки, можно настроить цвет маркера вершины и цвет ребер. Теперь граф уже более нагляден.

Следующее, что нужно сделать, — распутать граф. Это можно сделать вручную, двигая вершины, а можно использовать алгоритмы укладки, которые реализованы в Gephi.

Чего мы добиваемся правильной укладкой? Максимальной наглядности. Чем меньше на графе наложений вершин и ребер, чем меньше пересечений ребер, тем лучше. Также неплохо было бы, чтобы смежные вершины были расположены поближе друг к другу, а несмежные —подальше друг от друга. Ну и все было распределено по видимой области, а не сжато в одну кучу.

Как это сделать в Gephi? Левое нижнее окно «Укладка» содержит самые популярные алгоритмы укладки, построенные на силовых аналогиях. Представьте, что вершины — это заряженные шарики, который отталкиваются друг от друга, но при этом некоторые скреплены чем-то, похожим на пружинки. Если задать соответствующие силы и «отпустить» граф, вершины разбегутся на максимально допустимые пружинками расстояния.

Наиболее равномерную картину дает алгоритм Фрюхтермана и Рейнгольда. Выберите Fruchterman Reingold из выпадающего меню и задайте размер области построения. Нажмите кнопку «Исполнить». Получится что-то вроде этого:

Можно помочь алгоритму и, не останавливая его, поперетаскивать некоторые вершины, стараясь распутать граф. Но помните, что здесь нет кнопки «Отменить», вернуться к прежнему расположению вершин уже не удастся. Поэтому сохраняйте новые версии проекта перед каждым рискованным изменением.

Еще один полезный алгоритм — Force Atlas 2. Он представляет граф в виде металлических колец, связанных между собой пружинами. Деформированные пружины приводят систему в движение, она колеблется и в конце концов принимает устойчивое положение. Этот алгоритм хорош для визуализаций, подчеркивающих структуру группы и выделяющих подмножества с высокой степенью взаимодействия.

Этот алгоритм имеет большое количество настроек. Рассмотрим наиболее важные. «Запрет перекрытия» запрещает вершинам перекрывать друг друга. Разреженность увеличивает расстояние между вершинами, делая граф более читаемым. Также более воздушным граф делает уменьшение влияния весов ребер на взаимное расположение вершин.

Поигравшись с настройками, получим такой граф:

Получив граф в том виде, который вас устраивает, переходите к финальной обработке. Это закладка «Просмотр». Здесь мы можем задать, например, отрисовку графа кривыми ребрами, которая минимизирует наложение вершин на чужие ребра. Можем включить подписи вершин, задав размер и цвет шрифта. Наконец, поменять фон подложки. Например, так:

Для того чтобы сохранить получившийся рисунок, нажмите на надпись «Экспорт SVG/PDF/PNG в левом нижнем углу окна. Также отдельно не забудьте сохранить сам проект через верхнее меню «Файл» — «Сохранить проект».

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

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

Вы, наверное, думаете, как нам удалось раскрасить вершины в разный цвет? Есть одна хитрость. Можно перейти в закладку «Лаборатория данных», создать там новый столбец в вершинах, назвав его «Market». И заполнить для каждой вершины значениями: 1 если это рынок НТИ, 0 — если сквозная технология. Затем достаточно перейти в «Обработку», выбрать пиктограммку в виде палитры, Nodes — Partition, а в качестве разделителя — наш новый атрибут Market.

Для более сложных построений, когда требуется выделить кластеры и закрасить их разными цветами, в Gephi используется богатый арсенал статистических расчетов, результаты которых можно использовать для раздельной окраски. Находятся эти расчеты в правом столбце вкладки «Обработка».

Например, нажав кнопку «Запуск» возле расчета «Модулярность», вы узнаете оценку уровня кластеризации вашего графа. Если после этого выставить цвет вершин в зависимости от Modularity Class, появится симпатичная картинка наподобие такой:

Если вы хотите еще больше узнать о возможностях Gephi, стоит почитать руководство по работе с программой от Мартина Гранджина http://www. martingrandjean.ch/gephi-introduction/.

4. Анализ результата

Итак, вы получили итоговую визуализацию графа. Что она вам дает? Во-первых, это красиво, ее можно вставить в презентацию, показать знакомым или сделать заставкой на рабочем столе. Во-вторых, по ней вы можете понять, насколько сложной и многокластерной структурой является рассматриваемая вами предметная область. В-третьих, обратите внимание на самые крупные вершины и на самые жирные связи. Это особенные элементы, на которых все держится.
Так, построив граф экспертного сообщества, посещающего мероприятия в Точке кипения, мы сразу обнаружили участников, которые с наибольшей вероятностью выполняют роль суперконнекторов. Они являлись «вершинами», через которые кластеры объединялись в единое целое. А во втором случае мы увидели, как выглядит концентрация специалистов из томских компаний с точки зрения их принадлежности к рынку и сквозной цифровой технологии, на которую они делают ставку. Это косвенно говорит об уровне технологических компетенций и экспертизы региона.

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

9.3. Матрица смежности

Матрица смежности S — это квадратная матрица, в которой и число строк, и число столбцов равно n — числу вершин графа. В ячейки матрицы смежности записываются некоторые числа в зависимости от того, соединены соответствующие вершины рёбрами или нет, и от типа графа.

Матрица смежности для неориентированного графа

Элемент матрицы смежности sij неориентированного графа определяется следующим образом:

— равен единице, если вершины vi и vj смежны;

— равен нулю, если вершины vi и vj не смежны.

Если на диагонали матрицы стоят 1, то это показывает наличие петель.

Пример 5. Составить матрицу смежности для графа, представленного на рисунке ниже.

Пример 6. Или составить граф, или составить матрицу.

Таким образом, матрица смежности неориентированного графа симметрична относительно главной диагонали.

Матрица смежности для ориентированного графа

Элемент матрицы смежности sij ориентированного графа определяется следующим образом:

— равен единице, если из вершины vi в вершину vj входит дуга;

— равен нулю, если из вершины vi в вершину vj дуга не входит.

Если на диагонали матрицы стоят 1, то это показывает наличие петель.

Пример 7. Составить матрицу смежности для графа, представленного на рисунке ниже.

Пример 8. Составить матрицу смежности для графа, представленного на рисунке ниже. Или наоборот, построить граф по матрице смежности.

Таким образом, матрица смежности ориентированного графа не симметрична.

9.4. Список ребер

Пример 1.а. Составить список ребер для графа (1,е1,2), (1,е5,5), (2,е6,5), (2,е2,3), (5,е4,4), (3,е3,4), (4,е7,6).

9.1-9.4

Пример 1. (москинова). Задать матрицами инцидентности и смежности, а также списком ребер графы G1 и G3. Матрицы инцидентности Матрицы смежности Список ребер графа G3

9.5. Матрица достижимости

Матрица достижимости простого ориентированного графа G=(V,E) — бинарная матрица замыкания по транзитивности отношения E (оно задаётся матрицей смежности графа). Таким образом, в матрице достижимости хранится информация о существовании путей между вершинами орграфа.

Возведение в степень матрицы смежности орграфа показывает, за сколько шагов (величина степени) можно достичь некой вершины.

Способы построения матрицы достижимости:

1. Перемножение матриц

2. Алгоритм Уоршелла

3. Связанные понятия

Пример 1. Перемножение матриц. (википедия) Дан простой связный ориентированный граф. Он имеет матрицу смежности вида: Найдем булевы степени этой матрицы Е2, Е3, Е4. Матрица E1 показывает, в какие вершины мы можем попасть за 1 шаг. Матрица E2 показывает, в какие вершины мы можем попасть за 2 шага. Матрица E3 показывает, в какие вершины мы можем попасть за 3 шага. Матрица E4 показывает, в какие вершины мы можем попасть за 4 шага. Если посмотреть, то за второй шаг мы попадаем во все вершины, в которые не попали за первый шаг. Получим матрицу достижимости. Она показывает, есть ли путь из вершины a в вершину b. Если просто взять и сложить найденные четыре матрица Е, Е2, Е3, Е4, то получим матрицу, которая показывает количество путей длины от 1 до 4 между вершинами орграфа.

Пример 2. (мой). Составить матрицу достижимости и контрдостижимости.

Граф g задан матрицей инцидентности

Говорить о том, что ребро g и каждая из вершин u и y инцидентна g, стоит лишь в том случае, если g соединяет u и y. Уяснив это, перейдем к рассмотрению данного метода. Матрица инцидентности строиться по похожему, но не по тому же принципу, что и матрица смежности. Так если последняя имеет размер n×n, где n – число вершин, то матрица инцидентности – n×m, здесь n – число вершин графа, m – число ребер. То есть теперь чтобы задать значение какой-либо ячейки, нужно сопоставить не вершину с вершиной, а вершину с ребром.

В каждой ячейки матрицы инцидентности неориентированного графа стоит 0 или 1, а в случае ориентированного графа, вносятся 1, 0 или -1.

То же самое, но наиболее структурировано:

1. Неориентированный граф:

· 1 – вершина инцидентна ребру;

· 0 – вершина не инцидентна ребру.

2. Ориентированный граф:

· 1 – вершина инцидентна ребру, и является его началом;

· 0 – вершина не инцидентна ребру;

· -1 – вершина инцидентна ребру, и является его концом.

Построим матрицу инцидентности сначала для неориентированного графа (рис. 3.10), а затем для орграфа (рис. 3.11). Ребра обозначим буквами от a до e, вершины – цифрами. Все ребра графа не направленны, поэтому матрица инцидентности заполнена положительными значениями.

Рисунок 3.10 – Неориентированный граф и его матрица инцидентности

Для орграфа матрица имеет немного другой вид. В каждую из ее ячеек внесено одно из трех значений. Обратите внимание, что нули в двух этих матрицах занимают одинаковые позиции, ведь в обоих случаях структура графа одна. Но некоторые положительные единицы сменились на отрицательные, например, в неориентированном графе ячейка (1, b) содержит 1, а в орграфе -1. Дело в том, что в первом случае ребро b не направленное, а во втором – направленное, и, причем вершиной входа для него является вершина «1».

Рисунок 3.11 – Ориентированный граф и его матрица инцидентности

Каждый столбец отвечает за какое-либо одно ребро, поэтому граф, описанный при помощи матрицы инцидентности, всегда будет иметь следующий признак: любой из столбцов матрицы инцидентности содержит две единицы, либо 1 и -1 когда это ориентированное ребро, все остальное в нем – нули.

В программе матрица инцидентности задается, также как и матрица смежности, а именно при помощи двумерного массива. Его элементы могут быть инициализированы при объявлении, либо по мере выполнения программы.

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Только сон приблежает студента к концу лекции. А чужой храп его отдаляет. 8831 —

| 7545 — или читать все.

78.85.5.224 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)
очень нужно

Инцидентность вершин и рёбер графа, смежность вершин графа

Инцидентность — это когда вершина a является либо началом либо концом ребра e. Две вершины называются инцидентными, если у них есть общее ребро.

Для того, чтобы задать граф аналитически, множества V вершин графа и множества U рёбер графа, которые фигурировали в определении графа, будет недостаточно. Потребуется ещё и множество P троек вида (a, u, b) , указывающих какую пару a, b элементов множества вершин V соединяет тот или иной элемент u множества рёбер U графа. Элементы множества P называются инциденциями графа. Вот мы и подошли к одному из первых понятий теории графов — инцидентности.

Понятие инцидентности — одно из главных при создании структур данных для представления графов в памяти ЭВМ, к которым мы перейдём после примера 1.

Пример 1. Задать аналитически граф, представленный на рисунке ниже. (рис. А)

Решение. Распространённые ошибки — не заметить вершины графа, которые не соединены ни с одной другой вершиной, в том числе с самой собой, и не включить их во множество вершин графа, а также указать не все рёбра графа, соединяющие две вершины. Поэтому вершину f данного графа обязательно включаем во множество вершин графа V , а, рёбра 6 и 7, хотя они соединяют одну и ту же вершину саму с собой и обе не имеют направления, включаем во множество рёбер U .

Итак, задаём граф следующими множествами:

множество рёбер: U =

Смежность вершин графа — это когда две вершины графа соединены ребром.

Зададимся вопросом: можно ли поместить слона в компьютер? Ответ: можно, если слона смоделировать в виде графа, в котором вершинами являются части его тела, а рёбра соединяют те части тела, которые соединены в слоне как биологическом объекте. При этом получившийся граф должен быть представлен в памяти компьютера в понятном компьютеру виде.

В связи с широким применением графов в программировании и информационных технологиях вообще возникает вопрос о представлении графа в виде структуры данных. Различные способы представления графов в памяти компьютера отличаются объёмом занимаемой памяти и скоростью выполнения операций над графами.

Наиболее часто используются три такие структуры данных — матрица смежности, матрица инцидентности и список инцидентности.

Матрицы смежности

Матрица смежности, как и матрица инцидентности, позволяет установить множество вершин, соседних с заданной (то есть рассматриваемой в конкретной задаче), не прибегая к полному просмотру всей матрицы. Матрицы смежности обычно представляются двумерным массивом размера n x n , где n — число вершин графа.

Матрица смежности S — это квадратная матрица, в которой и число строк, и число столбцов равно n — числу вершин графа. В ячейки матрицы смежности записываются некоторые числа в зависимости от того, соединены соответствующие вершины рёбрами или нет, и от типа графа.

Матрица смежности для неориентированного графа

Элемент матрицы смежности s ij неориентированного графа определяется следующим образом:

— равен единице, если вершины v i и v j смежны;

— равен нулю, если вершины v i и v j не смежны.

Если для элемента матрицы v ij имеет место i = j , то есть элемент находится на диагонали, то этот элемент равен единице, если этот элемент имеет петлю, и нулю, если элемент не имеет петли.

Пример 2. Составить матрицу смежности для графа, представленного на рисунке ниже.

V	1	2	3	4	5
1	0	1	1	0	0
2	1	0	0	1	1
3	1	0	0	0	1
4	0	1	0	0	0
5	0	1	1	0	0

Таким образом, матрица смежности неориентированного графа симметрична относительно главной диагонали.

Матрица смежности для ориентированного графа

Элемент матрицы смежности s ij ориентированного графа определяется следующим образом:

— равен единице, если из вершины v i в вершину v j входит дуга;

— равен нулю, если из вершины v i в вершину v j дуга не входит.

Как и для неориентированных графов, так и для ориентированных, если для элемента матрицы v ij имеет место i = j , то есть элемент находится на диагонали, то этот элемент равен единице, если этот элемент имеет петлю, и нулю, если элемент не имеет петли.

Пример 3. Составить матрицу смежности для графа, представленного на рисунке ниже.

V	1	2	3	4	5
1	0	1	0	0	0
2	0	1	0	0	0
3	1	0	0	0	0
4	0	1	0	0	0
5	0	1	1	0	0

Таким образом, матрица смежности ориентированного графа не симметрична.

Матрица смежности для графа с кратными рёбрами

Если в графе есть вершины, соединённые между собой несколькими рёбрами, то элемент матрицы смежности s ij равен числу рёбер, соединяющих вершины v i и v j . Из этого следует, что если вершины v i и v j не соединены рёбрами, то элемент матрицы смежности s ij равен нулю.

Пример 4. Составить матрицу смежности для графа, представленного на рисунке ниже.

V	1	2	3	4	5
1	0	3	2	0	0
2	3	0	0	1	1
3	2	0	0	0	1
4	0	1	0	0	0
5	0	1	1	0	0

Матрица смежности для взвешенного графа

В случае взвешенного графа элемент матрицы смежности s ij равен числу w, если существует ребро между вершинами v i и v j с весом w. Элемент s ij равен нулю, если рёбер между вершинами v i и v j не существует.

Пример 5. Составить матрицу смежности для графа, представленного на рисунке ниже.

V	1	2	3	4	5
1	0	11	9	0	0
2	11	0	0	5	8
3	9	0	0	0	2
4	0	5	0	0	0
5	0	8	2	0	0

Матрицы инцидентности

Матрица инцидентности H — это матрица размера n x m , где n — число вершин графа, m — число рёбер графа. Обычно в матрице инцидентности строки соответствуют вершинам графа, а столбцы — рёбрам графа.

Матрица инцидентности для неориентированного графа

Элемент матрицы инцидентности для неориентированного графа h ij определяется следующим образом:

— равен единице, если вершина v i инцидентна ребру e j ;

— равен нулю, если вершина v i не инцидентна ребру e j .

Пример 6. Составить матрицу инцидентности для графа, представленного на рисунке ниже.

V	1-2	1-3	2-4	2-5	3-5
1	1	1	0	0	0
2	1	0	1	1	0
3	0	1	0	0	1
4	0	0	1	0	0
5	0	0	0	1	1

Матрица инцидентности для ориентированного графа

Элемент матрицы инцидентности для ориентированного графа h ij определяется следующим образом:

— равен минус единице, если вершина v i является началом ребра e j ;

— равен единице, если вершина v i является концом ребра e j ;

— равен нулю, если вершина v i не инцидентна ребру e j .

Пример 7. Составить матрицу инцидентности для графа, представленного на рисунке ниже.

V	1-2	1-3	2-4	2-5	3-5
1	1	-1	0	0	0
2	-1	0	-1	-1	0
3	0	1	0	0	-1
4	0	0	1	0	0
5	0	0	0	1	1

Списки инцидентности

Графы значительного объёма целесообразно хранить в памяти компьютера в форме списков инцидентности.

Список инцидентности одной вершины графа включает номера вершин, смежных с ней.

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

Пример 8. Составить списки инцидентности для графа, представленного на рисунке ниже.

Матрицы смежности и инцидентности целесообразнее использовать когда:

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

Из-за последнего обстоятельства матрицы чаще используются в теоретических исследованиях графов.

Списки инцидентности целесообразнее использовать когда:

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

На практике списки чаще используются в прикладных целях.

На данной странице вы можете задать матрицу инцидентности и построить по ней граф

© Граф Online — создание и визуализация графа в два клика или по матрице смежности и поиск кратчайшего пути, поиск компоненты связности, поиск Эйлеровго цикла. Поделиться: Twitter, Facebook, В Контакте. 2015 — 2019

сделать визуализацию сети онлайн с помощью наших шаблонов, руководств и четких документов.

Graph Studio — визуальный редактор сетевых данных. Используя Graph Studio, вы можете создавать объекты, соединять их, отображая отношения, редактировать стили и макет визуализации — и видеть все это в режиме реального времени. С помощью Graph Studio вы можете импортировать электронную таблицу Excel для создания визуализации и экспортировать визуализацию обратно в электронную таблицу.

Существует два способа создания визуализации сети в Graph Studio: 1) редактирование в самой Graph Studio с помощью нашего визуального редактора или 2) редактирование в электронной таблице Excel с последующим импортом электронной таблицы в Rhumbl.

Новичкам мы рекомендуем сначала проработать следующий раздел создания карты с помощью Graph Studio, а затем перейти к примеру импорта электронной таблицы.

Визуальное редактирование

Давайте создадим первую карту в Graph Studio, чтобы познакомиться с основами редактирования в Graph Studio.

Начните с нажатия «Новая карта» на домашней панели и выберите первый вариант «Создать новую карту» . Существует два способа создания карт: 1) вырезать карту из примера шаблона, как мы делаем сейчас, или 2) загрузить электронную таблицу Excel.

На следующем экране вы увидите возможность выбрать шаблон данных:

Эти примеры приведены здесь только для того, чтобы вы начали; данные полностью доступны для редактирования. В этом уроке мы выберем первый пример — Education. Следующий экран позволяет выбрать цветовую схему. Эта цветовая схема также полностью редактируема, так что пока просто выберите цветовую схему, которая кажется вам наиболее привлекательной. Мы пойдем по схеме «Лайт».

Вы создали свою первую карту!

Создание объектов

Одной из фундаментальных идей сетевой визуализации является идея сущностей . Сущность — это важная вещь в ваших данных. Объекты могут быть визуализированы как узлов на карте, или они могут быть группирующими объектов. Объекты группового типа не визуализируются на карте — они служат только «контейнером» для хранения других объектов. Узнайте больше об основах сущностей и типов сущностей.

Обратите внимание, что в примере с образованием у нас есть 3 типа сущностей: убер группа , отдел и тема . Вы можете переименовать эти типы сущностей, но вы не можете изменить, являются ли они сущностью типа узла или группы.

Давайте создадим новый тип объекта с именем учитель и сделаем его объектом типа узла:

Теперь давайте создадим новую сущность типа учитель . Нажмите кнопку «Редактировать объекты», чтобы открыть панель, нажмите «Добавить объект» и создайте объект с именем губка боб квадратные штаны 9.0034 . Укажите тип объекта как учитель (тип объекта, который мы только что создали).

Нажмите Сохранить. Если вы сейчас посмотрите на свою карту, то увидите красный узел, и если вы наведете на него курсор, вы должны увидеть квадратные штаны губки боба .

Причина, по которой он красный, заключается в том, что легко сказать, что это вновь созданная сущность. Это очень полезно, когда вы работаете над картами с несколькими людьми и хотите посмотреть, что изменилось.

Важно! На данный момент внесенные вами изменения не сохраняются навсегда. Если вы обновите страницу или закроете окно, эти изменения будут потеряны. Чтобы сохранить их навсегда, нажмите кнопку Сохранить на панели меню:

Установление отношений

На данный момент вы создали один тип сущности ( учитель ) и создали узел этого типа. Другой фундаментальной концепцией визуализации графа является идея взаимосвязей 9.0014 между сущностями. Давайте установим связь между Спанч Бобом и обратно.

Во-первых, посмотрите на резюме Отношения. Существует уже три существующих типа отношений. Первый из них особенный и называется HAS_PARENT_OF — это родительское отношение типа: отношения родительского типа описывают, как группируются сущности. Узнайте больше об основах отношений и типах отношений.

Мы добавим родительские отношения, начиная с от Губка Боб до Математика . Нажмите Добавить связь:

Щелкните Сохранить. На первый взгляд кажется, что ничего не произошло: карта выглядит так же! Это потому, что вам нужно сказать Rhumbl восстановить макет для вас, нажав кнопку «Обновить». Подождите... и новый узел теперь сгруппирован под своим новым родителем Math :

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

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

Теперь мы создадим еще одно отношение, указывая от Спанч Боб - Дифференциальные уравнения типа учит . После создания этой связи вы должны увидеть новую связь красным цветом:

И, как и раньше, чтобы увидеть, как этот новый край может повлиять на макет, нажмите «Обновить», чтобы заново создать макет визуализации.

Вот и все! Вот как вы создаете карту, используя метод визуального редактирования. Далее мы поговорим о создании карты методом редактирования электронных таблиц.

Редактирование электронной таблицы в формате списка смежности

При использовании метода редактирования электронной таблицы вы редактируете электронную таблицу Excel на своем компьютере, а затем загружаете эту электронную таблицу в Graph Studio.

Электронная таблица должна быть в одном из следующих форматов: Список смежности или Матрица смежности. Многие пользователи сообщают, что список смежности стал немного более интуитивным, поэтому мы начнем с него в этом руководстве.

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

Шаг 1 Для начала загрузите пример списка смежности. Затем перейдите на панель инструментов, нажмите «Создать новую карту» и выберите «Загрузить электронную таблицу Rhumbl».

Формат списка смежности перечисляет каждый объект в каждой строке и столбцы объекта в столбцах. Давайте посмотрим на эту первую строку в электронной таблице:

.

СЧ	Школа	тип

Эта первая строка описывает сущность, чей id равен SCH , имя -- это School , чей тип -- это School . Эти три свойства обязательны . Подробнее о столбцах электронной таблицы см.

Шаг 2 Затем загрузите данные, как будет предложено. Вы увидите следующий результат анализа:

Это говорит о том, что Rhumbl понял из электронной таблицы, что всего существует 7 сущностей, и среди этих 7 сущностей есть 11 взаимосвязей. Что это за отношения?

Есть два соответствующих отношения, проанализированных из этих ячеек в нашей электронной таблице:

Это говорит о том, что мех имеет аналог calc-1 , а em имеет аналог calc-2 .

У нас также есть 6 предпосылок отношений:

У нас тоже куча принадлежит отношениям. Говорят, что каждый объект принадлежит к одной группе . Единственная сущность, не имеющая родительской группы, — это корневая сущность, которой в нашем случае является сущность School. Эта строка говорит о том, что Департамент X находится в подчинении Школы.

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

Rhumbl предоставляет вам несколько различных цветовых схем. Вы можете изменить определенные цвета позже, но сейчас мы просто выберем схему Dark .

Ну вот! Это два основных способа визуализации графика: либо через визуальный редактор, либо через редактирование электронной таблицы. Мы предлагаем сразу же составить карту или просмотреть несколько примеров электронных таблиц.

Инструменты и подходы к визуализации больших графиков | by Sviatoslav Iguana

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

(Это перевод моей статьи на хабре, изначально написанной на русском языке)

1. Чтобы найти то, что нужно искать
   Обычно у нас просто есть набор вершин и ребер в качестве входных данных. Мы можем вычислить некоторую статистику или графические метрики на основе таких данных, но этого недостаточно, чтобы получить представление о структуре. Хорошая визуализация может четко показать, есть ли на графе какие-то кластеры или мосты, а может это однородное облако, или что-то еще.
2. Чтобы произвести впечатление на публику
   Очевидно, что визуализация данных используется для презентации. Это хороший способ показать выводы из проделанной работы. Например, если вы решили задачу кластеризации, вы можете раскрасить свой график метками и показать, как они связаны.
3. Для получения характеристик
   Несмотря на то, что большинство инструментов визуализации графиков были созданы только для создания некоторых изображений, они также хороши в качестве инструментов уменьшения размеров. Граф, представленный в виде матрицы смежности, представляет собой данные в многомерном пространстве. При его рисовании мы получаем две (обычно) координаты для каждой вершины. Эти координаты также можно использовать в качестве признаков. Близость между вершинами в этом пространстве означает сходство.

Что за проблемы с большими графами?

Под «большим графом» я буду понимать размеры примерно от 10К вершин и/или ребер. С меньшими размерами проблем обычно не возникает. Все инструменты, которые вы найдете поиском в несколько минут, скорее всего, будут работать как минимум приемлемо. Что не так с большими сетями? Основных проблем две: читабельность и скорость. Обычно визуализация большого графика выглядит беспорядочно, потому что на одном графике слишком много объектов. Кроме того, алгоритмы визуализации графов в большинстве своем имеют ужасную алгоритмическую сложность: квадратичная или кубическая зависимость от количества ребер или вершин. Даже если вы дождетесь результата один раз, найти лучшие параметры будет слишком долго.

[1] Хелен Гибсон, Джо Фейт и Пол Викерс: «Обзор методов компоновки двумерных графов для визуализации информации»

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

[2] О-Хюн Квон, Тарик Црновсанин и Кван-Лю Ма «Как будет выглядеть график на этом макете? Подход машинного обучения к визуализации больших графиков»

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

Компоновка — это способ сопоставления координат с каждой вершиной. Обычно это координаты на 2D-плоскости.

Что такое хороший макет?

Легко сказать, хорошо что-то выглядит или плохо. Критерии назвать не так просто, как машина могла бы это оценить. Чтобы сделать так называемый «хороший» макет, можно использовать эстетические метрики. Вот некоторые из них:

1. Минимальное пересечение ребер
   Это очевидно: слишком много пересечений делают график беспорядочным.
2. Смежные вершины ближе друг к другу, чем несмежные
   Логично, что соединенные узлы должны быть близки друг к другу. Он представляет собой основную информацию, присутствующую в графе по определению.
3. Сообщества сгруппированы в кластеры
   Если есть набор вершин, которые связаны друг с другом чаще, чем с другими частями графа, они должны выглядеть как плотное облако.
4. Минимальное количество перекрывающихся ребер и узлов.
   Тоже очевидно: если мы не можем определить, мало ли вершин или одна, то читабельность графика плохая.

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

• Силовой и энергетический
• Уменьшение размеров
• Узловые особенности на основе

Силовые и энергетические схемы

Примеры силовых компоновок. Источник изображения: [1]

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

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

Важными членами этой семьи являются Force Atlas, Fruchterman-Reingold, Kamada Kawaii и OpenOrd. Последний использует хитрые оптимизации для ускорения вычислений, например, обрезает длинные ребра. В качестве полезного побочного эффекта график становится более сгруппированным.

Уменьшение размеров

Примеры макетов уменьшения размеров. Источник изображения: [1]

Граф можно определить как матрицу смежности NxN, где N — количество узлов. Эту матрицу также можно рассматривать как таблицу из N объектов в N-мерном пространстве. Это представление позволяет нам использовать методы уменьшения размерности общего назначения, такие как PCA, UMAP, tSNE и т. д. Другой способ — вычислить теоретические расстояния между узлами, а затем попытаться сохранить пропорции при переходе в пространство с меньшими размерностями.

Макет на основе функций

Пример участка улья. Источник изображения: [1]

Обычно графические данные связаны с некоторыми объектами реального мира. Таким образом, вершины и ребра могут иметь свои особенности. Поэтому мы можем использовать эти функции для представления их на плоскости. Мы можем работать с узловыми признаками, как с обычными табличными данными, используя упомянутые выше методы уменьшения размерности или напрямую рисуя точечный график для пар признаков. Стоит упомянуть Hive Plot, потому что он сильно отличается от всех остальных методов. В ульевом участке узлы выровнены по нескольким радиальным осям, а ребра представляют собой кривые между ними.

Радость визуализации графиков.

Несмотря на то, что проблема визуализации графов относительно старая и популярная, с инструментами, которые могут работать с большими графами, ситуация очень плохая. Большинство из них заброшены разработчиками. Почти каждый из них имеет свои большие недостатки. Расскажу только о тех, которые достойны упоминания и умеют работать с большими графами. Что касается маленьких графиков, то проблем нет. Вы можете легко найти инструмент для своей цели, и, скорее всего, он будет работать хорошо.

Графвиз

Граф транзакций Биткойн до 2011 г. Иногда трудно настроить параметры

Это инструмент командной строки старой школы с собственным языком определения графа под названием «точка». Это пакет с несколькими макетами. Для больших графов он имеет макет sfdp из семейства Force-Directed. Плюсы и минусы этого инструмента в одном: он запускается из командной строки. Это полезно для автоматизации, но сложно настроить параметры без интерактивности. Вы даже не знаете, как долго нужно ждать результата, а также не знаете, нужно ли его останавливать и перезапускать с другими параметрами.

Gephi

Изображение с сайта gephi.org137K график рекомендаций фильмов от iMDBA несколько миллионов уже слишком много для Gephi

Самый мощный инструмент визуализации графиков, который я знаю. Он имеет графический интерфейс, содержит несколько макетов и множество инструментов для анализа графиков. Существует также множество плагинов, написанных сообществом. Например, мой любимый макет «Multigravity Force-Atlas 2» или инструмент экспорта sigma.js, который создает интерактивный шаблон веб-страницы на основе вашего проекта. В Gephi пользователи могут раскрашивать узлы и ребра по их признакам.

Но разработчики отказались от Gephi. Он также имеет немного старомодный графический интерфейс и отсутствие некоторых простых функций.

igraph

График музыкальных рекомендаций Last. fm. Исходник, описание и интерактивная версия находятся здесь

Я должен отдать должное этому универсальному пакету анализа графов. Одна из самых впечатляющих визуализаций графа была сделана одним из авторов igraph.

Недостатки igraph — ужасная документация по python API, но исходники читаемы и хорошо прокомментированы.

LargeViz

Несколько десятков миллионов вершин (транзакций и адресов) в одном из крупнейших биткойн-кластеров

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

Графика

Адреса, которые могут быть взломаны в течение одной недели, и их транзакции Интуитивно понятный и красивый графический интерфейс, но очень ограниченный

Это единственный платный инструмент в этом опросе. Graphistry — это сервис, который берет ваши данные и выполняет все расчеты на своей стороне. Клиент только смотрит на красивую картинку в своем браузере. Другие функции не намного лучше, чем в Gephi, за исключением того, что Graphistry имеет разумные параметры по умолчанию, хорошую цветовую схему и немного лучшую интерактивность. Он обеспечивает только один силовой макет. Он также имеет ограничение в 800 тыс. узлов или ребер.

Встраивание графиков

Существует подход и для сумасшедших размеров. Начиная примерно с миллиона вершин, есть смысл смотреть только на плотность вершин и вообще не рисовать ребра и отдельные вершины. Просто потому, что на таком сюжете никто не в состоянии разобрать отдельные объекты. Более того, большинство алгоритмов, которые были сделаны для визуализации графов, будут работать много часов, а может и дней на таких размерах. Эту проблему можно решить, если немного изменить подход. Существует множество подходов к получению представления фиксированного размера, отражающего особенности вершин графа. После получения такого представления вам остается только уменьшить размерность до двух, чтобы получить картинку.

Node2Vec

Node2Vec + UMAP

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

VERSE

VERSE + UMAP

Расширенный алгоритм универсального графического представления. Один из лучших в моем опыте.

Свертки графа

Свертки графа + автоэнкодер. Двудольный граф.

Существует множество способов определения свертки на графе. Но на самом деле это простое «размазывание» признаков соседями вершин. Мы также можем поместить информацию о локальной топологии в функции вершин.

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

Links

Simplifying Graph Convolutional Networks
arxiv. org/pdf/1902.07153.pdf

GraphViz
graphviz.org

Gephi
gephi.org

igraph
igraph.org

BAGINVIZ
arxiv.org/abs/1602.00370
github.com/lferry007/largevis

node 2
. xgfs/node2vec-c

VERSE
tsitsul.in/publications/verse
github.com/xgfs/verse

Блокнот с упрощенным примером сверток графа
/github/blograph-graph-uffv9t.com/iggisv9t.com/iggisv9t.com/iggisv9t.com/iggisv9t.com/iggisv9t.com/iggisv9t.com/iggisv9t.com/xgfs/verse

/Universal%20Convolver%20Example.ipynb

Свертки графов
Список статей о сверточных сетях графов: github.com/thunlp/GNNPapers

Это нейронные соединения части мозга мухи с https://neuprint.janelia.org/

Статья была опубликовано около года назад. Теперь появился новый очень многообещающий инструмент для визуализации графиков, особенно больших графиков: Graphia. Он находится в активной разработке, в отличие от давно заброшенного Gephi, и работает намного быстрее. Поскольку в Gephi интегрировано множество инструментов, вы можете прочитать о них здесь: https://graphia.app/userguide.html

Недостатки простительны:

• На данный момент имеет только одну силовую раскладку и очень ограниченные возможности ее настройки.
• Параметры рендеринга не подходят для больших графиков. По крайней мере, возможность отключить отображение краев или добавить непрозрачность была бы очень полезной.
• Сейчас Graphia относительно сырая. Например, мне пришлось конвертировать форматы графиков с помощью Gephi, чтобы вставить их в Grapia, которая вылетала на тех же графиках, представленных в формате CSV. Но я уверен, что все эти мелочи скоро будут улучшены.

Преимуществ слишком много, чтобы их перечислять. Представьте себе Gephi со всеми этими инструментами анализа, но переписанный с нуля на C++, намного быстрее и в активной разработке. Для сравнения: Gephi требуется несколько часов для построения графа из 173 тысяч узлов, а Graphia — всего несколько минут.

Я считаю, что этот обзор скоро устареет, поэтому лучше проверьте текущее состояние этого приложения самостоятельно.

Должен сказать, что некоторые пункты в этой статье немного устарели:

• Gephi больше не заброшен
• Graphia все еще выглядит сырой. Это быстро, но визуализация слишком беспорядочна, и невозможно настроить представление, чтобы сделать его пригодным для использования.
• Сейчас есть несколько отличных онлайн-инструментов

Cosmograph

Cosmograph: визуальная аналитика для больших графов

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

Cosgraph.app

Сверхбыстрый инструмент с принудительно управляемой компоновкой на webgl, ядром с открытым исходным кодом и нормальными настройками по умолчанию. Легкий, красивый, минималистичный, но с рядом полезных функций. Может обрабатывать сотни тысяч вершин и ребер. Даже быстрее, чем настольные инструменты.

Изображение с сайта космографа

Retina

Retina

Веб-приложение для обмена сетевыми визуализациями

ouestware.gitlab.io

Я смог использовать Retina с примерно 10 000 вершинами, но главной особенностью этого инструмента является публикация. Разместите файл gexf или graphml где-нибудь в Интернете (они даже предоставляют инструкции) и получите инструмент анализа графов, которым можно поделиться. Нет необходимости использовать настольный инструмент для ряда наиболее частых сценариев, таких как поиск узлов, исследование соседей узлов, фильтрация по атрибутам и т. д.

График, размещенный в Интернете, загружается в Retina

Например, я нашел график взаимодействия персонажей Гарри Поттера, размещенный на Github, и теперь я могу поделиться визуализацией

Матрицы смежности

Матрицы смежности Матрицы смежности

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

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

Пример: Матричное представление графа

Рассмотрим следующий ориентированный граф G (в котором вершины заказываются как v ₁ , v ₂ , v ₃ , v ₄ , и v ₅ ), и его эквивалентное представление матрицы смежности справа:

v1 v2 v3 v4 v5 v1 0 1 0 1 1 v2 0 0 0 1 0 v3 0 0 0 0 1 v4 0 0 0 0 0 v5 0 1 0 0 0

Как видно из приведенного выше графика, если путь длиной 1 существует от одной вершины к другой (т. е. две вершины смежны), должна быть запись 1 в соответствующей позиции в матрице. Например, из вершины v1 мы можем добраться до вершин v2, v4 и v5. Следовательно, у нас есть соответствующая запись 1 в матрице в первом строку и второй, четвертый и пятый столбцы.

Обычно количество единиц в i-й строке соответствует числу ребер, выходящих из вершины v _i , и числу единиц в j-м столбце соответствует количеству ребер, входящих в вершина v _j .

Определение матрицы смежности

Матрица смежности определяется следующим образом: Пусть G — граф с «n» вершинами, которые предполагаются упорядоченными из v ₁ до v _n .
Матрица размера n x n A, в которой

а _ij = 1, если существует путь из v _i до v _j
a _ij = 0 иначе

называется матрицей смежности.

Расчет пути между вершинами

Как показано в предыдущем примере, наличие ребра между двумя вершинами v _i и v _j показана записью из 1 в i ^-м ряду и j ^-й -й столбец матрицы смежности. Этот запись представляет собой путь длиной 1 от v _i до v _j .

Чтобы вычислить путь длины 2, матрица длины 1 должна умножается сам на себя, а матрица произведения является матричным представлением путь длиной 2.

Пример: вычисление матричного представления пути длины 2

Использование матрицы из предыдущего примера и умножение сама по себе, мы получаем следующую новую матрицу:

Исходный график G:

Матричное представление пути длиной 2 v1 v2 v3 v4 v5 v1 0 1 0 1 0 v2 0 0 0 0 0 v3 0 1 0 0 0 v4 0 0 0 0 0 v5 0 0 0 1 0

Приведенная выше матрица показывает, что мы можем перейти из вершины v1 в вершину v2 или из вершины v1 в вершину v4 за два хода.

No related posts.