ГРАФЫ. ПОИСК ПУТЕЙ В ГРАФЕ.
Граф и его элементы. Основные понятия. Граф – это совокупность объектов со связями между ними. Объекты рассматриваются как вершины, или узлы графа, а связи – как дуги, или ребра. Ребро графа называется дугой, если одна из его вершин считается начальной, другая – конечной. Основные элементы графа состоят из вершин графа, ребер графа и дуг графа. Сочетание этих элементов определяет понятия: неориентированный граф, ориентированный граф и смешанный граф. А Б В Дуга графа Дуга графа ребро графа Вершина графа Вершина графа Вершина графа
Неориентированный граф – это граф, для каждого ребра которого несуществен порядок двух его конечных вершин. 1 2 5 4 3 6
Ориентированный граф – это граф, для каждого ребра которого существенен порядок двух его конечных вершин. Пара вершин может соединяться двумя или более ребрами (дугами одного направления), такие ребра называются кратными. 1 2 3 5 4
Смешанный граф – это граф, содержащий как ориентированные, так и неориентированных ребра. Любой из перечисленных видов графа может содержать одно или несколько ребер, у которых оба конца сходятся в одной вершине, такие ребра называются петлями. Путем в графе называют конечную последовательность вершин, в которой каждая вершина соединена ребром с последующей в последовательности вершин. Длиной пути во взвешенном графе называют сумму длин звеньев этого пути. Количество k ребер в пути называется длиной пути. Путь называют циклом, если в нем первая и последняя вершины совпадают. 5 2 1 4 3 5 2 1 4 3
12 Задачи на поиск путей в Графе Задача 1. На рисунке – схема дорог, связывающих города A, B, C, D, E, F, G, H, K, L, M. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город M ? Решение B A K C E G F H L M
Решение задачи 1. Начнем считать количество путей с конца маршрута – с города М. N X — количество различных путей из города А в город X, N — общее число путей. В "М" можно приехать из C, F, L или H, поэтому N = N M = N C + N F + N H + N L (1 ) C F H L M
2. Аналогично: N C = N B ; N F = N E ; N H = N F + N G ; N L = N K. C F H L M B E G K A 3. Добавим еще вершины: N B = N A = 1; N E = N B + N A + N G = 1 + 1 + 2 = 4 ; N G = N A + N K = 1 + 1 = 2; N K = N A = 1.
4. Преобразуем вершины: N C = N B = 1; N F = N E = 4 ; N H = N F + N G = 4 + 2 = 6; N L = N K = 1. 5. Подставим в формулу (1): N = N К = 1 + 4 + 6 + 1 = 12 B A K C E G F H L M Ответ : 12
Задача 2. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город И? Решение A И Б Д В Ж З Е Г
Решение задачи 2. 1. Начнем считать количество путей с конца маршрута – с города И. N X — количество различных путей из города А в город X, N — общее число путей. В "И" можно приехать из Д, Ж, или З, поэтому N = N И = N Д + N Ж + N З (1 ) Д Ж З И
2. Аналогично: N Д = N Б ; N Ж = N Б + N В + N Е ; N З = N Ж + N Е. Д Ж З И 3.. Добавим еще вершины: N Б = N А = 1; N В = N А + N Г = 1 + 1 = 2; N Е = N В + N Г = 2 + 1 = 3; N Г = N А = 1. Б В Е Г А
4. Преобразуем первые вершины с учето значений вторых: N Д = N Б = 1; N Ж = N Б + N В + N Е = 1 + 2 + 3 = 6 ; N З = N Ж + N Е = 6 + 3 = 9. 5. Подставим в формулу (1): N = N К = 1 + 6 + 9 = 16. Ответ : 16 A И Б Д В Ж З Е Г
Задача 3. На рисунке изображена схема дорог, связывающих города A, B, C, D, E, F, G, H, K, L, M. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город M? Решение B C D E F L G H K M A
Решение задачи 3. 1. Начнем считать количество путей с конца маршрута — с города M. Пусть N X — количество различных путей из города А в город X, N — общее число путей. В город M можно приехать из L, G, F, H или K, поэтому N = N M = N L + N G +N F + N H + N K ;(*) 2.Аналогично: N L = N F + N G = 5 + 5 = 10; N G = N F = 5; N H = N F = 5; N K = N F + N E + N H = 5 + 1 + 5 = 11; N F = N A + N B + N C + N D + N E = = 5. 3. Добавим еще вершины: N B = N A = 1; N C = N A = 1; N D = N A = 1; N E = N A = 1. 4. Подставим в формулу : N = N M = 10 + 5 + 5 + 11 + 5 = 36. Ответ : 36.
Решите самостоятельно: 1). На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л? Ответ: 30 B E Б Д Е Г Ж К Л A
2). На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж? Ответ: 11 А Б Е Д Ж В Г
3). На рисунке изображена схема дорог, связывающих города A, B, C, D, E, F, G, H, K, L, M. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город M ? Ответ: 12 А М H B C D E K L F G
Задание на дом: На рисунке изображена схема дорог, связывающих города A, B, C, D, E, F, G, H, K, L, M. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город M ? B C D E F G H K L M А
Источники информации: http:// www.compress.ru/Archive/CP/2007/1/18/10.gif http:// kpolyakov.narod.ru/school/ege.htm http :// inf.reshuege.ru/test?theme=203 http:// inf.reshuege.ru/get_file?id=3029
