Автор: Сергеенкова И.М., ГБОУ Школа 1191, г. Москва Автор: Сергеенкова И.М., ГБОУ Школа 1191, г. Москва

Граф и его элементы. Основные понятия. Граф – это совокупность объектов со связями между ними. Объекты рассматриваются как вершины, или узлы графа, а связи – как дуги, или ребра. Ребро графа называется дугой, если одна из его вершин считается начальной, другая – конечной. Основные элементы графа состоят из вершин графа, ребер графа и дуг графа. Сочетание этих элементов определяет понятия: неориентированный граф, ориентированный граф и смешанный граф. А Б В Дуга графа ребро графа Вершина графа Вершина графа Вершина графа

Неориентированный граф – это граф, для каждого ребра которого несуществен порядок двух его конечных вершин.

Ориентированный граф – это граф, для каждого ребра которого существенен порядок двух его конечных вершин. Пара вершин может соединяться двумя или более ребрами (дугами одного направления), такие ребра называются кратными.

Смешанный граф – это граф, содержащий как ориентированные, так и неориентированных ребра. Любой из перечисленных видов графа может содержать одно или несколько ребер, у которых оба конца сходятся в одной вершине, такие ребра называются петлями. Путем в графе называют конечную последовательность вершин, в которой каждая вершина соединена ребром с последующей в последовательности вершин. Длиной пути во взвешенном графе называют сумму длин звеньев этого пути. Количество k ребер в пути называется длиной пути. Путь называют циклом, если в нем первая и последняя вершины совпадают

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. 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 = = 4; N G = N A + N K = = 2; N K = N A = 1.

4. Пре­об­ра­зу­ем вер­ши­ны: N C = N B = 1; N F = N E = 4; N H = N F + N G = = 6; N L = N K = Под­ста­вим в фор­му­лу (1): N = N К = = 12 B A K C E G F H L M Ответ: 12

Задача 2. На ри­сун­ке – схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В, Г, Д, Е, Ж, З, И. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­ прав­ле­нии, ука­зан­ном стрел­кой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да А в город И? Решение AИ Б Д В Ж З ЕГ

Решение задачи Нач­нем счи­тать ко­ли­че­ство путей с конца марш­ру­та – с го­ро­ да И. 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 Г = = 2; N Е = N В + N Г = = 3; N Г = N А = 1.

4. Пре­об­ра­зу­ем пер­вые вер­ши­ны с уче­то зна­че­ний вто­рых: N Д = N Б = 1; N Ж = N Б + N В + N Е = = 6; N З = N Ж + N Е = = Под­ста­вим в фор­му­лу (1): N = N К = = 16. Ответ: 16 A 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

Решение задачи Нач­нем счи­тать ко­ли­че­ство путей с конца марш­ру­та с го­ро­ да 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 = = 10; N G = N F = 5; N H = N F = 5; N K = N F + N E + N H = = 11; N F = N A + N B + N C + N D + N E = = До­ба­вим еще вер­ши­ны: N B = N A = 1; N C = N A = 1; N D = N A = 1; N E = N A = Под­ста­вим в фор­му­лу : N = N M = = 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 M А А

Источники информации: 1. gif