double arrow

A3 (базовый уровень, время – 3 мин)

1

Тема: Умение анализировать формальные описания реальных объектов и процессов.

Что нужно знать:

· если объекты некоторой системы отобразить вершинами, а связи между ними – линиями (ребрами), то получим граф;

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

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

· по взвешенному графу может быть построена таблица (весовая матрица).

       
 
   
 

  A B C D Е
A          
B          
C          
D          
Е          

Задача 1:

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

  A B C D Е F
A            
B            
C            
D            
Е            
F            

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

1) 9 2) 11 3) 13 4) 15

Решение:

1) Для удобства отобразим табличные данные в виде графа. Для этого на листе расставляем точки — населенные пункты. В соответствии с таблицей соединяем их и подписываем расстояния.

2) Переберем все возможные пути из A в F:

A-B-C-E-F = 3+3+2+7 = 15

A-B-C-D-F = 3+3+5+3 = 14

A-C-E-F = 5+2+7 = 14

A-C-D-F = 5+5+3 = 13

A-F = 15

Как видно, кратчайший вариант A-C-D-F = 13 км.

ВНИМАНИЕ: Чтобы не запутаться, рекомендуется перебирать пункты в алфавитном порядке.


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  


1

Сейчас читают про: