Матрицы графов

Методические указания к проведению лекционного занятия

Тема № 9.8. Элементы теории графов

План:

1. Основные понятия и определения

2. Матрицы графов

3. Достижимость и связность

4. Эйлеровы и гамильтоновы графы.

5. Деревья и циклы

Основные понятия и определения

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

При этом элементы множества V называются вершинами графа, а элементы множества Х – ребрами.

В множестве V могут встречаться одинаковые элементы, ребра, соединяющие одинаковые элементы называются петлями. Одинаковые пары в множестве Х называются кратными (или параллельными) ребрами. Количество одинаковых пар

(v, w) в Х называется кратностью ребра (v, w).

Множество V и набор Х определяют граф с кратными ребрами – псевдограф.

G = (V, X)

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

Если в наборе Х ни одна пара не встречается более одного раза, то мультиграф называется графом.

Если пары в наборе Х являются упорядочными, то граф называется ориентированным или орграфом.

Графу соответствует геометрическая конфигурация. Вершины обозначаются точками (кружочками), а ребра – линиями, соединяющими соответствующие вершины.

Определение. Если х = { v, w } – ребро графа, то вершины v, w называются концами ребра х.

Если х = (v, w) – дуга орграфа, то вершина v – начало, а вершина w – конец дуги х.

Определение. Вершины v, w графа G = (V, X) называются смежными, если { v,w }ÎX. Два ребра называются смежными, если они имеют общюю вершину.

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

Определение.Графы G₁(V₁, X₁) и G₂(V₂, X₂) называются изоморфмными, если существует взаимно однозначное отображение j: V₁ ® V₂, сохраняющее смежность.

Определение. Маршрутом (путем) для графа G(V, X) называется последовательность v₁x₁v₂x₂v₃…x_kv_k+1. Маршрут называется замкнутым, если его начальная и конечная точки совпадают. Число ребер (дуг) маршрута (пути) графа называется длиной маршрута (пути).

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

Определение. Замкнутый маршрут (путь) называется циклом(контуром). Цикл, в котором все вершины попарно различны, называется простым циклом.

Матрицы графов

Пусть D = (V, X) – орграф, где V = {v₁, …, v_n}, X = {x₁, …, x_m}.

Определение. Матрицей смежности орграфа D называется квадратичная матрица A(D) = [a_ij] порядка п, у которой

Определение. Если вершина v является концом ребра х, то говорят, что v и х – инцидентны.

Определение. Матрицей инцидентности орграфа D называется матрица размерности п ´ т B(D) = [b_ij], у которой

Пример. Записать матрицы смежности и инцидентности для графа, изображенного на рисунке.

x₁

v₁ x₄ v₂

x₂

x₃

v₃

Составим матрицу смежности:

Т.е. - матрица смежности.

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

Т.е.

Если граф имеет кратные дуги (ребра), то в матрице смежности принимается a_ij=k, где k – кратность дуги (ребра).

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

Пример. Задана симметрическая матрица Q неотрицательных чисел. Нарисовать на плоскости граф G(V, X), имеющий заданную матицу Q своей матрицей смежности. Найти матрицу инциндентности R графа G. Нарисованть также орграф , имеющий матрицу смежности Q, определить его матрицу инциндентности С.

x₄

x₃

v₂

x₂ x₅

x₆

x₁ v₁ v₃ x₇ x₈

x₁₀

x₁₁ x₉

v₄

Составим матрицу инциндентности:

Итого:

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

x₄

x₅

v₂

x₂ x₇

х₃ x₆

x₁ v₁ х₈ v₃ x₁₀ x₁₁

х₉

х₁₇ х₁₅ x₁₄

x₁₆ х₁₃ x₁₂

v₄

Составим матрицу инциндентности для ориетированного графа.

Элемент матрицы равен 1, если точка является концом дуги, -1 – если началом дуги, если дуга является петлей, элемент матрицы запишем как ±1.

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