Теория задания № 4

РАЗБОР ЗАДАНИЙ ПЕРВОЙ ЧАСТИ ЭКЗАМЕНА

Теория по заданию 4

ПОИСК КРАТЧАЙШЕГО ПУТИ

Граф — это математическая структура, которая используется для моделирования связей между различными объектами. Она состоит из вершин и рёбер, которые их соединяют.

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

Ориентированный граф – это граф, у которого все ребра имеют направление (стрелочки)

Стрелки показывают от какой вершины и до какой можно пройти по этому ребру.
Неориентированный граф – это граф, у которого все рёбра не имеют направления (просто линии, без стрелочек).
Ребро просто соединяет две вершины, и движение по нему возможно в обе стороны.

Неориентированный граф:
дороги двусторонние

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

Обычный граф:
Есть только дороги.

Взвешенный граф:
У каждой дороги есть длинна.
Дерево – структура данных, которая выглядит как перевёрнутое дерево.
Ключевые свойства: между любыми двумя пунктами (вершинами) есть ровно один путь по цепочке команд.
Граф с циклами – это граф, в котором можно, начав с одной вершины и пройдя по рёбрам, вернуться обратно в неё же.
В графе с циклами есть круговые маршруты.
Проходящий граф – это граф, в котором можно пройти по всем вершинам, посетив каждую только один раз.
Это не про рёбра, а именно про вершины.

Ориентированный граф
Неориентированный граф
Взвешенный граф

Дерево
Граф с циклами
Проходящий граф

Вариант решения задания не строя граф.

Рассмотрим на примере:

Найдите самый короткий путь из вершины А в вершину Е (в ответе только число).

1. Отметим вершины, которые нас интересуют по заданию (А и Е):

2. Постараемся избегать самые длинные пути:

Получилось, что мы избавились от путей АБ (17) и БЕ (19).

3. Отметим для себя самые выгодные пути и будем ориентироваться на них:

Получилось, что из вершины А осталась одна дорога в В (АВ=3), из В дорога идёт в Г (ВГ=7) и далее из Г в Д (ГД=6), а из Д дорога идёт уже в Е (ДЕ=2). Конечный минимальный путь из А в Е – это АВГДЕ=3+7+6+2=18. Обязательно проверяем, что остальные пути не длиннее пути АВГДЕ. В итоге ответом является 18.

Теория ясна, приступим к практике.

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

1.Между населенными пунктами А, В, С, D, Е, F построены дороги, протяженность которых приведена в таблице:

A
B
C
D
E
F
A

2
5

7
B
2

2
1

5
C
5
2

1

D

1

E

1

2
F
7
5

2

Определите длину кратчайшего пути между пунктами А и F. Передвигаться можно только по дорогам, протяженность которых указана в таблице.
Ответ:
2.Между населенными пунктами А, В, С, D, Е, F построены дороги, протяженность которых приведена в таблице:

A
B
C
D
E
F
A

2
1

B

1

3
C
2
1

4
D
1

1
4
E

1

5
F

3
4
4
5

Определите длину кратчайшего пути между пунктами А и F (при условии, что передвигаться можно только по построенным дорогам).
Ответ:
3.Между населенными пунктами A, B, C, D, E построены дороги, протяженность которых в (километрах) приведена в таблице:

A
B
C
D
E
A

1
2

4
B
1

4

C
2
4

1
D

4
E
4

1
4

Определите длину кратчайшего пути между пунктами B и D. Передвигаться можно только по дорогам, протяженность которых указана в таблице. Каждый пункт можно посетить только один раз.
Ответ:
4.Между населенными пунктами A, B, C, D, E построены дороги, протяженность которых (в километрах) приведена в таблице:

A
B
C
D
E
A

2
4

6
B
2

1

C
4
1

5
1
D

5

3
E
6

1
3

Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, протяженность которых указана в таблице. Каждый пункт можно посетить только один раз.
Ответ:
5.Между населенными пунктами А, В, С, D, Е построены дороги, протяженность которых (в километрах) приведена в таблице:

A
B
C
D
E
A

3
7

B
3

2

8
C
7
2

4

D

4

1
E

8

1

Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяженность которых указана в таблице.
Ответ:

посмотреть решения и ответы на практические задания

перейти к списку заданий