Презентации лекций / Презентация лекции 9 ДМ 20
.pdf
Тема 9 «Циклы и мосты. Фундаментальная система циклов»
«Дискретная математика» Олейник Татьяна Анатольевна
кафедра ВМ-1
План лекции
1.Пути, циклы, цепи на графе
2.Компоненты связности графа
3.Мосты и циклы графа.Цикломатическое число.
4.Фундаментальная система циклов графа
2
План лекции
1.Пути, циклы, цепи на графе
2.Компоненты связности графа
3.Мосты и циклы графа.Цикломатическое число.
4.Фундаментальная система циклов графа
3
, |
…, –вершины |
|
|
,…, |
–ребра |
1 |
|||
|
|
2 |
|||||||
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
3 |
|
|
||||||||
|
|
4 |
|||||||
|
|
|
= |
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
–началопути |
|
|
|
|
|
–конец пути |
|
|
|
вершина– путьдлины 0
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
допускается |
= |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
- путь |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
- цепь |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Путь |
|
|
|
|
Цепь |
Простая |
Цикл |
|
|
Простой |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
цепь |
|
|
|
|
цикл |
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
- |
|
- |
- |
|
|
|
|
|
- |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
+ |
|
- |
- |
|
|
|
|
|
- |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
+ |
|
- |
+ |
|
|
|
|
|
- |
||||||
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
+ |
|
+ |
+ |
|
|
|
|
|
+ |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
4
|
началои конец совпадают |
|
Путь |
началои конец совпадают |
Замкнутыйпуть |
|
||
Цепь |
началои конец совпадают |
Цикл |
ребра |
|
|
разные |
Простаяцепь |
|
|
Простойцикл |
|
вершины |
|
|
|
|
|
разные |
|
|
Награфеесть |
Награфеесть |
путьиз в |
простаяцепьиз в |
|
Леммаопростойцепи |
1
2
3
4
5
План лекции
1.Пути, циклы, цепи на графе
2.Компоненты связности графа
3.Мосты и циклы графа.Цикломатическое число.
4.Фундаментальная система циклов графа
6
|
1 |
Намножествевершинграфавводим |
2 |
бинарноеотношениедостижимости (связности) ~ |
3 |
в |
4 |
Рефлексивное? Симметричное? Транзитивное?
Да |
Да |
Да |
- отношение эквивалентности
Для каждой вершины строим класс эквивалентности 
~ - совокупность вершин графа, вкоторыеведетпуть из
7
Что мы знаем |
Каждый из них включает хотя бы однувершину |
|
|
о классах эквивалентности? |
Объединение классов равно |
Классы либоне пересекаются, либо совпадают Совокупностьразличных классов эквивалентности
1
2
3
4
|
= [ ] |
= [ ] |
~ |
… |
|
~ |
|
|
Подграф, |
Подграф, |
|
Компоненты |
|
… |
связности |
|||
порожденный |
порожденный |
|||
|
графа |
|||
|
|
Совокупностьподграфов, порожденныхклассами эквивалентности |
8 |
Пример: |
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
Граф, |
|
|
|
Граф, |
|
|
порожденный |
||||
порожденный |
|
|
|
||
|
{ ,} |
|
|||
{ ,,} |
|
|
|
Граф, |
|
|
|
|
|
||
|
|
|
|
||
|
|
|
порожденный |
||
|
|
|
|
||
|
|
|
{ } |
||
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
2 |
|
3 |
[ ]~= [ ]~= [ ]~= { ,,} |
4 |
[ ]~= [ ]~= { ,} |
|
[ ]~= { } |
|
|
|
Граф имеет три различные компоненты связности
Числоразличныхкомпонентсвязности– |
Если |
= 1, то графсвязный |
||
числосвязностиграфа |
|
|||
( ) |
||||
|
|
|||
|
|
|
||
|
|
|
|
|
9
План лекции
1.Пути, циклы, цепи на графе
2.Компоненты связности графа
3.Мосты и циклы графа.Цикломатическое число.
4.Фундаментальная система циклов графа
10