Содержание
На этой странице вы можете задать матрицу смежности и построить по ней граф
© Граф Online — создание и визуализация графа в два клика или по матрице смежности и поиск кратчайшего пути, поиск компоненты связности, поиск Эйлеровго цикла. Поделиться: Twitter, Facebook, В Контакте. 2015 — 2019
1. Постройте матрицы смежности и весовые матрицы для каждого графа:
2. Постройте графы, соответствующие каждой из матриц смежности:
3. Постройте графы, соответствующие каждой из весовых матриц:
4. Постройте орграф, соответствующий каждой из весовых матриц.
Первая работа по теории графов, принадлежащая известному швейцарскому математику Л. Эйлеру, появилась в 1736 г.
Вначале теория графов казалась довольно незначительным разделом математики, так как она имела дело в основном с математическими развлечениями и головоломками.
Однако дальнейшее развитие математики и особенно ее приложений дало сильный толчок развитию теории графов.
Уже в XIX столетии графы использовались при построении схем электрических цепей и молекулярных схем.
Граф — это одно из представлений связей, между объектами / событиями.
В настоящее время теория графов находит многочисленные применения в разнообразных практических вопросах: при установлении разного рода соответствий, при решении транспортных задач, задач о потоках в сеги нефтепроводов и вообще в так называемом «программировании». Теория графов теперь применяется и в таких областях, как экономика, психология и биология.
В виде графов преобразовываются электрические схемы, производственные цепочки на предприятии, план мероприятий, оптимальная логистическая доставка, связи между родственниками, друзьями и многое другое.
Графы делятся на ненаправленные, направленные, с весовыми коэффицикентами(взвешенные) и без коэффициентов.
Каждый граф имеет определенные характеристики. Основные из них это остов графа, матрица смежности, матрица инцидентности.
Остов графа — это подграф данного графа, содержащий все его вершины и являющийся деревом.
Матрица смежности графа — это квадратная матрица ( по числу вершин графа) где, каждый элемент матрицы (на пересечении i- столбца и j-ряда) есть состояния связи между вершинами i и j.
Элемент матрицы равен 1 если i-вершина графа, соединена с j-вершиной графа.
Во всех других случаях, в том числе когда i=j, значение элемента матрицы равно 0.
Это условие применимно только для ненаправленных графов и только для связей которые не начинаются и заканчиваются на одной и той же вершине ( петля)
Ненаправленный граф — граф, где не указаны направления движения связей между любыми вершинами.
Невзвешенный граф — граф, где связям между любыми вершинами не присвоено никакое значение, а показывает только лишь сам факт связи этих двух вершин
На этой странице бот строит ненаправленный граф, если для него задана матрица смежности.
Если мы не можете в уме построить матрицу смежности, то для этого есть ресурс Теория графов. Матрица смежности онлайн где можно построить такую матрицу.
Интересные особенности
В матрице смежности неориентированного графа (взвешенного или невзвешенного) не важно, есть одна очень важная особенность
Значения матрицы относительно главной диагонали — одинаковы.
Таким образом в принципе достаточно в качестве исходных данных вводить только верхнюю(диагональную) часть матрицы, но для удобства восприятия, ввод данных был сделан для полной матрицы.
Второй вывод который следует из вышесказанного следующий( и в примерах он прослеживается): Бот не проверяет симметричность-соответствие данных в позициях матрицы относительно главной диагонали.
Примеры:
Задана матрица смежности такого вида
В запросе пишем 0 0 1 0 1 0 1 0 0 0 1 1 0 1 0 0
и получаем ответ
| Заданная матрица смежности ненаправленного графа |
| Полученный граф, построенный по матрице |
 |
Матрица задана таким видом
Пишем в запросе
0 0 1 0 1 0 1 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 1 0 0 1 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0
Загрузка...
