Презентации лекций / Презентация лекции 9 ДМ 20
.pdf
1
2
3
4
|
, |
- мосты |
|
, |
, - не мосты |
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
все ребра - мосты |
|
|
|
|
|
|
|||||
11
1
2
3
4
Если 
–мост, то 
Ребрографа - мост |
Реброне содержится |
|
ни водном цикле |
||
|
12
1
2
3
4
|
|
|
= 2 |
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
= 0 |
|
|
|
|||||
13
|
О |
|
|
б |
|
|
о |
|
|
с |
|
|
н |
|
|
о |
|
|
в |
|
|
а |
|
|
н |
|
|
||
Если – мост, то |
и |
|
я |
||
|
||
|
|
14
|
|
О |
|
|
|
б |
|
|
|
о |
|
|
|
с |
|
|
|
н |
|
|
|
о |
|
|
|
в |
|
|
|
а |
|
Ребрографа - мост |
Реброне содержится |
н |
|
и |
|||
ни водном цикле |
|||
|
я |
15
О
б
о
с
н
о
в
а
н
и
я
16
План лекции
1.Пути, циклы, цепи на графе
2.Компоненты связности графа
3.Мосты и циклы графа.Цикломатическое число.
4.Фундаментальная система циклов графа
17
|
|
1 |
|
Намножествецикловграфавводим |
2 |
|
бинарноеотношениеравенства: |
3 |
Циклы |
множества ихребер совпадают |
4 |
|
Рефлексивное? Симметричное? Транзитивное?
Да |
Да |
Да |
- отношение эквивалентности
Для каждого цикла 
строим класс эквивалентности - совокупность всехциклов графа, равныхэтому циклу
18
|
1 |
Классы эквивалентности назовемабстрактными циклами |
2 |
|
3 |
Любой абстрактный цикл задается множествомсвоихребер |
4 |
Пример:
|
|
|
|
||
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
Абстрактные циклы:
|
= { |
, |
, |
} |
|
= { |
, |
, |
} |
|
= { |
, |
, |
, } |
Обобщенныйцикл -
Абстрактныйцикл
Объединениенепересекающихся абстрактныхциклов
Пустойцикл такжесчитаемобобщеннымциклом
19
|
1 |
Линейноепространство циклов: |
2 |
|
3 |
|
4 |
|
|
|
|
|
Сумма помодулюдва - |
|
Множество |
|
|
|
Операции |
разностьобъединения и пересечения |
|
|
|
|
множествребер циклов и |
|||
обобщенных |
|
|
|
наэтом |
|
|
циклов |
|
|
|
множестве |
Умножение на0 и 1: |
|
|
|
|
||||
|
|
|
|
|
||
|
|
|
|
|
|
= |
|
|
|
|
|
|
= |
Пример:
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
Абстрактные циклы: |
|
|
|
|
|
||
|
|
|
= |
, , |
, |
= |
|
|
= { , , } |
|
= |
, , |
= |
||
|
= { , , } |
||||||
|
|
|
|
|
|||
|
= { , , , } |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
20