конечные графы. Вершинами графа, элементы множества e называются ребрами графа а пара (V, e ), т е. множество вершин и ребер графа называется графом. Если две вершины графа соединены ребром, то такие вершины называются смежными
![]()
|
Теория графов Пусть задано некоторое множествоVи множество E пар различных элементов из V . Элементы этого множества V называются вершинами графа , элементы множества E называются ребрами графа . а пара (V , E ) , т.е. множество вершин и ребер графа называется графом . Если две вершины графа соединены ребром , то такие вершины называются смежными . Вершины , которые соединены ребром называются его Концами. Если вершина является концом ребра , то будем говорить , чторебро выходит из вершины .Число ребер , выходящих из вершины vназывается степенью вершины и обозначается d(v) . Вершина степени 0 называется изолированной , степени 1висячей . Граф H называется подграфом графа G, если вершины и ребра H принадлежат G . Подграф H графа G называется подграфом , порожденным множеством вершин { ![]() ![]() ![]() ![]() ![]() ![]() все ребра графа G , соединяющие эти вершины . Подграф H графа G называется подграфом , порожденным множеством ребер { ![]() ![]() ![]() ![]() ![]() ![]() все вершины графа G , являющимися концами этих ребер . Граф , у которого каждая пара вершин соединена ребром , называется полным графом . Полный граф с n вершинами обозначается ![]() ![]() ![]() ребер . Граф , который не имеет ни одного ребра называется пустым . ![]() n вершинами . Граф с n вершинами называется помеченным, если его вершины занумерованы от 1 до n.Два помеченных графа считаются равными , если множества вершин и ребер у них совпадают . Теорема . Число помеченных графов сn вершинами равно ![]() ![]() Доказательство . Рассмотрим множество V={1 , 2 ,…,n } всех вершин графа и множество всех его потенциально возможных ребер E={ (1,1) ,…, (1,n) , …,(n-1 ,n) }. ![]() ![]() Для каждого ребра (i ,j)из множества E существует две возможности : ребро (i ,j) есть в графе или ребра (i ,j) нет в графе .Поэтому число различных помеченных графов равно ![]() ![]() Определение . Граф Gназывается связным , если от любой его вершины можно по ребрам перейти к любой другой вершине .Будем говорить , что две вершины графа принадлежат одной компоненте . если от одной из них до другой можно перейти по ребрам графа . Задача .Если для графа наименьшая степень его вершин ![]() Решение . Рассмотрим компоненту , содержащую наименьшее число вершин .В ней будет не более ![]() ![]() Задача .Если граф с ![]() ![]() Решение . Рассмотрим несвязный граф с ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Определение .Пусть задан граф G . Рассмотрим граф ![]() ![]() только тогда , когда эти вершины не соединены ребром в графе G . Граф ![]() дополнительным графом к графу G . Задача . Из двух графов G и дополнительного к нему графа ![]() Решение . Пусть граф G не является связным и состоит из компонент ![]() ![]() дополнительном графе существуют ребра между любыми вершинами компонент ![]() ![]() (i ![]() ![]() Определение .Граф , степени всех вершин которого одинаковы называется регулярным графом . Определение . Граф , у которого существуют пары вершин , соединенные несколькими ребрами , называется мультиграфом . Лемма о рукопожатиях .Сумма степеней вершин графа равна удвоенному числу ребер . Следствие . Число вершин нечетной степени в графе четное . Доказательство леммы .В сумме степеней вершин графа каждое ребро учитывается дважды . Определение .Маршрутом в графе называется такая последовательность чередующихся вершин ![]() ![]() ![]() ![]() вершины ![]() ![]() ![]() ![]() Маршрут . в котором все ребра различные называется цепью . Про цепь говорят , чтоона соединяет свои концы . Цепь в графе можно задавать перечислением только вершин или только ребер .Цепь , в которой первая и последняя вершины совпадают , называется циклом . Цепь графа называется простой цепью ,если все ее вершины , кроме возможно крайних различны .Цикл графа называется простым циклом , если все его вершины кроме первой и последней различны . Простой цикл с p вершинами обозначается ![]() Определение .Ориентированная простая цепь называется путем ,ориентированный простой цикл называется контуром . ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Замкнутый ориентированный маршрут 1 ![]() Ориентированная цепь : 4 ![]() 6 ![]() 3 ![]() ![]() Определение. Длиной маршрута называется число ребер в нем с учетом повторения . Определение .Длиной цепи называется число содержащихся в ней ребер . Определение . Расстоянием между двумя вершинами графа называетсянаименьшаяиз длин цепей , соединяющих эти вершины . Сама такая цепь называется геодезической . Расстояние между вершинами uиv обозначается d(u , v). Определение .Самая длинная геодезическая цепь называется диаметром графа . Длину диаметра будем называть диаметром и обозначать D. Пример ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() d(1 ,5 )=2 , d(1 ,9 )=3 , d(4 ,9 )=3 .D=3. Ярусом вершины vпорядка n(обозначается D(v , n)) , n=1 , 1 , 2 ,… называется множество вершин , находящихся от вершины v на расстоянии n . Теорема .Пусть G=G (V , E ) –граф . Если существует путь из вершины ![]() ![]() ![]() ![]() Д ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Теорема . Граф G является связным тогда и только тогда , когда между любыми двумя его вершинами существует простой путь . Определение. Пусть G=G (V , E ) – граф . Подграф ![]() ![]() Если ![]() ![]() ![]() Значит ![]() Определение .Граф , вершины которого можно разбить на два множества ( две доли ) таким образом , что каждое ребро будет соединять вершины из разных множеств , называется двудольным . Двудольный граф обозначается G( ![]() ![]() ![]() ![]() ![]() ![]() Определение. Если каждая вершина графа отмечена , то он называется размеченным . Пример .Теорема ( Кенига ). Для того , чтобы граф был двудольным , необходимо и достаточно , чтобы он не содержал циклов нечетной длины . Доказательство .⇒ Пусть G( ![]() ![]() ![]() нечетной длины .Пусть ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() соединяет вершины из одной доли –противоречие . ![]() ![]() ![]() Включим во множество ![]() ![]() Выделим ярусы вершины v:D(v,0) , D(v ,1) , D(v , 2),….Вершины ярусов D (v , 2k+1 ), K=1 , 2 ,… включим во множество ![]() ![]() ![]() ![]() ![]() Есть вершины ,принадлежащие одной доле и соединенные ребром . Пусть для определенности u , w ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() число . Противоречие . |