Определение 1. Пусть G – неориентированный граф. Пусть Mc – квадратная матрица, строки и столбцы которой обозначены вершинами неориентированного графа G. Элемент i-ой строки и j-гo столбца матрицы Mc, обозначаемый cij, равен единице, если имеется ребро из i-ой вершины в j-ую вершину, и равен нулю в противном случае. Матрица Mc называется матрицей смежности графа G.
Заметим, что для сокращения записи обозначения строк и столбцов в матрицах смежности можно опускать, но рекомендуется их оставлять особенно в матрицах больших размерностей.
Говоря о свойствах матрицы смежности неориентированного графа, необходимо отметить, что она не только квадратная, но и всегда симметрична относительно главной диагонали.
Для демонстрации примеров введём следующие графы (см. два рис. ниже).
Этот неориентированный граф G1 состоит из множества вершин V(G1), содержащего 6 элементов, и множества рёбер E(G1), содержащего 6 элементов: V(G1) = {a, b, c, d, e, f}, E(G1) = {{a, b}, {a, c}, {b, d}, {c, d}, {с, e}, {d, f}}.
Неориентированный граф G2 состоит из множества вершин V(G2), содержащего 6 элементов, и множества рёбер E(G2), содержащего 5 элементов: V(G2) = {a, b, c, d, e, f}, E(G2) = {{a, c}, {b, e}, {c, d}, {d, e}, {d, f}}.
Пример 1. Для неориентированных графов G1 и G2, показанных на рис. выше, определим матрицы смежности.
Неориентированный граф G1 состоит из 6 вершин, поэтому его матрица смежности имеет размерность 6 на 6:
Неориентированный граф G2 также состоит из 6 вершин, поэтому его матрица смежности также имеет размерность 6 на 6:
Определение 2. Пусть G – неориентированный граф. Списком вершин (списком смежности) неориентированного графа называется таблица, в первом столбце которой указаны вершины графа, во втором столбце – соответствующие им смежные вершины. Таким образом, можно считать, что список вершин получен из матрицы смежности неориентированного графа путём замены единиц в каждой строке (столбце) на обозначение соответствующей строки (столбца), а нули отброшены.
Пример 2. Для неориентированных графов G1 и G2, показанных на рис. выше, определим списки вершин. Неориентированный граф G1 состоит из 6 вершин, поэтому список вершин будет состоять из 6 строк (см. табл. далее).
Неориентированный граф G2 также состоит из 6 вершин, поэтому его список вершин также будет состоять из 6 строк (табл. ниже).
Определение 3. Пусть G – неориентированный граф. Списочной структурой (списком смежности) неориентированного графа называется массив указателей на списки смежных вершин, другими словами, каждый элемент списка смежности представляется структурой с двумя полями: номером вершины и указателем на смежные вершины.
Пример 3. Для неориентированных графов G1и G2, показанных на рис. выше, изобразим списочную структуру. Неориентированный граф G1 состоит из 6 вершин, поэтому списочная структура (см. рис. далее) будет состоять из 6 строк. Введём обозначение вершин графа G1 таким образом, чтобы каждой вершине присвоить номер: вершине a присвоим номер 1, вершине b – 2, вершине с – 3, вершине d – 4, вершине e – 5, вершине f – 6.
Неориентированный граф G2 также состоит из 6 вершин, поэтому его списочная структура (см. рис. ниже) также будет состоять из 6 строк (более того, также введём номерное обозначение: вершине a присвоим номер 1, вершине b – 2, вершине с – 3, вершине d – 4, вершине e – 5, вершине f – 6).
Определение 4. Пусть G – неориентированный граф. Пусть Mи − матрица, строки которой обозначены вершинами графа, а столбцы – рёбрами графа. Будем считать, что вершины и рёбра неориентированного графа пронумерованы. Элемент i-ой строки и j-гo столбца матрицы Mи, обозначаемый Mij, равен единице, если i-ая вершина инцидентна j-ому ребру, и равен нулю в противном случае. Построенная таким образом матрица Mи называется матрицей инцидентности графа G.
Замечание. Поскольку каждая единица в строке матрицы инцидентности представляет инцидентность этой вершины соответствующему ребру, то степень каждой вершины графа равна сумме элементов строки матрицы инцидентности, а в каждом столбце имеются две единицы, так как каждое ребро инцидентно двум вершинам.
Заметим также, что если имеется неориентированный граф с петлями, то это сразу можно определить по виду матрицы инцидентности: соответствующий столбец содержит только одну единицу. При этом заметим, что в матрице инцидентности для неориентированного графа с петлями сумма элементов строки, соответствующей некоторой вершине, не представляет собой степень вершины, если в ней имеются петли.
Пример 4. Для неориентированных графов G1 и G2, показанных на рис. выше, определим матрицы инцидентности. Неориентированный граф G1 состоит из 6 вершин и 6 рёбер, поэтому его матрица инцидентности имеет размерность 6 на 6:
Неориентированный граф G2 состоит из 6 вершин и 5 рёбер, поэтому его матрица инцидентности имеет размерность 6 на 5:
Определение 5. Пусть G – неориентированный граф. Списком рёбер (списком инцидентности) неориентированного графа называется таблица, в первой строке которой указаны рёбра графа, во второй строке – инцидентные этим рёбрам вершины. Таким образом, можно считать, что список рёбер получен из матрицы инцидентности путём замены единиц в каждом столбце на обозначение соответствующих вершин, а нули отброшены.
Пример 5. Для неориентированных графов G1 и G2 , показанных на рис. выше, определим списки рёбер.
Неориентированный граф G1 состоит из шести рёбер, поэтому список рёбер будет состоять из шести столбцов (см. табл. далее).
Неориентированный граф G2 состоит из пяти рёбер, поэтому его список рёбер будет состоять из пяти столбцов (см. табл. далее).
Определение 6. Пусть G – неориентированный граф. Пусть MK– квадратная матрица, строки и столбцы которой обозначены вершинами неориентированного графа G. Элементы матрицы MK, обозначаемые kij, расположенные на главной диагонали, т.е. элементы i-ой строки и i-гo столбца, равны степени i-ой вершины, элементы i-ой строки и j-гo столбца (при i не равном j) равны -1, если имеется ребро из i-ой вершины в j-ую вершину, и равен нулю в противном случае. Матрица MK называется матрицей Кирхгофа неориентированного графа G.
Замечание. Матрица Кирхгофа неориентированного графа G связана с его матрицей смежности следующей зависимостью: MK = D – Mс, где D представляет собой матрицу, диагональные элементы которой равны степеням соответствующих вершин, остальные элементы нулевые.
Пример 6. Для неориентированных графов G1и G2, показанных на рис. выше, определим матрицы Кирхгофа.
Неориентированный граф G1 состоит из шести вершин, поэтому его матрица Кирхгофа имеет размерность 6 на 6.
На диагонали матрицы Кирхгофа располагаем числа, соответствующие степеням вершин графа: вершине a инцидентно 2 ребра, вершине b – 2 ребра, c – 3, d – 3, e – 1, f – 1.
Далее матрица заполняется в соответствии со смежностью вершин: вершины a и c – смежные – в соответствующие клетки матрицы ставим «-1», смежные вершины в графе a и b, c и d, d и f, b и d, e и c.
Матрица Кирхгофа неориентированного графа G1 имеет вид:
Проверим выполнимость замечания о связи матрицы Кирхгофа и матрицы смежности следующими вычислениями:
Как видно из выражений выше, левая и правая часть совпадают, следовательно, показана связь между матрицами смежности и Кирхгофа.
Неориентированный граф G2 также состоит из шести вершин, поэтому его матрица Кирхгофа также имеет размерность 6 на 6.
На диагонали матрицы Кирхгофа располагаем числа, соответствующие степеням вершин графа: вершине a инцидентно 1 ребро, вершине b – 1 ребро, c – 2, d – 3, e – 2, f – 1.
Далее матрица заполняется в соответствии со смежностью вершин: вершины a и c – смежные – в соответствующие клетки матрицы ставим «-1», смежные вершины в графе c и d, d и e, b и e, d и f.
Матрица Кирхгофа неориентированного графа G2 имеет следующий вид:
В качестве Упражнения 1 предлагается записать все выше определённые способы задания неориентированных графов для следующих вариантов размеченных неориентированных графов по ссылке (там имеются графы, представляющие собой буквы и цифры азбуки семафорного телеграфа, разработанной Клодом Шаппом):
В качестве дополнительного Упражнения 2 предлагается записать все выше определённые способы задания неориентированных графов для следующих вариантов неографов:
