Лекции по "Алгебре"

    Раздел 3. Теория графов

    Первые  задачи теории графов связаны с решением математических развлекательных задач  и головоломок (задача о Кенигсбергских мостах, задача о расстановке ферзей на шахматной доске, задача о перевозках, задача о кругосветном путешествии). Одним из первых результатов в теории графов явился критерий существования обхода графа без повторений, полученный Леонардом Эйлером, при решении задачи о Кенигсбергских мостах.

    Тема 3.1 Основные определения теории графов

    Наглядное представление о графе можно получить, если представить себе некоторое множество точек плоскости Х, называемых вершинами, и множество направленных или ненаправленных отрезков М, соединяющих все или некоторые из вершин и называемых дугами. Математически граф определяется как пара множеств (Х, Г).

    

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

    Определение: Граф, содержащий только ребра, называется ориентированным.

    Определение: Граф, содержащий только дуги, называется неориентированным.

    Определение: Пара вершин может соединяться двумя или более ребрами одного направления, такие ребра называются кратными.

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

    Определение: Вершины, соединенные ребром или дугой называются смежными,

    Определение: Дуги, имеющие общие вершины называются смежными.

    Определение: Ребро и любая из двух ее вершин называется инцидентными.

    Существуют  различные способы задания графов. Пусть u₁… u_n – вершины графа, а e₁… e_m – его ребра.

1. Матрица смежности. Это матрица, размерностью nxm, такая что, A_ij – равен числу ребер или дуг, соединяющую i – тую и j- тую вершины, и равна 0 если вершины несмежны.
2. Матрица инцидентности. B_ij =1, если u_i инцидентна ребру e_j , и = 0 если вершина и ребро неинцидентны.
3. Перечислением упорядоченных или неупорядоченных пар смежных вершин.
4. Заданием множества вершин графа, и способа отображения множества Х в множество Х.

Определение: Подграфом G_A графа G=(Х,Г) называется граф, в который входит лишь часть вершин графа G, образующих множество А вместе с дугами, соединяющими эти вершины.

Математически подграф G_A определяется следующим образом:

             G_A (А, Г_A )   где АÌХ    Г_A Х=(Гх)А

Определение:  Частичным графом G_A графа G=(Х,Г) называется граф, содержащий все вершины графа и только часть дуг графа.

Пример: Пусть граф G  - карта шоссейных дорог России, тогда карта шоссейных дорог Приморья – подграф, а карта главных дорог России – частичный граф.

Определение: Путем в графе G называется такая последовательность дуг, в которой конец каждой предыдущей дуги является началом следующей дуги. Путь М, последовательными вершинами которого являются вершины a,b,c … обозначается М(a,b,c…)

Определение: Длиной пути М называется число К, равное числу дуг, составляющих путь М.

Путь может быть конечным и бесконечным. В случае бесконечного пути полагаем К = ¥.

Определение: Путь, в котором ни одна дуга не встречается дважды, называется простым.

Определение:  Путь, в котором ни одна вершина не встречается дважды, называется элементарным.

Определение: Контур – это конечный путь М, у которого начальная и конечная вершина совпадают. При этом контур называется элементарным, если все его вершины различны ( за исключением начальной и конечной вершины).

Для неориентированного графа аналогичными понятиями являются понятия цепи и цикла. С понятием неориентированного графа связано понятие связности графа.

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

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

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

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

Определение: Степенью вершины u  графа G называется число ребер, инцидентных этой вершине.

Если граф G без петель имеет n вершин и m ребер, то сумма степеней всех вершин

    

Определение: Вершина u называется изолированной, если d_i  = 0, и концевой, если d_i= 1.

Определение: Граф, у которого все вершины имеют одинаковые степени (равные К), называется регулярным (степени К),

В полном графе  нет петель, и каждая пара вершин соединена в точности одним ребром.

Определение: Для графа G=(Х,Г), не имеющего петель и кратных ребер, дополнительным графом к G называют граф F= (Х1,Г1), у которого Х1 = Х, и вершины смежны только в том случае, если они несмежны в G.

