конечные графы. Вершинами графа, элементы множества e называются ребрами графа а пара (V, e ), т е. множество вершин и ребер графа называется графом. Если две вершины графа соединены ребром, то такие вершины называются смежными

• Название: Вершинами графа, элементы множества e называются ребрами графа а пара (V, e ), т е. множество вершин и ребер графа называется графом. Если две вершины графа соединены ребром, то такие вершины называются смежными
• Анкор: конечные графы
• Дата: 21.05.2023
• Размер: 350.58 Kb.
• Имя файла: teoria_konechnykh_grafov.docx
• Тип: Документы; #1148256
• страница: 1 из 4

Теория графов

Пусть задано некоторое множество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 вершинами равно , где k= .

Доказательство . Рассмотрим множество V={1 , 2 ,…,n } всех вершин графа и множество

всех его потенциально возможных ребер E={ (1,1) ,…, (1,n) , …,(n-1 ,n) }. =K= .

Для каждого ребра (i ,j)из множества E существует две возможности : ребро (i ,j) есть в графе или ребра (i ,j) нет в графе .Поэтому число различных помеченных графов равно

, где k= .

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

Задача .Если для графа наименьшая степень его вершин , то граф G связный .

Решение . Рассмотрим компоненту , содержащую наименьшее число вершин .В ней будет не более вершин . Но в таком случае степень любой вершины из этой компоненты будет не больше , что противоречит условию задачи .

Задача .Если граф с вершинами имеет больше , чем ребер ,то он связный .

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

p .число ребер в графе будет + = -np+ .

-np+ . (p)=2p-n =2(p- ) .Приp значение квадратного трехчлена растет . Наибольшее p при котором граф будет несвязным равно 1.Одна компонента такого графа будет , а вторая – граф .Число ребер в графе равно . а граф который получается из условия задачи имеет больше , чем значит он связный .

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

только тогда , когда эти вершины не соединены ребром в графе G . Граф называется

дополнительным графом к графу G .

Задача . Из двух графов G и дополнительного к нему графа хотя бы один из них связен .

Решение . Пусть граф G не является связным и состоит из компонент , . Тогда в

дополнительном графе существуют ребра между любыми вершинами компонент и

(i и граф будет связным .

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

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

Лемма о рукопожатиях .Сумма степеней вершин графа равна удвоенному числу ребер .

Следствие . Число вершин нечетной степени в графе четное .

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

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

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

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

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

Цепь графа называется простой цепью ,если все ее вершины , кроме возможно крайних различны .Цикл графа называется простым циклом , если все его вершины кроме первой и последней различны . Простой цикл с p вершинами обозначается .

Определение .Ориентированная простая цепь называется путем ,ориентированный простой цикл называется контуром .

1 4 7 Ориентированный маршрут

2 5 8 1

3 6 9

Замкнутый ориентированный маршрут 1 .

Ориентированная цепь : 4 . Замкнутая ориентированная цепь :

6 .Пример пути . соединяющего вершины 3 и 9 :

3 .Пример контура : 5 .

Определение. Длиной маршрута называется число ребер в нем с учетом повторения .

Определение .Длиной цепи называется число содержащихся в ней ребер .

Определение . Расстоянием между двумя вершинами графа называетсянаименьшаяиз

длин цепей , соединяющих эти вершины . Сама такая цепь называется геодезической . Расстояние между вершинами uиv обозначается d(u , v).

Определение .Самая длинная геодезическая цепь называется диаметром графа . Длину диаметра будем называть диаметром и обозначать D.

Пример

2 6 9

1 3 5

4 7 8

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, если выполнены следующие условия :

1. 
   - непустой связный подграф .
   
2. 
   Если - связный подграф графа G и , тогда .
   

Значит - максимальный связный подграф графа G .

Определение .Граф , вершины которого можно разбить на два множества ( две доли ) таким образом , что каждое ребро будет соединять вершины из разных множеств , называется двудольным . Двудольный граф обозначается G( , E). Полный двудольный граф , у которого =m , =n, обозначим .Если =1 , то граф называется звездой .

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

Пример .Теорема ( Кенига ). Для того , чтобы граф был двудольным , необходимо и достаточно , чтобы он не содержал циклов нечетной длины .

Доказательство .⇒ Пусть G( , E)-двудольный граф , в котором существует цикл

нечетной длины .Пусть = -…- - - . Не ограничивая общности можно считать , что . Тогда ,…, , , то есть ребро (

соединяет вершины из одной доли –противоречие .

Пусть все простые циклы графаG(V, E) имеют четную длину . Граф G можно считать связным . Разобьем вершины графа G на два непересекающихся множества и

1. 
   Включим во множество произвольную вершину v
   
2. 
   Выделим ярусы вершины v:D(v,0) , D(v ,1) , D(v , 2),….Вершины ярусов D (v , 2k+1 ),
   

K=1 , 2 ,… включим во множество .Вершины ярусов D (v , 2k )включим во множество . Тогда =V; = .Предположим , что в графе G

Есть вершины ,принадлежащие одной доле и соединенные ребром .

Пусть для определенности u , w .u D(v , 2n+1), D(v , 2m+1). Рассмотрим геодезические , соединяющие вершину v с вершинами u иw. Обозначим их , , а их длины обозначим и .В силу сказанного =2n+1 , =2m+1 .Эти геодезические имеют общие вершины , например, . Пусть - наиболее удаленная от вершины общая вершина геодезических . Может оказаться , что . Так как и

- это участки геодезических , то и и - это геодезические соединяющие вершины . Значит они имеют одинаковую длину , = =k . Тогда длина простой цепи

−w- - равна 1+(2n+1-k)+(2m+1-k)=1+2m+2n-2k–нечетное

число . Противоречие .