Презентация "Графы. Поиск путей в графе" 11 класс

Скачать материал

Подписи к слайдам:

ГРАФЫ.

ПОИСК ПУТЕЙ В ГРАФЕ.

Автор: Сергеенкова И.М.,

ГБОУ Школа № 1191, г. Москва

Граф и его элементы. Основные понятия.

Граф – это совокупность объектов со связями между ними.

Объекты рассматриваются как вершины, или узлы графа,

а связи – как дуги, или ребра.

Ребро графа называется дугой, если одна из его вершин считается начальной, другая – конечной.

Основные элементы графа состоят из вершин графа, ребер графа и дуг графа. Сочетание этих элементов определяет понятия: неориентированный граф, ориентированный граф и смешанный граф.

Дуга графа

ребро графа

Вершина

графа

Вершина

графа

Вершина

графа

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

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

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

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

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

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

Задачи на поиск путей в Графе

Задача 1.

На рисунке – схема дорог, связывающих города A, B, C, D, E, F, G, H, K, L, M. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города A в город M?

Решение

Решение задачи 1.

Начнем считать количество путей с конца маршрута – с города М.

NX — количество различных путей из города А в город X, N — общее число путей. В "М" можно приехать из C, F, L или H, поэтому

N = NM = NC + NF + N H + N L (1)

2. Аналогично:

NC = NB;

NF = NE;

NH = NF + NG;

NL = NK.

3. Добавим еще вершины:

NB = NA = 1;

NE = NB + NA + NG = 1 + 1 + 2 = 4;

NG = NA + NK = 1 + 1 = 2;

NK = NA = 1.

4. Преобразуем вершины:

NC = NB = 1;

NF = NE = 4;

NH = NF + NG = 4 + 2 = 6;

NL = NK = 1.

5. Подставим в формулу (1):

N = NК = 1 + 4 + 6 + 1 = 12

Ответ: 12

Задача 2.

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

Сколько существует различных путей из города А в город И?

Решение

Решение задачи 2.

1. Начнем считать количество путей с конца маршрута – с города И. NX — количество различных путей из города А в город 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

Задача 3.

На рисунке изображена схема дорог, связывающих города A, B, C, D, E, F, G, H, K, L, M. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города A в город M?

Решение

Решение задачи 3.

1. Начнем считать количество путей с конца маршрута — с города M. Пусть NX — количество различных путей из города А в город X, N — общее число путей. В город M можно приехать из L, G, F, H или K, поэтому N = NM = NL + NG+NF+ NH + NK;(*)

2.Аналогично:

NL = NF+ NG = 5 + 5 = 10;

NG = NF = 5;

NH = NF = 5;

NK = NF + NE + NH = 5 + 1 + 5 = 11;

NF = NA + NB + NC + ND + NE = = 5.

3. Добавим еще вершины:

NB = NA = 1;

NC = NA = 1;

ND = NA = 1;

NE = NA = 1.

4. Подставим в формулу :

N = NM = 10 + 5 + 5 + 11 + 5 = 36.

Ответ: 36.

Решите самостоятельно:

1).

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города А в город Л?

Ответ: 30