РАЗДЕЛ IV. ТЕОРИЯ ГРАФОВ.

Лекция № 14. Графы: основные понятия и операции.

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

1. Графы, их вершины, рёбра и дуги. Изображение графов.

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

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

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

В множестве V могут встречаться одинаковые элементы, ребра, соединяющие одинаковые элементы называются петлями (на рисунке 1.4 при вершине 5 имеется петля). Одинаковые пары в множестве E называются кратными (или параллельными) ребрами. Количество одинаковых пар (v, w) в E называется кратностьюребра (v, w). Например, на рисунке 1.1 все рёбра имеют кратность 1, а на рисунке 1.2 есть два ребра, соединяющих одни и те же вершины 1 и 4, следовательно, их кратность равна двум.

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

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

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

Ниже, на рисунке 1.1 изображен граф, на рисунке 1.2 мультиграф, на рисунке 1.4 – псевдограф.

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

Рисунок 1.

1.1 1.2 1.3

1.4 1.5

Замечание 1. Слово “линия”, которое мы используем, подразумевает несущественность того, какая конкретно линия используется для соединения двух вершин графа, то есть её геометрические характеристики не имеют значения.

Замечание 2. Граф можно определить, также как совокупность двух множеств и , между элементами которых установлено отношение инцидентности, при котором каждый элемент инцидентен ровно двум элементам .

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

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

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

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

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

На рисунке 1.5 все вершины, кроме вершины 1, являются висячими. На рисунке 1.3 вершина 4 является изолированной. Если граф состоит только из таких вершин, его называют пустым. В некоторых случаях пустым называют граф, не имеющей ни одной вершины.

Рисунок 2.

2.1 2.2 2.3

a. 2.5

На рисунке 2 представлены различные типы ориентированных графов.

Заметим, что каждому неориентированному графу можно поставить в соответствие ориентированный граф с тем же множеством вершин, в котором каждое ребро заменено двумя противоположными рёбрами, инцидентными тем же вершинам. Такое соответствие называется каноническим.

1. Матрица инцидентности и список рёбер. Матрица смежности графа.

Обычно рассматриваемые графы конечны, то есть, конечны множества их элементов – вершин и рёбер. Поэтому в дальнейшем конечность графов не будет оговариваться, тем более, что важнейшие понятия и результаты, приводимые ниже относятся к произвольным графам.

Задать граф – значит, описать множества его вершин и рёбер и задать между ними отношение инцидентности. Когда граф конечный, для описания его вершин и рёбер достаточно их занумеровать. Пусть - вершины графа, а - его рёбра. Отношение инцидентности можно определить матрицей размерности . Столбцы этой матрицы будут соответствовать вершинам графа, а строки – его рёбрам. Если ребро инцидентно вершине , то , в противном случае - . Такая матрица называется матрицей инцидентности неориентированного графа, поскольку по способу её задания невозможно различить начало и конец каждого ребра.

Пример 1. Составить матрицу инцидентности неориентированного графа, изображённого на рисунке 3.

Рисунок 3.

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

Для ориентированного графа матрица инцидентности составляется иначе. Это матрица размерности .

Если вершина - начало ребра , то . Если вершина - конец ребра , то . Если вершине инцидентна петля , то , где любое число, кроме чисел (обычно берут 2). В любом противном случае - .

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

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

Ещё проще задавать граф с помощью таблицы рёбер. Она состоит из двух столбцов; в левых содержатся названия рёбер, а в правых – инцидентные им вершины (для ориентированных графов обязательно сначала указывается начало ребра, потом конец). Ниже приведены таблицы рёбер для графов из примеров 1 и 2.

Для примера 1:

Для примера 2:

Очевидно, по списку рёбер можно построить его таблицу инцидентности. Действительно, каждая строка этого списка соответствует строке матрицы с тем же номером; аналогично можно выполнить обратную процедуру.

Ещё одним способом представления графа является построение для него матрицы смежности. Это квадратная матрица , в которой количество строк и столбцов равно количеству вершин графа. Для неориентированного графа эта матрица определяется следующим образом. Если вершины и являются смежными, то есть если выполняется , то . В противном случае, . Для графа из примера 1 таблица смежности имеет вид:

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

Матрица смежности ориентированного графа отличается только тем, что в том и только в том случае, когда в паре смежных вершин и вершина является началом, а вершина - концом ребра. Для графа из примера 2 матрица смежности выглядит следующим образом:

Очевидно, что вся информация об ориентированном графе, порождающем некоторую матрицу смежности, содержится в верхнем (относительно главной диагонали) её треугольнике.

Ориентированный граф с симметричной матрицей смежности канонически соответствует неориентированному графу, имеющему ту же таблицу смежности (но не наоборот).

1. Идентификация графов, заданных своими представлениями.

Итак, граф может быть представлен различными способами. Он может быть задан рисунком, матрицей инцидентности, списком рёбер или матрицей смежности. Вид чертежа зависит от формы линий и взаимного расположения вершин. Иногда, даже для пары достаточно простых графов, непонятно, одинаковы ли они (см. рисунок 5 “а” и “б”). Вид матриц, также как списков рёбер зависит от нумерации вершин и рёбер графа. В связи с этим возникает весьма существенный вопрос о том, как определять равенство графов.

Рисунок 5.

а) б)

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

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

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