Граф дополнительный к полному состоит из изолированных  вершин. Такой граф называется пустым, или вырожденным.

    Тема 3.2 Операции над графами

    Одноместные операции

1. Удаление  ребра графа – при этом все вершины графа сохраняются
2. Добавление ребра графа между двумя существующими вершинами.
3. Удаление вершины (вместе с инцидентными ребрами).
4. Добавление вершины (которую можно соединить с некоторыми вершинами графа).
5. Стягивание ребра – отождествление пары вершин, т.е. удаление пары смежных вершин, и добавление новой вершины, смежной с теми вершинами, которые были смежны, хотя бы одной из удаленных вершин)
6. Подразбиение ребра с- удаление ребра и добавление новой вершины, которая соединяется ребром с каждой из вершин удаленного ребра.

    Двуместные  операции

1. Объединение графов

 Пусть G1=(Х1,Г1) и G2=(Х2,Г2) такие, что Х1 Ç Х2= Æи Г1 Ç Г2= Æ Объединением графов называется граф, со множеством вершин Х1 È Х2 и ребер Г1 È Г2.

2. Сложение по модулю 2

Пусть G1=(Х1,Г1) и G2=(Х2,Г2). Объединением графов называется граф, со множеством вершин Х1 È Х2 и ребер (Г1 È Г2)\( Г1 Ç Г2).

    Тема 3.3 Отношения порядка и эквивалентности на графе

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

    Рефлексивность: Условие Х<=Х – истинно. Это означает эквивалентность вершины самой себе. Однако, при желании, это условие можно рассматривать как наличие петли в вершине Х.

    Транзитивность: Условие Х<=У, У<=Z Þ Х<=Z означает, сто вершины последовательно встречаются на одном и том же пути.

    Антисимметричность  Х<=У, У<=Х Þ Х º У. Левая часть этого выражения говорит о том, что существует путь из Х в У и путь из У в Х. Т.о. в графе существует контур, на котором лежат вершины Х и У. Из правой части свойства вытекает, что вершины лежащие на одном контуре – эквивалентны. Будем рассматривать этот вывод, как определение отношения эквивалентности на графе и покажем, что такое определение удовлетворяет всем условиям отношения эквивалентности.

    Рефлексивность: Условие Х=Х – вытекает из определения отношения эквивалентности. Всегда можно считать, что существует путь из Х в Х длины 0.

    Транзитивность: Условие Х=У У=Z Þ Х=Z так же очевидно, так как если в графе есть контур, содержащий вершины Х и У, и есть контур, содержащий У и Z, то существует контур, содержащий вершины Х и Z.

    Симметричность: Условие Х=У Þ У=Х так же очевидно и вытекает из определения отношения эквивалентности и понятия контура графа.

    Таким образом, отношения порядка и эквивалентности определяют некоторый связный граф.

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

    Тема 3.4 Числовые характеристики графа

    Определение: Цикломатическое число. Пусть G – неориентированный граф, имеющий n – вершин, m– ребер и r – компонент связности. Цикломатическим числом графа называется

      n(G)=m-n+r

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

    Определение: Множество внутренней устойчивости. Множество С Í Х графа G = (Х,Г) называется внутренне устойчивым, если никакие две вершины из С несмежны, т.е. для "х Î С Þ Г_х ÇС = Æ.

    Определение: Множество внутренней устойчивости, содержащее наибольшее число элементов, называется числом внутренней устойчивости графа G.

    Определение: Множество внешней устойчивости. Множество С Ì Х графа G = (Х,Г) называется внешне устойчивым, если

    "х Î С Þ Г_х ÇС = Æ.

    Определение: Множество внешней устойчивости, содержащее наименьшее число элементов, называется наименьшим внешне устойчивым множеством, а число элементов этого множества называется числом внешней устойчивости графа.

    Тема 3.5 Обход графа

    Определение: Маршрут, содержащий все ребра или все вершины графа, и обладающий определенными свойствами называется обходом графа.

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

    Существует  критерий существования эйлеровый  циклов в графе.

    Теорема Эйлера: Связный граф имеет эйлеров цикл Û когда каждая его вершина имеет четную степень.