Понятие и представление графа
Что такое граф? Граф — фундаментальное понятие дискретной математики, комбинация набора вершин и набора ребер. Чтобы лучше понять, что такое граф — представьте дорожную систему некоторой страны N.
Пусть в нашем государстве N 6 городов. Эти города связаны дорогами таким образом, как показано на схеме. 
На этой схеме изображен граф. Этот граф имеет 6 вершин и 6 ребер.
Также, дороги в нашей стране могут быть как односторонними, так и двухсторонними. В теории графов приняты следующие термины — графы с односторонними ребрами называют ориентированными, иначе — неориентированными. До этого наш граф был неориентированным, теперь — ориентированным. 
Также мы можем присвоить ребрам графа какой-либо параметр, например, стоимость проезда по дороге. Теперь наш граф стал взвешенным. 
Путём в графе называется последовательность вершин, каждая из которых соединена со следующей вершиной ребром. Граф называют связным, если между любой парой вершин существует хотя бы один путь.
Циклы в графе
Иногда бывает так, что первая вершина, с которой мы начинаем наш путь, совпадает с последней. В этом случае мы можем сказать, что граф имеет цикл. 
Так, вершины 3,5,6 связаны циклом.
Особые графы
Иногда встречаются достаточно специфические графы. В частности, мультиграфы разрешают наличие нескольких ребер между двумя вершинами. Такие ребра называют кратными. Также встречаются так называемые петли. Петля — ребро, входящее в вершину, из которой она исходит. 
Дерево
Дерево — структура данных, связный граф, не имеющий циклов. Ребра дерева неориентированы и невзвешены. 
Дерево — это связный граф без циклов, петель и кратных рёбер.
Создание графа и методы представления
Существует два способа представления графа. Первый из них — матрица смежности. Этот способ достаточно просто реализуется. Пусть у нас есть граф из N вершин, мы создаем матрицу (двумерный массив) \(N * N\), где будем хранить логические значения. Если путь из вершины i в вершину j существует, то \(graph[i][j] = true\), в противном случае — \(false\).
Реализуем следующую программу с использованием матрицы смежности: введем вершины графа и выведем матрицу смежности, где “\(+\)” — означает, что путь существует.
У матрицы смежности есть свои преимущества и недостатки. Мы можем проверить, существует ли ребро между двумя вершинами за \(0(1)\). Очевидно, что матрица занимает \(N^2\) памяти, что является неприемлемым для больших графов. В такой ситуации мы вынуждены искать оптимальное решение.
Второй способ представления графа — список смежности. Его идея заключается в хранении для каждой вершины расширяемого массива (вектора), содержащего всех её соседей.
Теперь для каждой вершины будем выводить количество вершин, смежных с ней.
Cписок смежности более оптимален по памяти и по времени, чем матрица смежности. Однако, следует учитывать особенности поставленной задачи и выбирать наиболее оптимальный вариант из предложенных.
Построение геометрических орграфов на основании матриц
Нарисовать на плоскости орграф G = ( X, U ), единственный с точностью до изоморфизма, имеющий заданную матрицу В своей матрицей смежности. Найти матрицу инцидентности орграфа G.
Решение. Заданная матрица смежности В имеет 4 строки и 4 столбца, следовательно, орграф имеет 4 вершины. Обозначим их соответственно ,, , . Матрицу В перепишем в виде
Построим на плоскости 4 точки и обозначим их ,, , .
Рис. 22. Изоморфный орграф G = ( X, U ).
Так как , то при вершине нет петель, , значит из вершины исходят 2 стрелки к вершине . Рассуждая таким же образом, построим геометрический орграф, изоморфный орграфу G = ( X, U ), для которого матрица В является матрицей смежности ( рис. 22 ).
Теперь запишем матрицу инцидентности С для орграфа G.
Построенный орграф G = ( X, U ) имеет 4 вершины и 12 дуг, т.е. Х=<. >,
Матрица инцидентности орграфа G будет иметь 4 строки и 12 столбцов
Петле соответствует нулевой столбец. Матрица инцидентности только указывает на наличие петель в орграфе, но не указывает, каким вершинам эти петли инцидентны.
3. Задана симметрическая матрица А неотрицательных целых чисел.
1. Нарисовать на плоскости граф (единственный с точностью до изоморфа), имеющий заданную матрицу А своей матрицей смежности. Найти матрицу инцидентности графа G.
2. Нарисовать на плоскости орграф (единственный с точностью до изоморфизма), имеющий заданную матрицу А свое матрицей смежности. Найти матрицу инцидентности орграфа G.
Решение1. Напомним, что матрицей смежности графа с множеством вершин называется матрица размера , в которой элемент равен числу ребер в G, соединяющих с . Матрица смежности графа G является симметрической, то есть
Построим граф по заданной матрице смежности.
Поскольку данная матрица является симметрической матрицей четвертого порядка с неотрицательными элементами, то ей соответствует неориентированный граф с четырьмя вершинами. Расположив вершины на плоскости произвольным образом (рис. 3), соединяем их с учетом кратности ребер.
Теперь найдем матрицу инцидентности графа G =(X,U).
Напомним определение матрицы инцидентности графа G=(X,U) с множеством вершин и множеством ребер Так называется матрица размера , у которой
2. Заданная матрица А имеет 4 строки и 4 столбца, следовательно орграф имеет 4 вершины. Обозначим их соответственно а матрицу представим в виде
На плоскости строим 4 точки. Обозначим их через
Рис. 4. Изоморфный орграф G=(X,U).
Так как то при вершине имеется петля; значит, из вершины выходят две стрелки к вершине и т.д. (рис.4).
Теперь запишем матрицу инцидентности С для орграфа G.
Построим орграф G=(X,U) имеет 4 вершины и 17 дуг, т.е.
Матрица инцидентности орграфа G будет иметь 4 строки и 17 столбцов
4. Заданная формула От формулы перейти к эквивалентной ей формуле так, чтобы формула не содержала связок «» и «». Исходя из истинностных таблиц, доказать, что формулы и равно сильны (логически эквивалентны). Для формулы СКНФ и СДНФ.
Решение. Как известно, все формулы логики высказываний можно записать при помощи пропозициональных связок : т.е. пропозициональные связки могут быть определены в терминах связок Можно доказать, что
Используя равенства (1) – (3) и основные законы
21 – 30. Задана симметрическая матрица A неотрицательных целых чисел.
1. Нарисовать на плоскости граф G=(X,U) (единственный с точностью до изоморфизма), имеющий заданную матрицу А своей матрицей смежности. Найти матрицу инцидентности
2. Нарисовать на плоскости орграф G=(X,U) (единственный с точностью до изоморфизма)? Имеющий заданную матрицу А своей матрицей смежности. Найти матриц инцидентности
Теория графов. Часть третья (Представление графа с помощью матриц смежности, инцидентности и списков смежности)
Итак, мы умеем задавать граф графическим способом. Но есть еще два способа как можно задавать граф, а точнее представлять его. Для экономии памяти в компьютере граф можно представлять с помощью матриц или с помощью списков.
Матрица является удобной для представления плотных графов, в которых число ребер близко к максимально возможному числу ребер (у полного графа).
Другой способ называется списком. Данный способ больше подходит для более разреженных графов, в котором число ребер намного меньше максимально возможного числа ребер (у полного графа).
Перед чтением материала рекомендуется ознакомится с предыдущей статьей, о смежности и инцидентности, где данные определения подробно разбираются.
Матрица смежности
Но тем кто знает, но чуть забыл, что такое смежность есть краткое определение.
Смежность – понятие, используемое только в отношении двух ребер или в отношении двух вершин: два ребра инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными.
Матрица (назовем ее L) состоит из n строк и n столбцов и поэтому занимает n^2 места.
Каждая ячейка матрицы равна либо 1, либо 0;
Ячейка в позиции L (i, j) равна 1 тогда и только тогда, когда существует ребро (E) между вершинами (V) i и j. Если у нас положение (j, i), то мы также сможем использовать данное правило. Из этого следует, что число единиц в матрице равно удвоенному числу ребер в графе. (если граф неориентированный). Если ребра между вершинами i и j не существует, то ставится 0.
Для практического примера возьмем самый обыкновенный неориентированный граф:
А теперь представим его в виде матрицы:
Ячейки, расположенные на главной диагонали всегда равны нулю, потому что ни у одной вершины нет ребра, которое и начинается, и заканчивается в ней только если мы не используем петли. То есть наша матрица симметрична относительно главной диагонали. Благодаря этому мы можем уменьшить объем памяти, который нам нужен для хранения.
С одной стороны объем памяти будет:
Но используя вышеописанный подход получается:
Потому что нижнюю часть матрицы мы можем создать из верхней половины матрицы. Только при условии того, что у нас главная диагональ должна быть пустой, потому что при наличии петель данное правило не работает.
Если граф неориентированный, то, когда мы просуммируем строку или столбец мы узнаем степень рассматриваемой нами вершины.
Если мы используем ориентированный граф, то кое-что меняется.
Здесь отсутствует дублирование между вершинами, так как если вершина 1 соединена с вершиной 2, наоборот соединена она не может быть, так у нас есть направление у ребра.
Возьмем в этот раз ориентированный граф и сделаем матрицу смежности для него:
Если мы работаем со строкой матрицы, то мы имеем элемент из которого выходит ребро, в нашем случаи вершина 1 входит в вершину 2 и 8. Когда мы работаем со столбцом то мы рассматриваем те ребра, которые входят в данную вершину. В вершину 1 ничего не входит, значит матрица верна.
Если бы на главной диагонали была бы 1, то есть в графе присутствовала петля, то мы бы работали уже не с простым графом, с каким мы работали до сих пор.
Используя петли мы должны запомнить, что в неориентированном графе петля учитывается дважды, а в ориентированном — единожды.
Матрица инцидентности
Инцидентность – понятие, используемое только в отношении ребра и вершины: две вершины (или два ребра) инцидентными быть не могут.
Матрица (назовем ее I) состоит из n строк которое равно числу вершин графа, и m столбцов, которое равно числу ребер. Таким образом полная матрица имеет размерность n x m. То есть она может быть, как квадратной, так и отличной от нее.
Ячейка в позиции I (i, j) равна 1 тогда, когда вершина инцидентна ребру иначе мы записываем в ячейку 0, такой вариант представления верен для неориентированного графа.
Сразу же иллюстрируем данное правило:
Сумма элементов i-ой строки равна степени вершины.
При ориентированным графе, ячейка I (i, j) равна 1, если вершина V (i) начало дуги E(j) и ячейка I (i, j) равна -1 если вершина V (i) конец дуги E (j), иначе ставится 0.
Одной из особенностей данной матрицы является то, что в столбце может быть только две ненулевых ячейки. Так как у ребра два конца.
При суммировании строки, ячейки со значением -1, могут складываться только с ячейками, также имеющими значение -1, то же касается и 1, мы можем узнать степень входа и степень выхода из вершины. Допустим при сложении первой вершины, мы узнаем, что из нее исходит 1 ребро и входят два других ребра. Это является еще одной особенностью (при том очень удобной) данной матрицы.
Список смежности (инцидентности)
Список смежности подразумевает под собой, то что мы работаем с некоторым списком (массивом). В нем указаны вершины нашего графа. И каждый из них имеет ссылку на смежные с ним вершины.
В виде списка это будет выглядеть так:
Неважно в каком порядке вы расположите ссылку так как вы рассматриваете смежность относительно первой ячейки, все остальные ссылки указывают лишь на связь с ней, а не между собой.
Так как здесь рассматривается смежность, то здесь не обойдется без дублирования вершин. Поэтому сумма длин всех списков считается как:
Когда мы работаем с ориентированным графом, то замечаем, что объем задействованной памяти будет меньше, чем при неориентированном (из-за отсутствия дублирования).
Сумма длин всех списков:
Со списком инцидентности все просто. Вместо вершин в список (массив) вы вставляете рёбра и потом делаете ссылки на те вершины, с которыми он связан.
К недостатку списка смежности (инцидентности) относится то что сложно определить наличие конкретного ребра (требуется поиск по списку). А если у вас большой список, то удачи вам и творческих успехов! Поэтому, чтобы работать максимальной отдачей в графе должно быть мало рёбер.
Взвешенность графа
Взвешенный граф — это граф, в котором вместо 1 обозначающее наличие связи между вершинами или связи между вершиной и ребром, хранится вес ребра, то есть определённое число с которым мы будем проводить различные действия.
К примеру, возьмем граф с весами на ребрах:
И сделаем матрицу смежности:
В ячейках просто указываем веса ребра, а в местах где отсутствует связь пишем 0 или -∞.
Более подробно данное определение будет рассмотрено при нахождении поиска кратчайшего пути в графе.
Итак, мы завершили разбор представления графа с помощью матрицы смежности и инцидентности и списка смежности (инцидентности). Это самые известные способы представления графа. В дальнейшем мы будем рассматривать и другие матрицы, и списки, которые в свою очередь будут удобны для представления графа с определёнными особенностями.
Построить ненаправленный граф по матрице
Первая работа по теории графов, принадлежащая известному швейцарскому математику Л. Эйлеру, появилась в 1736 г.
Вначале теория графов казалась довольно незначительным разделом математики, так как она имела дело в основном с математическими развлечениями и головоломками.
Однако дальнейшее развитие математики и особенно ее приложений дало сильный толчок развитию теории графов.
Уже в XIX столетии графы использовались при построении схем электрических цепей и молекулярных схем.
Граф — это одно из представлений связей, между объектами / событиями.
В настоящее время теория графов находит многочисленные применения в разнообразных практических вопросах: при установлении разного рода соответствий, при решении транспортных задач, задач о потоках в сети нефтепроводов и вообще в так называемом «программировании». Теория графов теперь применяется и в таких областях, как экономика, психология и биология.
В виде графов преобразовываются электрические схемы, производственные цепочки на предприятии, план мероприятий, оптимальная логистическая доставка, связи между родственниками, друзьями и многое другое.
Графы делятся на н енаправленные, направленные, с весовыми коэффициентами(взвешенные) и без коэффициентов.
Каждый граф имеет определенные характеристики. Основные из них это остов графа, матрица смежности, матрица инцидентности.
Остов графа — это подграф данного графа, содержащий все его вершины и являющийся деревом.
Матрица смежности графа — это квадратная матрица ( по числу вершин графа) где, каждый элемент матрицы (на пересечении i- столбца и j-ряда) есть состояния связи между вершинами i и j.
Элемент матрицы равен 1 если i-вершина графа, соединена с j-вершиной графа.
Во всех других случаях, в том числе когда i=j, значение элемента матрицы равно 0.
Это условие применимо только для ненаправленных графов и только для связей которые не начинаются и заканчиваются на одной и той же вершине ( петля)
Ненаправленный граф — граф, где не указаны направления движения связей между любыми вершинами.
Невзвешенный граф — граф, где связям между любыми вершинами не присвоено никакое значение, а показывает только лишь сам факт связи этих двух вершин
На этой странице бот строит ненаправленный граф, если для него задана матрица смежности.
Если мы не можете в уме построить матрицу смежности, то для этого есть ресурс Теория графов. Матрица смежности онлайн где можно построить такую матрицу.
Интересные особенности
В матрице смежности неориентированного графа (взвешенного или невзвешенного) не важно, есть одна очень важная особенность
Значения матрицы относительно главной диагонали — одинаковы.
Таким образом в принципе достаточно в качестве исходных данных вводить только верхнюю(диагональную) часть матрицы, но для удобства восприятия, ввод данных был сделан для полной матрицы.
Второй вывод который следует из вышесказанного следующий( и в примерах он прослеживается): Бот не проверяет симметричность-соответствие данных в позициях матрицы относительно главной диагонали.