Графы

Практическое занятие 1.1 Графы. Преподаватель: Зиганшина Айгуль Раисовна Определения Графом называется совокупность точек (объектов) и соединяющих их линий (связей). Точки графа при этом называются его вершинами, а связывающие их линии – рёбрами. Определения A B C D E A, C, A, D – маршрут, но не цепь A, C, E, B, C, D – цепь A, D, C, B, E – простая цепь Маршрутом в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершиной ребром. Цепью называется повторяющихся рёбер. маршрут без Простой цепью называется маршрут без повторяющихся вершин (в простой цепи нет повторяющихся рёбер). Определения Количество ребер, выходящих из вершины графа, называется степенью вершины. Вершина графа, имеющая степень, называется нечетной. нечетную Четная степень Вершина графа, имеющая четную степень, называется четной. Граф называется конечным, множество его ребер конечно. если Нечетная степень Определения Связный граф - это граф, между любой парой вершин которого существует хотя бы один путь. Несвязный граф - это граф, в котором существует хотя бы одна пара вершин, между которыми нет пути. Коне Связный граф Несвязный граф Эйлеров цикл 6 2 5 3 4 1 8 7 9 10 11 Каждая вершина этого графа имеет чётную степень, поэтому этот граф — эйлеров. Обход рёбер в порядке возрастания даёт эйлеров цикл. В любом конечном связном графе, все вершины которого четны, существует цикл, в котором каждое ребро графа участвует ровно один раз. Такой цикл называют эйлеровым циклом, а граф, все вершины которого четны, - эйлеровым графом. Условия существования эйлерова цикла 6 2 5 3 4 1 8 7 9 10 11 Каждая вершина этого графа имеет чётную степень, поэтому этот граф — эйлеров. Обход рёбер в порядке возрастания даёт эйлеров цикл. Условия существования эйлерова цикла : 1. Сеть, не имеющая нечётных вершин, допускает эйлеров цикл с началом в любой точке сети. 2. Сеть, имеющая две и только две нечётных вершины, обходится по эйлеровому пути, если начать движение с одной нечётной вершины и закончить его в другой. 3. Сеть, имеющую больше двух нечётных вершин, нельзя полностью обойти одним маршрутом. Задача о семи Кенигсбергских мостах Как пройти по всем городским мостам Кёнигсберга (через реку Прегель не проходя ни по одному из мостов дважды? Решение Кёнигсбергская сеть имеет 4 вершины, в каждой из которых сходится нечётное число дугмостов: все вершины – нечётные (N для них равны 3,3,3 и 5), следовательно, требуемого маршрута – не существует. Этот граф не эйлеров. Задача 1 Торговец, живущий в городе А, намерен посетить города В, C, D, расстояния между которыми ему известны: AB=11, CD=10. AC=13, AD=17, BC=6, BD=9, Требуется указать кратчайший циклический маршрут из города А, проходящий через три других города. B A D C Решение Возможных циклических маршрутов 6: ABCDA, ACDBA, ADBCA, ACBDA, ABDCA, ADCBA. B D A C Найдем первые три длины: ABCDA =11+6+10+17=44 ACDBA =13+10+9+11=43 ADBCA = 17+9+6+13=45 Значит, кратчайшим является либо ACDBA или ABDCA = 43. Деревья Важный класс графов составляют деревья. Деревом называется связный граф, который не имеет циклов. Число вершин (В) дерева и число его ребер (Р) различаются на единицу. В2 В4 Р3 В1 Р1 Р2 В3 В5 Р4 В=Р+1 Задача 2 Пусть пять пунктов pi (i=1,…,5) требуется соединить коммуникациями, если стоимость (в условных единицах) каждого из участков дана следующими числами: q12=20, q13=15, q14=25, q15=30, q23=17, q24=22, q25=20, q34=10, q35=31, q45=29. Требуется построить «экономичное дерево», минимизирующее сумму расстояний между вершинами связного графа. 2 4 1 3 5 Решение I. На первом этапе строится ребро, которое является наиболее дешёвым. Им является отрезок, соединяющий p3 и p4. Одна из этих точек может стать корнем дерева. p3 10 p4 Решение II. На втором – определяется и строится точка, имеющая наименьшее из значений q3i и q4i (i = 1, 2, 5). Так как наименьшим из этих значений является q31 = 15, то очевидно, что к имеющемуся отрезку пристраиваются точка p1 и ребро p1p3. 10 p3 15 p1 p4 Решение III. Затем сравниваются стоимости qlj (j = 2,5 , l = 1,3,4). Наименьшим из них является q32=17. Таким образом, к предыдущему графу добавляется ребро р2р3. 10 p3 15 p1 17 p2 p4 Решение IV. Наконец, сопоставляя значения q5k (k = 1,…,4), определяем наименьшее из них: q52 = 20. Это позволяет изображением ребра p2p5 завершить построение графа коммуникационной сети. Стоимость её строительства Q = q34 + q13 + q23 + q25 = 10 + 15 + 17 + 20 = 62 условных единиц. 10 p3 15 p1 p4 17 p2 20 p5 Задача 3 Шахматный турнир проводится по круговой системе, при которой каждый участник встречается с другим участником ровно один раз . В турнире участвуют 7 школьников. Известно, что в настоящий момент: 1) Ваня сыграл 6 партий; 2) Толя сыграл 5 партий; 3) Леша и Дима сыграли по 3 партии; 4) Семен и Илья сыграли по 2 партии; 5) Женя сыграл 1 партию. Требуется определить с кем из участников сыграл в шахматы Леша. Решение Толя (5) Леша (3) Ваня (6) Изобразим участников турнира точками. Для каждой точки укажем ее Дима (3) имя и количество партий, сыгранных этим игроком. Семен (2) Женя (1) Илья (2) Число в скобках – это степень вершины, оно показывает сколько ребер выходит из данной вершины. Решение Толя (5) Леша (3) Ваня (6) Дима (3) Семен (2) Женя (1) Илья (2) Построим ребра графа с учетом степеней вершин. Начать построение следует с вершины В, так как это единственная вершина, которая соединяется со всеми другими вершинами графа. Решение Толя (5) Леша (3) Ваня (6) Дима (3) Семен (2) Женя (1) Илья (2) Для вершин В и Ж построены все возможные ребра. Решение Толя (5) Леша (3) Ваня (6) Дима (3) Семен (2) Женя (1) Илья (2) С учетом ребра ВТ, строим оставшиеся 4 ребра. Решение Толя (5) Леша (3) Ваня (6) Дима (3) Семен (2) Женя (1) Илья (2) Все возможные ребра построены для вершин: Ж, В, Т, И, С. Решение Толя (5) Леша (3) Ваня (6) Дима (3) Леша сыграл в шахматы с: Толей, Ваней и Димой. Семен (2) Женя (1) Илья (2) Спасибо за внимание! Тема следующего практического занятия: Сети