Файл: Вершинами графа, элементы множества e называются ребрами графа а пара (V, e ), т е. множество вершин и ребер графа называется графом. Если две вершины графа соединены ребром, то такие вершины называются смежными.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.11.2023
Просмотров: 324
Скачиваний: 4
– пустой граф с
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