Графы и матрицы, связанные с графами

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Контрольная работа

Дискретная математика

Графы и матрицы, связанные с графами

1. Теоретическая часть

Графы

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

Пусть V - произвольное множество, V2 - множество всех его двухэлементных подмножеств, т.е. множество неупорядоченных пар {а, b}, где а, b V. Пара (V, E), где Е - произвольное подмножество V2, называется графом (неориентированным графом). При этом элементы множества V называются вершинами графа, элементы множества E - ребрами. Множества вершин и ребер графа G обозначаются символами V(G) и E(G) соответственно. Вершины и ребра графа называются его элементами.

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

Говорят, что две вершины u и v смежны, если множество {u, v} является ребром, и не смежны в противном случае. Если е = {u, v} - ребро, то вершины u и v называют его концами. В этом случае также говорят, что ребро е соединяет вершины u и v. Такое ребро обозначается символом uv .

Два ребра называются смежными, если они имеют общий конец.

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

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

Это (5, 6)-граф, V(G) = {1, 2, 3, 4, 5}, E(G) = {{1, 2}, {1, 5}, {2,3}, {2, 4}, {2, 5}, {4, 5}}. Вершины 1 и 2 смежны, а 1 и 3 не смежны. Вершина 1 и ребро {1, 2} инцидентны. Иногда в графах допускается наличие петель, т.е. ребер {а, а} (рис. 2), и кратных ребер, т.е. ребро {а, b} учитывается несколько раз (рис. 3). Мы будем рассматривать графы без петель и кратных ребер.

Ориентированный граф - это пара (V, А), где V - множество вершин, А - множество ориентированных ребер (или дуг), т.е. упорядоченных пар (u, v), где u, v V. При этом и называется началом дуги, v - концом. На рисунке дуги отмечаются стрелками, указывающими направление от начала к концу (рис. 4).

Графы специального вида

Приведем примеры некоторых графов специального вида.

Граф G называется полным, если любые две его вершины смежны, т.е.

E(G) = (V(G))(2)

Полный граф порядка п обозначается символом Кп, в нем ребер. На рис. 5 изображены графы Кп, .

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

Ниже неоднократно используются термины “разбиение” и “покрытие”. Набор подмножеств множества S называется покрытием множества S, если объединение этих множеств совпадает с S. Покрытие называется разбиением, если никакие два из входящих в него множеств не пересекаются.

Граф называется двудольным, если существует такое разбиение множества его вершин на две части (доли), что концы каждого ребра принадлежат разным частям. Если при этом любые две вершины, входящие в разные доли, смежны, то граф называется полным двудольным. Полный двудольный граф, доли которого состоят из p и из q вершин обозначается символом при р = 1 получаем звезду . На рис. 7 изображены звезда и полный двудольный граф .

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

Пути в графах

Чередующаяся последовательность

вершин и ребер графа, такая что

(i = 1, 2, …, l),

называется путем, соединяющим вершины и (или (, )-путем). Очевидно, что путь можно задать последовательностью

его вершин, а также последовательностью его ребер

.

Граф называется связным, если любые две несовпадающие вершины в нем соединены маршрутом.

Путь называется простым, если все его вершины, кроме, может быть, крайних, различны. Путь называется цепью, если все его ребра различны, и простой цепью, если все его вершины различны. Путь (*) называется циклическим, если . Циклическая цепь называется циклом, а циклическая простой путь - простым циклом. Простую цепь, имеющую п вершин, будем обозначать Cn, простой цикл - Zn (рис.8).

Число l ребер в пути (2.1) называется его длиной.

Деревом называется связанный граф без циклов. Лес - произвольный граф без циклов.

Фундаментальные циклы и разрезы

Остовом связного графа G мы называем подграф G', содержащий все вершины графа G и являющийся деревом.

Определение 1. Пусть Т -- остов связного графа G. Тогда ребра, принадлежащие остову, называются ветвями, а не принадлежащие -- хордами.

Пусть G -- связный граф, а Т -- некоторый его фиксированный остов. Обозначим ветви графа b1,b2,…,bn-1, а хорды c1,c2,cm-n+1, где m -- число ребер, an -- число вершин графа G. Если к остову прибавить одну из хорд сi, то получится ровно один цикл, который мы обозначим Сi.

Определение 2. Цикл связного графа G с фиксированным остовом Т, содержащий ровно одну хорду, называется фундаментальным.

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

Определение 4. Пусть G(V, Е) -- связный граф, V1 C V,

.

Разделителем графа G называется множество всех ребер из Е, один конец которых лежит в V1, а другой -- в .

Определение 5. Пусть G(V, Е) -- граф и V1 С V -- некоторое подмножество его вершин. Пусть Е1 -- подмножество всех ребер из Е, оба конца которых принадлежат V1. Тогда подграф G1(V1,E1) графа G называется вершинно порожденным и обозначается < V1 >.

Теорема 1. Пусть G(V, Е) -- граф, в котором каждая вершина имеет четную степень. Тогда множество ребер Е графа G можно представить в виде объединения реберно-непересекающихся циклов.

Теорема 2. Разделитель связного графа G является разрезом графа G - < V1 > и --связные подграфы графа G.

