Лекции 14. Основные понятия теории графов. Некоторые виды графов (4 часа)

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


Алгоритм Прима. Выбираем вершину , которая будет корнем дерева. Из трех ребер, инцидентных вершине , выбираем те, что имеют наименьший вес.
Два ребра (до вершин и ) с весом, равным 7, инцидентны вершине . Присоединяем их.
К вершине присоединяем ребро с весом 5 до вершины . К вершине присоединяем ребро с весом 4 до вершины . К вершине присоединяем ребро с весом 6 до вершины .
Получаем следующее минимальное корневое дерево с весом, равным _min(T)=7+7+6+5+4=29. Высота дерева = 3.
Задача 2: Задача о нахождении дерева кратчайших расстояний – нахождение кратчайшего пути из одной вершины в любую другую.
Пусть дан ориентированный связный граф со взвешенными ребрами. Вес ребра (x_i,x_j) обозначим c_ij.
Требуется найти в заданном графе путь, соединяющий две заданные вершины и доставляющий минимум или максимум суммарного веса входящих в него рёбер. Чаще всего эта функция трактуется как длина пути, и задача называется задачей о кратчайших путях.
Для решения этой задачи применяется алгоритм Дейкстры (Голландия, 1930-2002), реализующий принцип динамического программирования: сведение данной задачи к аналогичной, имеющей меньшую размерность так, чтобы её решение являлось частью решения большей задачи.
Суть алгоритма: начиная с исходной вершины (вес = 0), добавлять к пути по одной вершины, определяя её вес (метку) как расстояние до неё от исходной вершины через уже добавленные, возможно, меняя их вес.
После обработки всех вершин путь строится от конечной вершины по рёбрам, дающим соответствующий вес.


Контрольные задания.

1. 
   Определить цикломатическое число и максимальный тип вершин.
   

2. 
   Найти остов минимального веса.
   

5

1

6

3

2

2

3

4

3. 
   Найдите количество остовных подграфов, являющихся деревьями, в полных подграфах с 3-мя, 4-мя, 5-ю, 6-ю вершинами.
   
4. 
   Нарисовать все попарно неизоморфные деревья восьмого порядка.
   
5. 
   Доказать, что центр дерева состоит из 1 вершины в случае, когда диаметр этого дерева четное число, и из 2-х смежный вершин, если диаметр – нечетное число.
   
6. 
   Нарисовать все попарно неизоморфные деревья седьмого порядка.
   
7. 
   Докажите, что если из каждой вершины графа выходит более одного ребра, то граф не является деревом.
   
8. 
   Докажите, что у дерева всегда найдется вершина, из которой выходит ровно одно ребро. (Такая вершина называется висячей)
   
9. 
   Докажите, что если у графа-дерева удалить висячую вершину вместе с ребром, из нее выходящим, то полученный граф снова будет деревом.
   
10. 
    На конференции присутствуют 50 ученых, каждый из которых знаком, по крайней мере, с 25 участниками конференции. Докажите, что найдутся четверо из них, которых можно усадить за круглый стол так, чтобы каждый сидел рядом со знакомыми ему людьми.
    
11. 
    В некоторой стране любые два города соединены либо авиалинией, либо железной дорогой. Докажите, что а) можно выбрать вид транспорта так, чтобы от любого города можно было добраться до любого другого, пользуясь только этим видом транспорта;
    

б) из некоторого города, выбрав один из видов транспорта, можно добраться до любого другого города не более, чем с одной пересадкой (пользоваться можно только выбранным видом транспорта) в) можно выбрать вид транспорта так, чтобы пользуясь только им, можно было добраться из любого города до любого другого не более, чем с двумя пересадками.

12. 
    Дима, приехав из Врунляндии, рассказал, что там есть несколько озер, соединенных между собой реками. Из каждого озера вытекают три реки, и в каждое озеро впадают четыре реки. Докажите, что он ошибается.
    
13. 
    В некоторой стране есть столица и еще 100 городов. Некоторые города (в том числе и столица) соединены дорогами с односторонним движением. Из каждого нестоличного города выходит 20 дорог, и в каждый город входит 21 дорога. Докажите, что в столицу нельзя проехать ни из одного города.
    
14. 
    В некотором городе каждый город соединен с каждым дорогой. Сумасшедший король хочет ввести на дорогах одностороннее движение так, чтобы выехав из любого города, в него нельзя было вернуться. Можно ли так сделать?
    
15. 
    Докажите, что на ребрах связного графа можно расставить стрелки так, чтобы из некоторой вершины можно было добраться по стрелкам до любой другой.
    
16. 
    В связном графе степени всех вершин четны. Докажите, что на ребрах этого графа можно расставить стрелки так, чтобы выполнялись следующие условия: а) двигаясь по стрелкам, можно добраться от любой вершины до любой другой; б) для каждой вершины числа входящих и исходящих ребер равны.
    
17. 
    В одном государстве 100 городов и каждый соединен с каждым дорогой с односторонним движением. Докажите, что можно поменять направление движения на одной дороге так, чтобы от любого города можно было доехать до любого другого.