Презентации лекций / Презентация лекции 10 ДМ 20
.pdf
1
2
Граф = ( ,) : → [ ;+∞) 3
4
взвешенныйграф |
( ) = ∑( ) - |
ρ( ) –весребра |
весграфа |
|
Пусть граф связный |
у негоесть остовы.Сравнимих по весу. |
||
Остов |
|
|
Минимальныйостов |
|
|
||
|
|
||
наименьшеговеса |
|
|
графа |
|
|
||
Как построитьминимальныйостов?
|
0-й шаг |
|
-й шаг |
|
|
|
К началушагапостроеностовныйподграф |
смножествомребер |
|
Строимостовный |
|
. Добавляемк нему из множества\ |
ребро так,чтобы |
|
подграф без ребер: |
|
соблюдалисьдваусловия: |
|
|
|
|
|
1) добавление не приводиткобразованиюцикла |
|
V |
= , = |
2) из ребер,удовлетворяющихп. 1), имеет наименьший вес |
||
|
|
|
Получаемновыйостовныйподграф … |
|
11
Деревосвыделеннойвершиной–корневоедерево
Бинарный кодкорневого дерева:
Базис индукции: |
|
|
Если |
|
|
01 |
|
корень |
|
01 |
01 |
0011 |
|
|
|
00100111 |
|
корень |
Индуктивный переход:
То
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 1 |
|
|
01 |
0101 |
01
01
01 001011
корень
1
2
3
4
=
0101001011
12
1
2
3
4
|
В любом |
|
Число нулей |
начальном |
|
отрезке число |
||
равно числу |
||
нулей больше |
||
единиц |
||
или равно |
||
|
||
|
числу единиц |
Бинарный
код
Разбиваем код на пары из 0 и 1 по правилу: |
|
|
|
|
|
первую 1 объединяем в пару с ближайшим |
0 1 0 0 1 0 1 1 |
|
2 |
||
слева 0; |
|
|
|
|
|
каждую следующую 1 объединяем в пару с |
1 |
2 |
3 |
|
3 |
ближайшим слева неиспользованным |
|
|
|
1 |
4 |
нулем. |
|
|
|
||
|
|
4 |
|
||
Каждая пара соответствует ребру графа. |
|
|
|
корень |
|
|
|
|
|
||
|
|
|
|
|
13 |
Строимкоддерева:
Нумеруемвершиныграфа.
Находим висячую вершинус наименьшим номером.Записываемномерсмежнойсней вершины (этоначало кода).Удаляем саму висячую синцидентнымейребром.
Такпоступаем дотехпор пока неостанется одно ребро(еговершиныв код невключают).
5
6
12
|
3 |
|
4 |
2 2 4 |
1 |
|
1 |
|
|
2 |
|
Строимдеревопокоду: |
3 |
|
4 |
||
|
Последовательноменяемкод, (шаг1 -первое число,шаг 2- второе число,…)
Очередноечисло заменяем на наименьшеенатуральное число,
которого нетв последовательности, полученной на предыдущем шаге.
Когда изменили последнююцифру кода, выписываемдва наименьшихнатуральных числа, которых в последнейверсиинет.
Это концы ребра,которое некодировалось. Если записать под последнимкодом исходный, тодруг под другом встанутконцы остальныхребер
2 2 4 1 |
|
|
6 |
5 |
|
|
|
||
3 2 4 1 |
|
|
|
|
|
|
|
2 |
|
3 5 4 1 |
|
1 |
|
|
|
|
3 |
||
3 5 2 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 5 2 4 |
1 6 |
|
4 |
|
|
|
|
|
|
2 2 4 1 |
|
|
14 |
|
|
|
|
2 |
|
3 |
|
= |
− |
Графсвязный |
|
Вграфенетциклов |
= |
− |
|
1 |
|
4 |
Дерево- |
|
|
Графсвязный |
Теорема |
Графсвязный |
о характеристическихсвойствах |
|
|
|
|
|
Вграфенетциклов |
деревьев |
Каждоеребро-мост |
|
6 |
|
5 |
|
|
|
Вграфенетциклов |
|
Любыедвевершины |
|
|
|
|
|
|
|
Добавлениелюбого |
|
графаможносоединить |
|
|
ребраприводитк |
|
простойцепью,причем |
|
|
образованиюровно |
|
единственной |
|
|
одногопростогоцикла |
|
|
15 |
|
|
|
|
|
О
б
о
с
н
о
в
а
н
и
я
Неодноэлементноедеревоимеет не менеедвух висячих вершин
О
б
о
с
н
о
в
а
н
и
я
16