3. Способы задания графов

Один из способов задания графа уже рассмотрен – это геометрическое изображение, т.е. диаграмма.

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

0. Матрица инцидентности графа.

Пусть задан граф G(V, X), где V ={v₁, v₂, …, v_n}, X = {x₁, x₂,…, x_m}.

Матрицей инцидентности графа G(V, X) называется матрица размера m n, элементы которой определяются следующим образом:

В любой строке матрицы инцидентности два или один элемент не равны нулю, т.к. каждое ребро соединяет две вершины, а если ребро – петля, то вершину саму с собой.

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

Составим матрицу инцидентности для графа 13.1. Это матрица размера 7 7:

В первом и четвертом столбцах по одной единице, следовательно первая и четвертая вершины – висячие; в седьмом столбце все элементы равны нулю, значит седьмая вершина изолированная.

В третьей строке только один элемент не равен нулю, следовательно третье ребро- петля.

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

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

Пусть задан граф G(V, X), где V ={v₁, v₂, …, v_n}, X = {x₁, x₂,…, x_m}.

Матрицей смежности графа G(V, X) называется квадратная матрица n n, элементы которой определяются следующим образом:

k – количество ребер, соединяющих вершины v_i и v_j .

Составим матрицу смежности для графа 13.1. Это квадратная матрица размера 7 7:

Матрица смежности неориентированного графа симметрична относительно главной диагонали.

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

Сумма элементов верхнего или нижнего треугольника вместе с главной диагональю равна количеству ребер в графе. Для нашего графа сумма равна (учитывая только элементы не равные нулю): 1+1+1+2+1+1=7.

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

4. Маршруты в неориентированном графе

Определение: Маршрутом , соединяющий вершины v₁ и v_k+1 , называется последовательность v₁x₁v₂x₂…v_kx_kv_k+1 , где k 1, v_i  V, x_i X, ребро x_i соединяет вершины v_i с вершиной v_i+1 . Вершина v₁ (v _нач)– начало маршрута (начальная вершина), v_k+1 (v _кон)– конец маршрута (конечная вершина).

Для графа 13.1 построим маршрут, соединяющий вершину v₁ с вершиной v₅ :

v₁x₁v₃x₃v₃v₂x₅v₆x₇v₅ .

Допускается краткая запись маршрута. В том случае, если в маршруте нет кратных ребер, то составляют последовательность только из вершин.

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

Перепишем наш маршрут, использую комбинированную запись: v₁v₃v₃v₂v₆x₇v₅ . В последовательность включено только кратное ребро x₇ .

Длиной маршрута l называется количество ребер в нем.

В нашем маршруте 5 ребер, значит его длина l =5.

Познакомимся с видами маршрутов.

Если v_нач = v_кон , то маршрут называется замкнутым.

Если v_нач  v_кон , то маршрут называется незамкнутым.

Виды незамкнутых маршрутов:

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

Цепь, в которой все вершины попарно различны называется простой цепью.

Виды замкнутых маршрутов:

Замкнутый маршрут, в котором все ребра попарно различны называется циклом.

Цикл, в котором все вершины попарно различны называется простым циклом.

Заметим, что петля или кратное ребро являются простыми циклами.

Составим различные маршруты для приведенного ниже графа на рисунке 13.5.

Рис. 13.5.

Маршрут v₁v₂v₃v₄ – простая цепь.

Маршрут v₂v₄v₅v₆v₆v₄ – цепь, не являющаяся простой.

Маршрут v₃v₄v₅v₆v₅ – замкнутый маршрут.

Маршрут v₃v₂v₄v₅v₆v₄v₂v₃ – цикл, не являющийся простым.

Маршрут v₃v₂v₄v₃ – простой цикл.