Если S -- разрез связного графа G, а V1 -- множество вершин одной компоненты связности графа G\S, то

S =.

Теорема 3. Любой разделитель связного графа G(V, Е) является разрезом или объединением реберно непересекающихся разрезов.

Теорема 4. Любые цикл и разрез связного графа имеют четное число общих ребер.

Матрицы, связанные с графами

Будем рассматривать ориентированные графы, которые мы будем называть "орграфами". Граф G всегда обозначает граф без петель на n вершинах и m ребрах.

Определение 1. Пусть G(V, Е) -- граф. Перенумеруем его вершины: V = {vi,...,vn}. Матрицу А = (aij) размера n x n, в которой

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

Предложение 1. Пусть G(V, Е) -- граф, в котором вершины перенумерованы, и А -- его матрица смежности. Тогда элемент mij матрицы M= Аk равен числу маршрутов между вершинами Vi и Vj длины к.

Определение 2. Пусть G(V, Е) -- граф, на каждом ребре которого задано направление. Такой граф будем называть орграфом. Ребра орграфа будем называть дугами. Если направление на дуге

e = (vi,vj)

задано от вершины vi, к вершине vj, то будем говорить, что дуга е исходит из вершины vi и заходит в вершину vj.

Определение 3. Пусть G(V, Е) -- орграф, в котором перенумерованы вершины и дуги. Матрицей инцидентности графа G называется матрица

В = bij

размера n x т, элементы которой определяются следующим образом:

Всякий столбец матрицы В орграфа содержит два ненулевых элемента, -1 и 1. Поэтому любую строчку этой матрицы можно определить по остальным (n - 1) строкам.

Определение 4. Матрицу Во, полученную из матрицы В вычеркиванием одной произвольной строки, будем называть усеченной матрицей инцидентности.

Очевидно, ранги матриц В и Во совпадают и не превосходят п-1.

Теорема 1. Определитель любой усеченной матрицы инцидентности дерева равен ±1.

Следствие. Ранг матрицы инцидентности связного графа G на п вершинах равен (n -- 1).

Определение 5. Пусть имеется связный граф G и его остов Т. Перенумеруем сначала хорды, а потом ветви графа G. Каждому фундаментальному разрезу придадим ориентацию, совпадающую с ориентацией соответствующей ветви. Матрицу К = (kij) размера (п -- 1) х т, строки которой соответствуют фундаментальным разрезам, а столбцы -- дугам орграфа G, будем называть матрицей фундаментальных разрезов, если

Определение 6. Пусть имеется связный граф G и его остов Т. Перенумеруем сначала хорды, а потом ветви графа G. Каждому фундаментальному циклу придадим ориентацию, совпадающую с ориентацией соответствующей хорды. Матрицу Ф = (Фij) размера (m-n+1) х т, строки которой соответствуют фундаментальным циклам, а столбцы -- дугам орграфа G, будем называть матрицей фундаментальных циклов, если

Теорема 2. Пусть G -- связный орграф, Т -- его ocmoв, В, К, Ф -- матрицы инцидентности, фундаментальных разрезов и фундаментальных циклов соответственно. Тогда

Определение 7. Матрица X размера р х q называется унимодулярной, если определитель любой ее квадратной подматрицы равен 1,-1 или 0.

Теорема 3. Матрицы инцидентности, фундаментальных циклов и фундаментальных разрезов связного графа G унимодулярны.

Теорема 4. Пусть G -- связный граф, Вo -- усеченная матрица инцидентности какой-либо из ориентации графа G. Тогда число остовов графа G равно .

2. Практическая часть

Вариант №2

Даны следующие граф G и его остов T:

n = 7, m = 10

Задачи:

Найти матрицу смежности графа G. С ее помощью найти число маршрутов из вершины V2 в вершину V5 длины 3;

Задать некоторую ориентацию графа G. Для данного остова Т перенумеровать сначала ветви, а потом хорды графа. Найти матрицы инцидентности (В), фундаментальных циклов (Ф) и разрезов (К) графа G. Проверить условия ВФТ=0 и ФКТ=0;

Найти код Прюфера для остова.

Матрица смежности A размера n x n:

Так как элемент mij матрицы M=Ak равен числу маршрутов между вершинами Vi и Vj длины k, то искомое число маршрутов между V2 и V5 равно 3. (см. Приложение)

Ответ: 3 маршрута.

Зададим ориентацию графа и пронумеруем ветви и хорды:

Матрица инцидентности размера n x m:

Матрица фундаментальных циклов размера (m-n+1) x m:

Фундаментальные разрезы:

К1 К2 K3 K4

{E1, E3} {E1, E2, E4} {E2, E5} {E6, E9}

K5 K6

{E7, E9, E10} {E8, E10}

Матрица фундаментальных разрезов размера (n-1) x m:

Условия ВФТ=0 и ФКТ=0 проверены в системе Matlab.

граф матрица прюфер matlab

Литература

1. А.В. Клюшин «Введение в дискретную математику», МИЭТ, 2004г.

2. И.Б.Кожухов, А.А.Прокофьев, Т.В.Соколова «Курс дискретной математики», МИЭТ, 2000г.

Размещено на Allbest.ru