Графы, ориентированные графы, матрица смежности , матрица инцидентности, метрические характеристики графа

Глава 6 Графы, ориентированные графы, матрица смежности , матрица инцидентности, метрические характеристики графа 6.1.Графы, ориентированные графы, матрица смежности , матрица инцидентности Граф G=(V,E), это ориентированная пара множеств, где V множество вершин, Е – множество рёбер. Ребро – множество из двух вершин {v,u}. Ориентированный граф (орграф) G=(V,E), это ориентированная пара множеств, где V множество вершин, Е – множество дуг (ориентированных рёбер) (v,u). Мультиграф - содержит кратные рёбра, но не содержит петель. Псевдограф – содержит петли. Взвешенный граф – граф, в котором каждому ребру сопоставлен вес – положительное целое число. Вершины v,u инцидентны ребру e ={ v,u } и ребро е инцидентно вершинам v,u. Вершины v,u инцидентны ориентированному ребру e =(v,u) и ребро е инцидентно вершинам v,u. При этом е идёт из вершины v в вершину u. Степень вершины v – число рёбер, инцидентных этой вершине. Для неориентированного графа обозначается deg (v). Для ориентированного графа deg in(v) – число рёбер, входящих в вершину v и deg out(v) – число рёбер, выходящих из вершины v. Висячая вершина - вершина степени 1. Изолированная вершина - вершина степени 0. Количество рёбер графа равно половине суммы степеней всех вершин графа . Вершины v,u, являющиеся концами ребра e ={ v,u } (дуги e =(v,u) ), называются смежными. Чередующаяся последовательность инцидентных вершин и рёбер, начинающаяся и заканчивающаяся вершинами, называется маршрутом. Маршрут без повторяющихся рёбер называется цепью в графе и путём в орграфе. Простая цепь - цепь без повторяющихся вершин. Матрица смежностb графа (орграфа) с n вершинами это двоичная матрица A=(aij) с n строками и n столбцами, для которой aij = 1, если { vi,vj }E для , 0, в противном случае. Матрица инцидентности графа с n вершинами и m рёбрами это бинарная матрица B=(bij) с n строками и m вершинами: для графа bij = 1, если вершина vi инцидентна ребру ej, 0, в противном случае. для орграфа bij = 1, если из вершина vi является концом ребра ej, -1, если вершина vi является началом ребра ej, 0, если вершина vi не инцидентна ребру ej. Граф G’=(V ’,E ’) называется подграфом графа G=(V,E) если V’ V, E’ E. Граф называется связным, если между любой парой вершин графа существует цепь. Подграф G’ графа G называется компонентой графа G, если граф G’ связен, и при добавлении к G’ любой вершины или любого ребра графа G полученный граф несвязен. 6.2. Специальные графы Полный граф Kn с n вершинами содержит все возможные рёбра, их количество равно n(n1)/2. Цикл - связный граф Cn с n вершинами, в котором все вершины имеют степень 2. Простая цепь Pn. - связный граф с n  2 вершинами степени 2 и двумя вершинами степени 1. Звезда Sn - связный граф с n  1 вершиной степени 1 и одной вершиной степени n  1. Колесо Wn - связный граф с n  1 вершиной степени 3 и одной вершиной степени n  1. Пустой граф Nn - граф с n вершинами, в котором нет рёбер. 6.3. Изоморфные графы Множество рёбер графа можно рассматривать как однородное бинарное отношение на множестве вершин. Пусть имеется два графа G=(V,E) и G’ = (V’,E’), │V│=│V’ │и имеется взаимно однозначное соответствие между вершинами множеств V, V’ . Пусть вершина v V отображается на вершину v’ V’, вершина u V отображается на вершину u’V’. Если из того, что существует ребро { v,u } Е следует, что существует ребро { v’,u’ } Е’ и наоборот, то графы G и G’ называются изоморфными. Характеристики графа, которые сохраняются для изоморфных графов, называются инвариантами. Например, число вершин, рёбер, циклов, число компонент связности, диаметр. Полная система инвариантов, позволяющая для пары графов определить изоморфны ли они, неизвестна. Но и отсутствие такой системы не доказано. 6.4. Метрические характеристики графа Длина цепи равна числу рёбер в ней. Расстояние d(v, u) между вершинами v, u равна длине кратчайшей цепи, соединяющей эти вершины. Расстояние обладает следующими характеристиками d(v,u)0, d(v,u)=0  v=u, d(v,u)= d(u, v), d(v,u)+ d(u, t) d(v,t)  неравенство треугольника. Величина (v)= max d ( v, u) называется эксентриситетом вершины v в графе G=( V,E). u V Величина R(G)= min ( v) = min max d( u, v) называется радиусом графа G=( V,E). v V v V u V Величина D(G)= max d( v, u) называется диаметром графа G=( V,E). v V , u V Подмножество вершин C={v/ (v)= R(G)} называется центром графа G. ГЛАВА 7. Операции над графами _ Дополнение G графа G = (V,E), |V|=n это граф, полученный путём удаления из полного графа Kn всех рёбер графа G. Другие операции: инверсия, пересечение, объединение, декартово произведение, разность, симметричная разность, транзитивное замыкание. Глава 8. Дерево. Остовное дерево. Матричная теорема о деревьях. Фундаментальные циклы и разрезы. 8.1. Деревья. Остов графа. Лес – граф без циклов. Дерево - связный лес. Теорема 8.1. Любое дерево содержит висячую вершину Теорема 8.2. Дерево с n вершинами содержит n1 рёбер. Остовный граф графа G – подграф графа G, содержащий все вершины графа G, являющийся лесом. Остов графа G – подграф графа G, содержащий все вершины графа G, являющийся деревом. Следствие 8.1. Лес с n вершинами и k компонентами содержит nk рёбер. Все компоненты леса - деревья. Число (G)=nk - ранг (коцикломатическое число) графа G с n вершинами и k компонентами относительно его остовного леса. Число (G) = m(G)=mn+k - цикломатическое число графа G с n вершинами, k компонентами, m рёбрами относительно остовного леса. Число (G)=n1 - ранг (коцикломатическое число) связного графа G с n вершинами. Хорда графа G относительно остова Т – ребро, не принадлежащее остову Т графа G . Число (G) = m(G)= mn+1 - цикломатическое число а также также число хорд связного графа G с n вершинами, m рёбрами. 8.2. Матричная теорема о деревьях Сконструируем матрицу М, используя матрицу смежности графа G с n вершинами. Заменим диагональные элементы aii, i =1,..., n степенями соответствующих вершин deg(vi), а остальные ненулевые элементы aij (ij aij 0) их отрицаниями aij. Теорема 8.3. Значение всех алгебраических дополнений матрицы М одинаково и равно количеству остовов графа G . 8.3. Фундаментальные циклы и разрезы. В общем случае связный граф имеет несколько остовов. Пусть Т остов графа G. Обозначим Н множество всех хорд графа G относительно остова Т. При добавлении к Т хорды относительно Т образуется цикл. Будем добавлять к Т по одной хорде из Н. Полученные таким образом циклы называются фундаментальными циклами графа G относительно остова Т. Множество всех фундаментальных циклов относительно остова Т называется системой фундаментальных циклов графа G относительно остова Т. Это система линейно независимых циклов, т.е. ни один из них не может быть получен как линейная комбинация остальных циклов. Количество таких циклов равно количеству хорд, т.е. равно (G) = mn+1. Сказать – одна хорда 8.4.Фундаментальные разрезы Множество рёбер, при удалении которых увеличивается количество компонент связности, разрезом. На основании системой фундаментальных циклов графа G относительно остова Т можно построить систему фундаментальных разрезов графа G относительно остова Т. Количество таких разрезов равно (G)=n1. Глава 9. Эйлеровы и Гамильтоновы графы Эйлеров цикл графа G - цикл, который содержит все рёбра графа, причём каждое ребро включено только один раз. Эйлеров граф – граф, для которого существует Эйлеров цикл. Теорема 9.1. Граф является Эйлеровым тогда и только тогда, когда степени всех его вершин чётны. Ориентированный граф называется сильносвязным, если для любой пары вершин v , u существует как путь из v в u, так и из и в v. Цикл в ориентированном графе называется контуром. Теорема 9.2. Ориентированный граф имеет Эйлеров контур тогда и только тогда, когда он сильносвязен и для любой его вершины degin(v)= degout(v)i. Гамильтонов цикл графа G - цикл, который содержит все вершины графа, причём каждая вершина включена только один раз. Гамильтонов граф – граф, для которого существует Гамильтонов цикл. Не существует эффективного критерия для определения обладает ли граф Гамильтоновым циклом. Теорема 9.3. (Дирак) Если степени всех вершин графа с n вершинами больше или равны n /2, то в графе существует Гамильтонов цикл. Существование Эйлерова и Гамильтонова циклов не связано друг с другом. Глава 10. Стабильность графа. 10.1. Внешняя стабильность. Доминирующее множество Подмножество вершин графа G =( V,E) называется доминирующим множеством или множеством внешней устойчивости, если любая вершина графа G либо принадлежит этому подмножеству либо смежна хотя бы с одной вершиной этого подмножества. Минимальное доминирующее множество графа – доминирующее множество, любое подмножество которого не является доминирующим для данного графа. Наименьшее доминирующее множество – минимальное доминирующее множество, содержащее наименьшее количество элементов по сравнению с остальными доминирующими множествами данного графа. Число доминирования или число внешней устойчивости – количество элементов в наименьшем доминирующем множестве. 10.2. Внутренняя стабильность. Независимое множество. Подмножество вершин графа G =( V,E)называется независимым множеством или множеством внутренней устойчивости, если вершины этого подмножества попарно несмежны. Максимальное независимое множество графа – независимое множество, для каждой вершины которого среди не вошедших в него вершин существует смежная с ней вершина. Наибольшее независимое множество – максимальное независимое множество, содержащее наибольшее количество элементов по сравнению с остальными независимыми множествами данного графа. Число независимости ( число внутренней устойчивости) – количество элементов в наибольшем независимом множестве. Глава 11. Раскраска вершин графа Правильная раскраска вершин графа – раскраска, при которой смежные вершины имеют разные цвета. Очевидно, что вершины, принадлежащие независимому множеству, могут быть раскрашены одним цветом. Хроматическое число графа (G) – наименьшее количество красок для правильной раскраски графа. Двудольный граф – граф G =( V,E),для которого множество V можно разбить на подмножества V1 and V2: V1  V2=V, V1  V2=. При этом V1 и V2 независимые множества и для любого ребра один конец принадлежит V1 , другой V2. Хроматическое число двудольного графа равно 2. Другой тип раскраски. Глава 12.Планарные графы. Критерий Понтрягина-Куратовского планарности графов. Раскраска планарного графа. Плоский граф - граф, который изображён на плоскости без пересечения ребер. Планарный граф – граф, для которого существует изоморфный ему плоский граф. Грань плоского графа - часть плоскости, ограниченная простым циклом и не содержащая внутри других циклов. Бесконечная грань - часть плоскости, расположенная вне плоского представления графа и ограниченная изнутри простым циклом. Соседние грани – грани, границы которых имеют хотя бы одно общее ребро. Обозначим n количество вершин, m количество рёбер, f количество граней графа. Если в плоском графе длина всех простых циклов >3, то справедливо неравенство m  (для двудольного графа m 2f). 3f 2 Theorem 12.1. Для плоского графа справедлива формула Эйлера n+ f =m+2. Следствие 12.1. Для плоского графа с m рёбрами и n вершинами справедливы неравенства m  3 n 6 (для двудольного графа m 2n4). Следствие 12.2. Любой планарный граф Any planar graph possesses a vertex of the degree at most 5. Следствие 12.3. Граф K5 не планарен. Следствие 12.4. Граф K3,3 не планарен. 12.2. Критерий планарности Понтрягина-Куратовского. Проходная вершина – вершина степени 2. Операция добавления проходной вершины w: ребро {u,v} заменяется двумя рёбрами {u,w} , {w,v}. Операция удаления проходной вершины w: пара рёбер {u,w} , {w,v} заменяется ребром {u,v}. Операция стягивания ребра е={ u,v } в точку: склеивание вершин u,v в одну вершину. Два графа гомеоморфны, если один из них может быть получен из другого применением конечного числа операций добавления и удаления проходных вершин и стягивания рёбер. Если графы гомеоморфны, то они планарны или непланарны одновременно. Теорема Понтрягина-Куратовского. Граф G планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных графам K5 или K3,3. 12.3. Раскраска планарного графа Теорема 12.3. Хроматическое число планарного графа не превышает 5. Глава 13. Паросочетание в двудольном графе Теорема Холла. Венгерский алгоритм Паросочетание в двудольном графе — произвольное множество рёбер двудольного графа такое, что никакие два ребра не имеют общей вершины. Вершины двудольного графа, инцидентные рёбрам паросочетания, называются покрытыми. Максимальное паросочетание — это такое паросочетание в графе которое не содержится ни в каком другом паросочетании этого графа, то есть к нему невозможно добавить ни одно ребро, которое бы являлось несмежным ко всем рёбрам паросочетания. Паросочетание двудольного графа называется совершенным, если оно покрывает все вершины доли V1 графа. Чередующаяся цепь — путь в двудольном графе, для любых двух соседних рёбер которого верно, что одно из них принадлежит паросочетанию, а другое нет. Вершины, неинцидентные рёбрам паросочетания, называются свободными. Допустимая цепь — чередующаяся цепь, у которой оба конца свободны. Пусть A V1. Обозначим (A) множество вершин, смежных вершинам из А (очевидно (A)V2). Теорема 13.1 (Ф.Холл). Совершенное паросочетание в двудольном графе G = (V1,V2;E) существует тогда и только тогда, справедливо условие A, A V1 |A||(A)| . Венгерский алгоритм 1)Выбрать какое-нибудь паросочетание. 2)Найти допустимую цепь с. 3)Удалить из паросочетания все рёбра паросочетания, принадлежащие цепи с, и добавить к паросочетанию все свободные вершины цепи с. 4)Выполнять пункты 2, 3 пока удаётся найти допустимую цепочку. Если не удалось найти допустимую цепочку, то - либо совершенное паросочетание построено, т.е. все вершины V1 покрыты. - либо совершенного паросочетания в данном графе не существует, т.е. не все вершины V1 покрыты.