Лекция № 16. Маршруты, цепи и циклы.

Рисунок 5.

Рисунок 3.

Рисунок 2.

Рисунок 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.1 2.2 2.3

a. 2.5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

а) б)

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

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

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

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

Пусть G(V, Е) – неориентированный граф. Рассмотрим конечную последовательность рёбер такую, что любые два соседние ребра имеют одну общую инцидентную вершину . Эту последовательность называется маршрутом графа.

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

Любой отрезок конечного или бесконечного маршрута вида , где также является маршрутом и называется участком маршрута .

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