КЭС 2.11 Граф. Вершина, ребро, путь. Ориентированные и неориентированные графы. Длина (вес) ребра. Весовая матрица графа. Длина пути между вершинами графа. Поиск оптимального пути в графе. Начальная вершина (источник) и конечная вершина (сток) в ориентированном графе. Вычисление количества путей в направленном ациклическом графе
2.12 Дерево. Корень, вершина (узел), лист, ребро (дуга) дерева. Высота дерева. Поддерево. Примеры использования деревьев. Перебор вариантов с помощью дерева
Тип ответа: краткий ответ
Задание 4 ОГЭ по информатике и ИКТ предлагает определить длину кратчайшего пути между двумя пунктами. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз. В таблице указаны расстояния от пункта до пункта. К примеру, цифра на пересечении А и В означает расстояние от А до В. Если не указано - то пункты не соединяются напрямую.
Если выражаться на языке информатике, перед нами матрица смежности, в которой хранится информация о ребрах графа. Можно представить матрицу в виде взвешенного графа (схемы), подписать ребра графа (протяженность дороги) и найти кратчайший путь.
Соблюдайте пропорции, когда это возможно, но это возможно не всегда, потому что на деле расстояния даны не по прямой, а чертить легче прямые отрезки. Так будет проще найти самый короткий путь. Затем пытаемся идти, собирая самые короткие дороги (ребра графа). Некоторые пути можно сразу исключить, останется только дорога с минимальной протяженностью.
Вот варианты задания, которые могут вам попасться на реальном экзамене в этом году.
Варианты задания 4 ОГЭ от ФИПИ
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
- |
A |
B |
C |
D |
E |
F |
|
A |
- |
3 |
5 |
|
|
15 |
|
B |
3 |
- |
1 |
4 |
|
|
|
C |
5 |
1 |
- |
2 |
|
9 |
|
D |
|
4 |
2 |
- |
3 |
6 |
|
E |
|
|
|
3 |
- |
4 |
|
F |
15 |
|
9 |
6 |
4 |
- |
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт С. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Решение:
По таблице видим, что пункт А соединяется напрямую с В, С и F (между ними указано расстояние).
B дополнительно с C, D.
C дополнительно с D, F
D - с E, F
E - с F
Начертим схему дорог и подпишем расстояния из таблицы. Получаем такой взвешенный граф:
Идем из А через С, собирая самые короткие дороги до F.
Некоторые пути можно сразу исключить. Например, от А до С короче через В, тогда путь AC не используем (зачеркиваем). BD тоже вычеркиваем, так как ВС уже задействовали. Из D до F короче напрямую, значит DEF не используем. AF не проходит через С, вычеркиваем.
ABCDF = AB + BC + CD + DF = 3 + 1 + 2 + 6 = 12 км - это и есть кратчайший путь
Ответ: 12
Второй вариант схемы
Сначала рисуем маршрут по минимальным числам в таблице (красная линия). Затем дополняем возможными путями.
Не ленитесь, подпишите все расстояния, будет нагляднее!
В точку С можно добраться по АС или АВС.
АС = 5, АВС = 3 + 1 = 4
Из С в F пути:
СF = 9
СDЕF = 2 + 3 + 4 = 9
СDF = 2 + 6 = 8
Значит, кратчайший путь через С - это АВСDF = 8 + 4 = 12 км
Ответ: 12
E6DE46
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
F |
|
A |
|
3 |
5 |
|
|
15 |
|
B |
3 |
|
1 |
4 |
|
|
|
C |
5 |
1 |
|
2 |
|
9 |
|
D |
|
4 |
2 |
|
3 |
6 |
|
E |
|
|
|
3 |
|
2 |
|
F |
15 |
|
9 |
6 |
2 |
|
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт С. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Решение:
Подпишите длины отрезков из таблицы, так легче будет сориентироваться.
Пытаемся идти, собирая самые короткие дороги.
Некоторые пути можно сразу исключить. Например, от А до С короче через В, тогда путь AC не используем (зачеркиваем). От В до D короче через C, а не напрямую с B, тогда BD тоже вычеркиваем. Из D до F короче через Е, значит DF не используем. AF через С не проходит.
ABCDЕF = AB + BC + CD + DЕ + ЕF = 3 + 1 + 2 + 3 + 2 = 11 км - это и есть кратчайший путь
Ответ: 11
4EBE73
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
3 |
9 |
8 |
9 |
|
B |
3 |
|
|
4 |
|
|
C |
9 |
|
|
2 |
2 |
|
D |
8 |
4 |
2 |
|
5 |
|
E |
9 |
|
2 |
5 |
|
Определите длину кратчайшего пути между пунктами A и E, проходящего через пункт D. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Решение:
Подпишите длины отрезков из таблицы, так легче будет сориентироваться.
Пытаемся идти из A в E, собирая самые короткие дороги, но обязательно через пункт D.
Путь АD=8 исключаем, он длиннее, чем АВD=3+4=7.
DЕ=5 исключаем, он длиннее, чем DСЕ=2+2=4
Остался АВDСЕ = 3 + 4 + 2 + 2 = 11 км
Ответ: 11
B4AE72
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
5 |
6 |
5 |
3 |
|
B |
5 |
|
|
4 |
|
|
C |
6 |
|
|
2 |
2 |
|
D |
5 |
4 |
2 |
|
5 |
|
E |
3 |
|
2 |
5 |
|
Определите длину кратчайшего пути между пунктами A и D, проходящего через пункт С. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Решение:
Не ленитесь, подпишите все расстояния, будет нагляднее!
У нас по схеме через точку С 3 пути.
Рассмотрим их.
ACD=6+2=8
AECD=3+2+2=7
ACED=6+2+5=13
AECD - самый короткий
Ответ: 7
9ABCB7
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
F |
|
A |
|
1 |
2 |
|
|
15 |
|
B |
1 |
|
3 |
4 |
|
|
|
C |
2 |
3 |
|
1 |
|
6 |
|
D |
|
4 |
1 |
|
2 |
6 |
|
E |
|
|
|
2 |
|
1 |
|
F |
15 |
|
6 |
6 |
1 |
|
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт С. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Решение:
Подпишите длины отрезков из таблицы, так легче будет сориентироваться.
Пытаемся идти, собирая самые короткие дороги
Сначала путь до С.
АС=2, это короче, чем АВС=1+3=4
Теперь варианты с С до F
СF=6
CDF=1+6=7
CDEF=1+2+1=4, короткий получился равен 4.
Тогда АCDEF=2+4=6
Ответ: 6
0D2DD9
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
5 |
9 |
6 |
9 |
|
B |
5 |
|
|
3 |
|
|
C |
9 |
|
|
2 |
2 |
|
D |
6 |
3 |
2 |
|
5 |
|
E |
9 |
|
2 |
5 |
|
Определите длину кратчайшего пути между пунктами A и E, проходящего через пункт D. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Решение:
Рассмотрим пути.
АD=6 это самый короткий путь до точки D, так как AC=9, что больше 6 и AB=5, что точно не меньше будет 6, даже если следующее звено до D будет равно минимальному 1.
Теперь рассмотрим пути от D до E.
DE=5
Через С будет DСЕ=2+2=4 , это меньше 5.
Значит, короткий путь будет АDСЕ=6+4=10
Ответ: 10
AEBD50
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
3 |
9 |
8 |
9 |
|
B |
3 |
|
|
4 |
|
|
C |
9 |
|
|
3 |
2 |
|
D |
8 |
4 |
3 |
|
2 |
|
E |
9 |
|
2 |
2 |
|
Определите длину кратчайшего пути между пунктами A и E, проходящего через пункт D. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Решение:
До точки D
АВD=3+4=7 - это самый короткий путь.
Теперь рассмотрим пути от D до E.
DЕ=2
Через С будет DСЕ=3+2=5 , это больше 2.
Значит короткий путь будет
АВDЕ=7+2=9
Ответ: 9
1C05C9
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
F |
|
A |
|
3 |
4 |
|
|
15 |
|
B |
3 |
|
3 |
4 |
|
|
|
C |
4 |
3 |
|
1 |
|
6 |
|
D |
|
4 |
1 |
|
2 |
6 |
|
E |
|
|
|
2 |
|
1 |
|
F |
15 |
|
6 |
6 |
1 |
|
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт С. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Решение:
Подпишите длины отрезков из таблицы, так легче будет сориентироваться.
Пытаемся идти, собирая самые короткие дороги.
Сначала путь до С.
АС=4, а ABC=3+3=6, то есть выбираем АС.
Теперь от С до F.
ACF =4+6=10
CDF=1+6=7.
СDЕF=1+2+1=4Получается АСDЕF=4+4=8 самый короткий.
Ответ: 8
E66A35
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
2 |
4 |
|
5 |
|
B |
2 |
|
1 |
|
|
|
C |
4 |
1 |
|
4 |
3 |
|
D |
|
|
4 |
|
3 |
|
E |
5 |
|
3 |
3 |
|
Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
По таблице А соединяется с В, С, Е; В дополнительно с С; С дополнительно с D, Е; D с Е.
Из таблицы
АВ = 2 ВС = 1
АС = 4 СD = 4
АЕ = 5 CЕ = 3
DЕ = 3
Подпишите длины отрезков у себя на рисунке, чтобы не запутаться.
Можно исключить АС, так как в точку С можно попасть быстрее через АВС; если идете из С, исключите крюк СЕD, так как дорога СD меньше.
Осталось проверить только 2 пути:
АЕD = 5 + 3 = 8 км
АВСD = 2 + 1 + 4 = 7 км - кратчайший путь
Ответ: 7
44E848
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
F |
|
A |
|
3 |
|
|
|
15 |
|
B |
3 |
|
2 |
3 |
7 |
|
|
C |
|
2 |
|
1 |
3 |
|
|
D |
|
3 |
1 |
|
1 |
|
|
E |
|
7 |
3 |
1 |
|
2 |
|
F |
15 |
|
|
|
2 |
|
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт C. Передвигаться можно только по дорогам, указанным
в таблице. Каждый пункт можно посетить только один раз.
Решение:
A выходит только на B, поэтому будем искать путь к С через B.
ABC=3+2=5.
Другие варианты с B до С не рассматриваем, так как они больше 2.
Теперь с С до F.
CDEF=1+1+2=4
CEF=3+2=5
Самый короткий путь ABCDEF=5+4=9
Ответ:9
FAEF44
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
8 |
|
|
5 |
|
B |
8 |
|
|
3 |
3 |
|
C |
|
|
|
2 |
1 |
|
D |
|
3 |
2 |
|
|
|
E |
5 |
3 |
1 |
|
|
Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
Рассмотрим варианты, берем в строках минимальные значения, также не переходим в альтернативных вариантах в точки уже рассмотренные в предыдущих вариантах решения на предмет короткого пути.
AB = 8
BD = 3
ABD=8+3=11
AE = 5
EC = 1
CD=2
AECD=5+1+2=8
Ответ: 8
77024A
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице.
|
|
A |
B |
C |
D |
E |
F |
|
A |
|
8 |
3 |
|
|
|
|
B |
8 |
|
|
3 |
|
|
|
C |
3 |
|
|
|
4 |
3 |
|
D |
|
3 |
|
|
1 |
3 |
|
E |
|
|
4 |
1 |
|
2 |
|
F |
|
|
3 |
3 |
2 |
|
Определите длину кратчайшего пути между пунктами A и D (при условии, что передвигаться можно только по указанным в таблице дорогам). Каждый пункт можно посетить только один раз.
Решение:
Рассмотрим варианты, берем в строках минимальные значения, также не переходим в альтернативных вариантах в точки уже рассмотренные в предыдущих вариантах решения на предмет короткого пути.
ABD=8+3=11
ACFD=3+3+3=9 и через Е ACED 3+4+1=8
Ответ: 8
BF5B47
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
F |
|
A |
|
2 |
|
|
|
15 |
|
B |
2 |
|
2 |
3 |
6 |
|
|
C |
|
2 |
|
|
3 |
|
|
D |
|
3 |
|
|
2 |
|
|
E |
|
6 |
3 |
2 |
|
6 |
|
F |
15 |
|
|
|
6 |
|
Определите длину кратчайшего пути между пунктами A и F. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Решение:
Рассмотрим варианты, берем в строках минимальные значения, также не переходим в альтернативных вариантах в точки уже рассмотренные в предыдущих вариантах решения на предмет короткого пути.
AF=15
ABDEF=2+3+2+6=13
ABCE=2+2+3+6=13
ABEF=2+6+6=14
Ответ: 13
DFF144
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
2 |
|
|
1 |
|
B |
2 |
|
5 |
|
4 |
|
C |
|
5 |
|
2 |
1 |
|
D |
|
|
2 |
|
4 |
|
E |
1 |
4 |
1 |
4 |
|
Определите длину кратчайшего пути между пунктами B и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
Рассмотрим варианты, берем в строках минимальные значения, также не переходим в альтернативных вариантах в точки уже рассмотренные в предыдущих вариантах решения на предмет короткого пути.
BAED=2+1+4=7
BAECD=2+1+1+2=6
BAC=5+2=7
BED=4+4=8
Ответ: 6
DBEC47
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
4 |
|
|
1 |
|
B |
4 |
|
|
1 |
2 |
|
C |
|
|
|
4 |
|
|
D |
|
1 |
4 |
|
4 |
|
E |
1 |
2 |
|
4 |
|
Определите длину кратчайшего пути между пунктами A и C. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
Рассмотрим варианты, берем в строках минимальные значения, также не переходим в альтернативных вариантах в точки уже рассмотренные в предыдущих вариантах решения на предмет короткого пути.
ABDC=4+1+4=9
AEDC=1+4+4=9
AEBDC=1+2+1+4=8
Ответ: 8
556B44
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
2 |
5 |
1 |
|
|
B |
2 |
|
3 |
|
|
|
C |
5 |
3 |
|
3 |
2 |
|
D |
1 |
|
3 |
|
|
|
E |
|
|
2 |
|
|
Определите длину кратчайшего пути между пунктами A и Е. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
Рассмотрим варианты, берем в строках минимальные значения, также не переходим в альтернативных вариантах в точки уже рассмотренные в предыдущих вариантах решения на предмет короткого пути.
ABCE=2+3+2=7
ADCE=1+3+2=6
Ответ: 6
945043
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
3 |
5 |
|
|
|
B |
3 |
|
1 |
6 |
|
|
C |
5 |
1 |
|
4 |
1 |
|
D |
|
6 |
4 |
|
3 |
|
E |
|
|
1 |
3 |
|
Определите длину кратчайшего пути между пунктами A и D (при условии, что передвигаться можно только по указанным в таблице дорогам). Каждый пункт можно посетить только один раз.
Решение:
Рассмотрим варианты, берем в строках минимальные значения, также не переходим в альтернативных вариантах в точки уже рассмотренные в предыдущих вариантах решения на предмет короткого пути.
ABD=3+6=9
ABCD=3+1+4=8
ABCED=3+1+1+3=8
Ответ: 8
672944
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
1 |
4 |
3 |
7 |
|
B |
1 |
|
2 |
5 |
|
|
C |
4 |
2 |
|
3 |
|
|
D |
3 |
5 |
3 |
|
2 |
|
E |
7 |
|
|
2 |
|
Определите длину кратчайшего пути между пунктами A и Е, проходящего через пункт С. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
Рассмотрим варианты, берем в строках минимальные значения, также не переходим в альтернативных вариантах в точки уже рассмотренные в предыдущих вариантах решения на предмет короткого пути.
ABCDE =1+2+3+2=8
Ответ: 8
05E8F3
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
6 |
1 |
|
1 |
|
B |
6 |
|
|
1 |
|
|
C |
1 |
|
|
2 |
2 |
|
D |
|
1 |
2 |
|
1 |
|
E |
1 |
|
2 |
1 |
|
Определите длину кратчайшего пути между пунктами A и B, проходящего через пункт E (при условии, что передвигаться можно только по указанным
в таблице дорогам). Каждый пункт можно посетить только один раз.
Решение:
AEDB=1+1+1=3 остальные варианты можно не рассматривать, так как количество связей не может быть меньше, а показатели здесь минимальные.
Ответ: 3
27C7FD
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
F |
|
A |
|
3 |
1 |
2 |
6 |
|
|
B |
3 |
|
1 |
|
|
|
|
C |
1 |
1 |
|
|
|
|
|
D |
2 |
|
|
|
2 |
|
|
E |
6 |
|
|
2 |
|
3 |
|
F |
|
|
|
|
3 |
|
Определите длину кратчайшего пути между пунктами B и F. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
Рассмотрим варианты, берем в строках минимальные значения, также не переходим в альтернативных вариантах в точки уже рассмотренные в предыдущих вариантах решения на предмет короткого пути.
BCADEF=1+1+2+2+3=9
Ответ: 9
3E0BF2
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
F |
|
A |
|
3 |
5 |
|
|
15 |
|
B |
3 |
|
3 |
|
|
|
|
C |
5 |
3 |
|
5 |
2 |
|
|
D |
|
|
5 |
|
|
3 |
|
E |
|
|
2 |
|
|
7 |
|
F |
15 |
|
|
3 |
7 |
|
Определите длину кратчайшего пути между пунктами A и F. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Решение:
ACEF=5+2+7=14
ACDF=5+5+3=13
Ответ: 13
9CCA01
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
2 |
6 |
4 |
|
|
B |
2 |
|
3 |
|
|
|
C |
6 |
3 |
|
3 |
2 |
|
D |
4 |
|
3 |
|
|
|
E |
|
|
2 |
|
|
Определите длину кратчайшего пути между пунктами A и Е. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
ABCE=2+3+2=7
Ответ: 7
692404
Между населёнными пунктами 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. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
BACED=1+2+1+4=8
Ответ: 8
340308
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
1 |
1 |
|
2 |
|
B |
1 |
|
3 |
6 |
|
|
C |
1 |
3 |
|
1 |
|
|
D |
|
6 |
1 |
|
7 |
|
E |
2 |
|
|
7 |
|
Определите длину кратчайшего пути между пунктами A и D (при условии, что передвигаться можно только по указанным в таблице дорогам). Каждый пункт можно посетить только один раз.
Решение:
ACD 1+1=2
Напрямую с А нет пути, поэтому через одну точку и с минимальными номиналами будет 2, меньше искать нет смысла.
Ответ: 2
F25E71
Между населёнными пунктами A, B, C, D построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
|
A |
|
5 |
8 |
3 |
|
B |
5 |
|
2 |
1 |
|
C |
8 |
2 |
|
4 |
|
D |
3 |
1 |
4 |
|
Определите длину кратчайшего пути между пунктами A и C. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
AC=8
ABC=5+2=7
ADC=3+4=7
ADBC=3+1+2=6
Ответ: 6
761075
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
Е |
|
A |
|
2 |
1 |
4 |
8 |
|
B |
2 |
|
|
|
5 |
|
C |
1 |
|
|
2 |
|
|
D |
4 |
|
2 |
|
3 |
|
Е |
8 |
5 |
|
3 |
|
Определите длину кратчайшего пути между пунктами A и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
ACDE=1+2+3=6
Ответ: 6
BDD67F
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
6 |
1 |
5 |
2 |
|
B |
6 |
|
4 |
|
|
|
C |
1 |
4 |
|
6 |
|
|
D |
5 |
|
6 |
|
2 |
|
E |
2 |
|
|
2 |
|
Определите длину кратчайшего пути между пунктами D и B. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
DEACB=2+2+1+4=5+4=9
Ответ: 9
57BC75
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
F |
|
A |
|
3 |
5 |
|
|
15 |
|
B |
3 |
|
|
4 |
|
|
|
C |
5 |
|
|
1 |
|
|
|
D |
|
4 |
1 |
|
2 |
6 |
|
E |
|
|
|
2 |
|
1 |
|
F |
15 |
|
|
6 |
1 |
|
Определите длину кратчайшего пути между пунктами A и F. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Решение:
ACDEF=5+1+2+1=9
Ответ: 9
78F3B9
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
2 |
|
4 |
|
|
B |
2 |
|
5 |
1 |
|
|
C |
|
5 |
|
3 |
2 |
|
D |
4 |
1 |
3 |
|
|
|
E |
|
|
2 |
|
|
Определите длину кратчайшего пути между пунктами A и Е. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
EC=2+1+3+2=8
Ответ: 8
1BD7B7
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
2 |
|
1 |
|
|
B |
2 |
|
3 |
3 |
|
|
C |
|
3 |
|
3 |
2 |
|
D |
1 |
3 |
3 |
|
|
|
E |
|
|
2 |
|
|
Определите длину кратчайшего пути между пунктами A и Е. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
ADC=1+3+2=6
Ответ: 6
5106B5
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
1 |
|
|
|
|
B |
1 |
|
2 |
2 |
7 |
|
C |
|
2 |
|
|
3 |
|
D |
|
2 |
|
|
4 |
|
E |
|
7 |
3 |
4 |
|
Определите длину кратчайшего пути между пунктами A и Е. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
ABCE=1+2+3=6
Ответ: 6
57BDB6
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
4 |
|
|
2 |
|
B |
4 |
|
1 |
4 |
1 |
|
C |
|
1 |
|
2 |
|
|
D |
|
4 |
2 |
|
5 |
|
E |
2 |
1 |
|
5 |
|
Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
AEBCD=2+1+1+2=6
Ответ: 6
34BBBC
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
|
3 |
2 |
|
|
B |
|
|
4 |
|
5 |
|
C |
3 |
4 |
|
1 |
|
|
D |
2 |
|
1 |
|
4 |
|
E |
|
5 |
|
4 |
|
Определите длину кратчайшего пути между пунктами A и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
ADE=2+4=6
Ответ: 6
8B45B8
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
6 |
|
|
3 |
|
B |
6 |
|
2 |
5 |
1 |
|
C |
|
2 |
|
2 |
|
|
D |
|
5 |
2 |
|
6 |
|
E |
3 |
1 |
|
6 |
|
Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
AEBCD=3+1+2+2=8
Ответ: 8
4C0315
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
F |
|
A |
|
2 |
5 |
|
|
15 |
|
B |
2 |
|
1 |
|
|
|
|
C |
5 |
1 |
|
1 |
3 |
|
|
D |
|
|
1 |
|
|
6 |
|
E |
|
|
3 |
|
|
3 |
|
F |
15 |
|
|
6 |
3 |
|
Определите длину кратчайшего пути между пунктами A и F. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Решение:
ABCEF=2+1+3+3=9
Ответ: 9
21C114
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
2 |
3 |
4 |
|
|
B |
2 |
|
1 |
5 |
2 |
|
C |
3 |
1 |
|
|
5 |
|
D |
4 |
5 |
|
|
7 |
|
E |
|
2 |
5 |
7 |
|
Определите длину кратчайшего пути между пунктами A и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
ABE=2+2=4
Ответ: 4
26B413
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
Е |
|
A |
|
1 |
1 |
|
4 |
|
B |
1 |
|
|
3 |
3 |
|
C |
1 |
|
|
2 |
1 |
|
D |
|
3 |
2 |
|
5 |
|
Е |
4 |
3 |
1 |
5 |
|
Определите длину кратчайшего пути между пунктами A и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
ACE=1+1=2
Ответ: 2
998916
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
6 |
|
|
4 |
|
B |
6 |
|
2 |
5 |
1 |
|
C |
|
2 |
|
2 |
|
|
D |
|
5 |
2 |
|
6 |
|
E |
4 |
1 |
|
6 |
|
Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
AEBCD=4+1+2+2=9
Ответ: 9
8E0617
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
2 |
2 |
|
4 |
|
B |
2 |
|
5 |
|
|
|
C |
2 |
5 |
|
|
1 |
|
D |
|
|
|
|
4 |
|
E |
4 |
|
1 |
4 |
|
Определите длину кратчайшего пути между пунктами B и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
BACED=2+2+1+4
Ответ: 9
8FFD16
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
2 |
1 |
|
5 |
|
B |
2 |
|
4 |
|
|
|
C |
1 |
4 |
|
1 |
4 |
|
D |
|
|
1 |
|
2 |
|
E |
5 |
|
4 |
2 |
|
Определите длину кратчайшего пути между пунктами B и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
По таблице А соединяется с В, С, Е; В дополнительно с С; С дополнительно с D, Е; D с Е.
Подпишите длины отрезков из таблицы, так легче будет сориентироваться.
Пытаемся идти, собирая самые маленькие расстояния.
BACDE=2+1+1+2=6
Ответ: 6
F78223
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
F |
|
A |
|
3 |
7 |
|
|
2 |
|
B |
3 |
|
|
|
|
|
|
C |
7 |
|
|
3 |
1 |
|
|
D |
|
|
3 |
|
1 |
2 |
|
E |
|
|
1 |
1 |
|
|
|
F |
2 |
|
|
2 |
|
|
Определите длину кратчайшего пути между пунктами B и C. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
BAFD=3+2+2+2=9
Ответ: 9
EE4920
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
2 |
|
|
1 |
|
B |
2 |
|
5 |
|
4 |
|
C |
|
5 |
|
3 |
3 |
|
D |
|
|
3 |
|
4 |
|
E |
1 |
4 |
3 |
4 |
|
Определите длину кратчайшего пути между пунктами B и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
BAED=2+1+4=7
Ответ: 7
37E226
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
6 |
|
1 |
4 |
|
B |
6 |
|
2 |
5 |
|
|
C |
|
2 |
|
2 |
|
|
D |
1 |
5 |
2 |
|
6 |
|
E |
4 |
|
|
6 |
|
Определите длину кратчайшего пути между пунктами B и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
BCDAE=2+2+1+4=9
Ответ: 9
7057DC
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
F |
|
A |
|
3 |
5 |
|
|
15 |
|
B |
3 |
|
|
4 |
|
|
|
C |
5 |
|
|
2 |
|
|
|
D |
|
4 |
2 |
|
3 |
6 |
|
E |
|
|
|
3 |
|
4 |
|
F |
15 |
|
|
6 |
4 |
|
Определите длину кратчайшего пути между пунктами A и F. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Решение:
ACDF=5+2+6=13
Ответ: 13
B100D0
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
4 |
7 |
|
|
|
B |
4 |
|
1 |
5 |
|
|
C |
7 |
1 |
|
3 |
|
|
D |
|
5 |
3 |
|
1 |
|
E |
|
|
|
1 |
|
Определите длину кратчайшего пути между пунктами A и Е. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
ABCDF=4+1+3+1=9
Ответ: 9
1FE6D0
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
Е |
|
A |
|
3 |
3 |
|
|
|
B |
3 |
|
2 |
1 |
4 |
|
C |
3 |
2 |
|
5 |
|
|
D |
|
1 |
5 |
|
|
|
Е |
|
4 |
|
|
|
Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
ABD=3+1=4
Ответ: 4
274256
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
F |
|
A |
|
1 |
5 |
|
|
13 |
|
B |
1 |
|
2 |
|
|
|
|
C |
5 |
2 |
|
1 |
|
|
|
D |
|
|
1 |
|
2 |
5 |
|
E |
|
|
|
2 |
|
2 |
|
F |
13 |
|
|
5 |
2 |
|
Определите длину кратчайшего пути между пунктами A и F. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Решение:
ABCDEF=1+2+1+2+2=8
Ответ: 8
A29351
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
F |
|
A |
|
1 |
5 |
|
|
15 |
|
B |
1 |
|
2 |
|
|
|
|
C |
5 |
2 |
|
3 |
|
|
|
D |
|
|
3 |
|
2 |
3 |
|
E |
|
|
|
2 |
|
2 |
|
F |
15 |
|
|
3 |
2 |
|
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт D. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только 1 раз.
Решение:
ABCDF=1+2+3+3=9
Ответ: 9
EB8553
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
5 |
3 |
|
|
|
B |
5 |
|
1 |
4 |
|
|
C |
3 |
1 |
|
6 |
|
|
D |
|
4 |
6 |
|
1 |
|
E |
|
|
|
1 |
|
Определите длину кратчайшего пути между пунктами A и Е. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
ACBDF=3+4+1+1=9
Ответ: 9
35125E
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
3 |
7 |
|
|
|
B |
3 |
|
2 |
|
8 |
|
C |
7 |
2 |
|
4 |
|
|
D |
|
|
4 |
|
1 |
|
E |
|
8 |
|
1 |
|
Определите длину кратчайшего пути между пунктами A и Е. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
ABCDE=3+2+4+1=10
Ответ: 10
484BA5
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
2 |
|
4 |
|
|
B |
2 |
|
3 |
5 |
2 |
|
C |
|
3 |
|
|
3 |
|
D |
4 |
5 |
|
|
5 |
|
E |
|
2 |
3 |
5 |
|
Определите длину кратчайшего пути между пунктами A и C. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
ABC=2+3=5
Ответ:5
0C31A2
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
5 |
|
|
3 |
|
B |
5 |
|
1 |
5 |
|
|
C |
|
1 |
|
1 |
5 |
|
D |
|
5 |
1 |
|
6 |
|
E |
3 |
|
5 |
6 |
|
Определите длину кратчайшего пути между пунктами A и D (при условии, что передвигаться можно только по указанным в таблице дорогам). Каждый пункт можно посетить только один раз.
Решение:
ABCD=5+1+1=7
Ответ: 7
1FEEAD
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
2 |
5 |
|
6 |
|
B |
2 |
|
2 |
|
|
|
C |
5 |
2 |
|
6 |
1 |
|
D |
|
|
6 |
|
4 |
|
E |
6 |
|
1 |
4 |
|
Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
По таблице А соединяется с В, С, Е; В дополнительно с С; С дополнительно с D, Е; D с Е.
Подпишите длины отрезков из таблицы, так легче будет сориентироваться.
Пытаемся идти, собирая самые короткие дороги.
ABCED=2+2+1+4=9
Ответ: 9
2E5EA0
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
1 |
|
|
2 |
|
B |
1 |
|
|
1 |
2 |
|
C |
|
|
|
2 |
1 |
|
D |
|
1 |
2 |
|
|
|
E |
2 |
2 |
1 |
|
|
Определите длину кратчайшего пути между пунктами A и C (при условии, что передвигаться можно только по указанным в таблице дорогам). Каждый пункт можно посетить только один раз.
Решение:
AEC=2+1=3
Ответ: 3
5D33A5
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
2 |
6 |
|
8 |
|
B |
2 |
|
3 |
|
|
|
C |
6 |
3 |
|
5 |
2 |
|
D |
|
|
5 |
|
3 |
|
E |
8 |
|
2 |
3 |
|
Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
По таблице А соединяется с В, С, Е; В дополнительно с С; С дополнительно с D, Е; D с Е.
Подпишите длины отрезков из таблицы, так легче будет сориентироваться.
Пытаемся идти, собирая самые короткие дороги.
ABCD=2+3+5=10
Ответ: 10
4B6BC1
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
3 |
|
|
|
|
B |
3 |
|
1 |
2 |
6 |
|
C |
|
1 |
|
|
3 |
|
D |
|
2 |
|
|
3 |
|
E |
|
6 |
3 |
3 |
|
Определите длину кратчайшего пути между пунктами A и Е. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
ABCE=3+1+3=7
Ответ: 7
7988CA
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
F |
|
A |
|
2 |
3 |
7 |
|
15 |
|
B |
2 |
|
|
3 |
|
|
|
C |
3 |
|
|
5 |
|
|
|
D |
7 |
3 |
5 |
|
2 |
11 |
|
E |
|
|
|
2 |
|
4 |
|
F |
15 |
|
|
11 |
4 |
|
Определите длину кратчайшего пути между пунктами A и F. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Решение:
ABDEF=2+3+2+4=11
Ответ: 11
BB3AC7
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
F |
|
A |
|
3 |
5 |
|
|
15 |
|
B |
3 |
|
|
4 |
|
|
|
C |
5 |
|
|
3 |
|
|
|
D |
|
4 |
3 |
|
2 |
6 |
|
E |
|
|
|
2 |
|
2 |
|
F |
15 |
|
|
6 |
2 |
|
Определите длину кратчайшего пути между пунктами A и F. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Решение:
ABDEF=3+4+2+2=11
Ответ: 11
B4EDC8
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице.
|
|
A |
B |
C |
D |
E |
F |
|
A |
|
3 |
|
|
|
|
|
B |
3 |
|
2 |
|
|
7 |
|
C |
|
2 |
|
|
2 |
|
|
D |
|
|
|
|
1 |
1 |
|
E |
|
|
2 |
1 |
|
3 |
|
F |
|
7 |
|
1 |
3 |
|
Определите кратчайший путь между пунктами A и F (при условии, что передвигаться можно только по указанным в таблице дорогам). Каждый пункт можно посетить только один раз.
Решение:
ABCDF=3+2+2+1+1=9
Ответ: 9
188AC9
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
5 |
|
4 |
2 |
|
B |
5 |
|
3 |
3 |
|
|
C |
|
3 |
|
4 |
|
|
D |
4 |
3 |
4 |
|
1 |
|
E |
2 |
|
|
1 |
|
Определите длину кратчайшего пути между пунктами A и C. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
AEDC=2+1+4=7
Ответ: 7
59EAC4
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
F |
|
A |
|
2 |
3 |
7 |
|
15 |
|
B |
2 |
|
|
3 |
|
|
|
C |
3 |
|
|
1 |
|
|
|
D |
7 |
3 |
1 |
|
2 |
11 |
|
E |
|
|
|
2 |
|
3 |
|
F |
15 |
|
|
11 |
3 |
|
Определите длину кратчайшего пути между пунктами A и F. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Решение:
ACDEF=3+1+2+3=9
Ответ: 9
65BEC2
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
F |
|
A |
|
3 |
4 |
|
|
15 |
|
B |
3 |
|
2 |
|
|
|
|
C |
4 |
2 |
|
1 |
|
|
|
D |
|
|
1 |
|
2 |
6 |
|
E |
|
|
|
2 |
|
2 |
|
F |
15 |
|
|
6 |
2 |
|
Определите длину кратчайшего пути между пунктами A и F, не проходящего через пункт B. Передвигаться можно только по дорогам, указанным
в таблице. Каждый пункт можно посетить только один раз.
Решение:
ACDEF=4+1+2+2=9
Ответ: 9
8323C8
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
F |
|
A |
|
3 |
5 |
|
|
15 |
|
B |
3 |
|
1 |
|
|
|
|
C |
5 |
1 |
|
2 |
|
|
|
D |
|
|
2 |
|
4 |
6 |
|
E |
|
|
|
4 |
|
1 |
|
F |
15 |
|
|
6 |
1 |
|
Определите длину кратчайшего пути между пунктами A и F. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Решение:
ABCDEF=3+1+2+4+1=11
Ответ: 11
43E791
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
7 |
2 |
6 |
2 |
|
B |
7 |
|
4 |
|
|
|
C |
2 |
4 |
|
8 |
|
|
D |
6 |
|
8 |
|
3 |
|
E |
2 |
|
|
3 |
|
Определите длину кратчайшего пути между пунктами B и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
BCAD=4+2+2+3=11
Ответ: 11
1CD999
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице.
|
|
A |
B |
C |
D |
E |
F |
|
A |
|
5 |
3 |
|
|
|
|
B |
5 |
|
|
6 |
2 |
|
|
C |
3 |
|
|
|
5 |
4 |
|
D |
|
6 |
|
|
3 |
5 |
|
E |
|
2 |
5 |
3 |
|
|
|
F |
|
|
4 |
5 |
|
|
Определите длину кратчайшего пути между пунктами A и D, проходящего через E (при условии, что передвигаться можно только по указанным
в таблице дорогам). Каждый пункт можно посетить только один раз.
Решение:
ABED = 5+2+3 = 10
Ответ: 10
13D296
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
4 |
4 |
|
|
|
B |
4 |
|
1 |
5 |
|
|
C |
4 |
1 |
|
3 |
|
|
D |
|
5 |
3 |
|
1 |
|
E |
|
|
|
1 |
|
Определите длину кратчайшего пути между пунктами A и Е. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
ACDE=4+3+1=8
Ответ: 8
D8229C
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
2 |
7 |
|
6 |
|
B |
2 |
|
3 |
|
|
|
C |
7 |
3 |
|
5 |
2 |
|
D |
|
|
5 |
|
3 |
|
E |
6 |
|
2 |
3 |
|
Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
По таблице А соединяется с В, С, Е; В дополнительно с С; С дополнительно с D, Е; D с Е.
Подпишите длины отрезков из таблицы, так легче будет сориентироваться.
Пытаемся идти, собирая самые короткие дороги.
AED=6+3=9
Ответ: 9
42FAE7
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
1 |
|
|
|
|
B |
1 |
|
4 |
2 |
8 |
|
C |
|
4 |
|
|
4 |
|
D |
|
2 |
|
|
4 |
|
E |
|
8 |
4 |
4 |
|
Определите длину кратчайшего пути между пунктами A и Е. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
ABDE=1+2+4=7
Ответ: 7
B414E2
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
F |
|
A |
|
1 |
4 |
|
|
15 |
|
B |
1 |
|
2 |
|
|
|
|
C |
4 |
2 |
|
5 |
|
|
|
D |
|
|
5 |
|
3 |
3 |
|
E |
|
|
|
3 |
|
3 |
|
F |
15 |
|
|
3 |
3 |
|
Определите длину кратчайшего пути между пунктами A и F. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Решение:
ABCDF=1+2+5+3=11
Ответ: 11
2442E1
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
2 |
3 |
|
|
|
B |
2 |
|
1 |
3 |
5 |
|
C |
3 |
1 |
|
4 |
3 |
|
D |
|
3 |
4 |
|
1 |
|
E |
|
5 |
3 |
1 |
|
Определите длину кратчайшего пути между пунктами A и Е, проходящего через пункт С. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
ABDE=2+3+1=6
Ответ: 6
A97CEA
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
F |
|
A |
|
3 |
5 |
|
|
15 |
|
B |
3 |
|
1 |
|
|
|
|
C |
5 |
1 |
|
1 |
|
|
|
D |
|
|
1 |
|
2 |
6 |
|
E |
|
|
|
2 |
|
2 |
|
F |
15 |
|
|
6 |
2 |
|
Определите длину кратчайшего пути между пунктами A и F. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Решение:
ABCDEF=3+1+1+2+2=9
Ответ: 9
EC30EC
Между населёнными пунктами 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. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
По таблице А соединяется с В, С, Е; В дополнительно с С; С дополнительно с D, Е; D с Е.
Подпишите длины отрезков из таблицы, так легче будет сориентироваться.
Пытаемся идти, собирая самые короткие дороги.
ABCED=2+1+1+3=7
Ответ: 7
E87CE9
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
|
1 |
2 |
4 |
|
B |
|
|
4 |
|
|
|
C |
1 |
4 |
|
4 |
|
|
D |
2 |
|
4 |
|
1 |
|
E |
4 |
|
|
1 |
|
Определите длину кратчайшего пути между пунктами B и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
BCADE=4+1+2+1=8
Ответ: 8
FD2668
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
2 |
|
|
3 |
|
B |
2 |
|
5 |
2 |
4 |
|
C |
|
5 |
|
1 |
|
|
D |
|
2 |
1 |
|
|
|
E |
3 |
4 |
|
|
|
Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
ABD=2+2=4
Ответ: 4
0B8869
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
F |
|
A |
|
1 |
5 |
|
|
15 |
|
B |
1 |
|
2 |
|
|
|
|
C |
5 |
2 |
|
1 |
|
|
|
D |
|
|
1 |
|
2 |
6 |
|
E |
|
|
|
2 |
|
1 |
|
F |
15 |
|
|
6 |
1 |
|
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт E. Передвигаться можно только по дорогам, указанным
в таблице. Каждый пункт можно посетить только один раз.
Решение:
ABCDEF=1+2+1+2+1=7
Ответ: 7
2FC360
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
Е |
|
A |
|
4 |
9 |
|
|
|
B |
4 |
|
2 |
3 |
|
|
C |
9 |
2 |
|
2 |
2 |
|
D |
|
3 |
2 |
|
3 |
|
Е |
|
|
2 |
3 |
|
Определите длину кратчайшего пути между пунктами A и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
ABCE=4+2+2=8
Ответ: 8
528163
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
4 |
|
|
|
|
B |
4 |
|
4 |
|
1 |
|
C |
|
4 |
|
1 |
2 |
|
D |
|
|
1 |
|
3 |
|
E |
|
1 |
2 |
3 |
|
Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
ABED=4+1+3=8
Ответ: 8
ACC66D
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
7 |
4 |
|
|
|
B |
7 |
|
2 |
|
4 |
|
C |
4 |
2 |
|
4 |
|
|
D |
|
|
4 |
|
4 |
|
E |
|
4 |
|
4 |
|
Определите длину кратчайшего пути между пунктами A и Е, проходящего через пункт C. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
ACBE=4+2+4=10
Ответ: 10
E89660
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
F |
|
A |
|
2 |
5 |
|
|
15 |
|
B |
2 |
|
2 |
|
|
|
|
C |
5 |
2 |
|
1 |
3 |
|
|
D |
|
|
1 |
|
|
6 |
|
E |
|
|
3 |
|
|
4 |
|
F |
15 |
|
|
6 |
4 |
|
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт C. Передвигаться можно только по дорогам, указанным
в таблице. Каждый пункт можно посетить только один раз.
Решение:
ABCEF=2+2+3+4=4+7=11
Ответ: 11
6FC465
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
5 |
8 |
8 |
12 |
|
B |
5 |
|
|
4 |
|
|
C |
8 |
|
|
|
7 |
|
D |
8 |
4 |
|
|
5 |
|
E |
12 |
|
7 |
5 |
|
Определите длину кратчайшего пути между пунктами A и E (при условии, что передвигаться можно только по указанным в таблице дорогам). Каждый пункт можно посетить только один раз.
Решение:
ADE = 8+5 = 13
Ответ: 13
4F4D3A
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
2 |
|
|
5 |
|
B |
2 |
|
2 |
3 |
1 |
|
C |
|
2 |
|
1 |
|
|
D |
|
3 |
1 |
|
1 |
|
E |
5 |
1 |
|
1 |
|
Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
ABED = 2+1+1 = 4
Ответ: 4
FCAE3A
Между населёнными пунктами A, B, C, D построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
|
A |
|
2 |
7 |
4 |
|
B |
2 |
|
5 |
1 |
|
C |
7 |
5 |
|
2 |
|
D |
4 |
1 |
2 |
|
Определите длину кратчайшего пути между пунктами A и C. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
ABDC = 2+1+2 = 5
Ответ: 5
781336
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
|
4 |
5 |
7 |
|
B |
|
|
1 |
|
3 |
|
C |
4 |
1 |
|
2 |
1 |
|
D |
5 |
|
2 |
|
1 |
|
E |
7 |
3 |
1 |
1 |
|
Определите длину кратчайшего пути между пунктами A и E, проходящего через пункт D (при условии, что передвигаться можно только по указанным
в таблице дорогам). Каждый пункт можно посетить только один раз.
Решение:
ADE = 5+1 = 6
Ответ: 6
B7483A
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
5 |
6 |
10 |
5 |
|
B |
5 |
|
|
4 |
|
|
C |
6 |
|
|
2 |
7 |
|
D |
10 |
4 |
2 |
|
5 |
|
E |
5 |
|
7 |
5 |
|
Определите длину кратчайшего пути между пунктами A и D, проходящего через пункт E (при условии, что передвигаться можно только по указанным
в таблице дорогам). Каждый пункт можно посетить только один раз.
Решение:
Не ленитесь, подпишите все расстояния, будет нагляднее!
AED = 5+5 = 10
Ответ: 10
DDD73B
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
F |
|
A |
|
3 |
4 |
|
|
18 |
|
B |
3 |
|
3 |
|
|
|
|
C |
4 |
3 |
|
4 |
|
|
|
D |
|
|
4 |
|
2 |
6 |
|
E |
|
|
|
2 |
|
1 |
|
F |
18 |
|
|
6 |
1 |
|
Определите длину кратчайшего пути между пунктами A и F. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Решение:
ACDEF = 4+4+2+1 = 11
Ответ: 11
D6913D
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
3 |
3 |
|
|
|
B |
3 |
|
|
5 |
6 |
|
C |
3 |
|
|
4 |
|
|
D |
|
5 |
4 |
|
1 |
|
E |
|
6 |
|
1 |
|
Определите длину кратчайшего пути между пунктами A и Е. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
ACDE = 3+4+1 = 8
Ответ: 8
387B3E
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
Е |
|
A |
|
1 |
4 |
5 |
6 |
|
B |
1 |
|
|
3 |
2 |
|
C |
4 |
|
|
|
2 |
|
D |
5 |
3 |
|
|
1 |
|
Е |
6 |
2 |
2 |
1 |
|
Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
ABD = 1+3 = 4
Ответ: 4
02D38B
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
7 |
4 |
|
|
|
B |
7 |
|
2 |
|
5 |
|
C |
4 |
2 |
|
4 |
|
|
D |
|
|
4 |
|
5 |
|
E |
|
5 |
|
5 |
|
Определите длину кратчайшего пути между пунктами A и Е. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
ACBE = 4+2+5 = 11
Ответ: 11
B1B889
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
1 |
5 |
|
2 |
|
B |
1 |
|
|
6 |
|
|
C |
5 |
|
|
1 |
7 |
|
D |
|
6 |
1 |
|
|
|
E |
2 |
|
7 |
|
|
Определите длину кратчайшего пути между пунктами A и D, проходящего через пункт B (при условии, что передвигаться можно только по указанным
в таблице дорогам). Каждый пункт можно посетить только один раз.
Решение:
ABD = 1+6 = 7
Ответ: 7
B64486
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
2 |
5 |
1 |
|
|
B |
2 |
|
1 |
|
|
|
C |
5 |
1 |
|
3 |
2 |
|
D |
1 |
|
3 |
|
|
|
E |
|
|
2 |
|
|
Определите длину кратчайшего пути между пунктами A и Е. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
ABCE = 2+1+2 = 5
Ответ: 5
A3078A
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
7 |
|
|
4 |
|
B |
7 |
|
2 |
6 |
2 |
|
C |
|
2 |
|
3 |
|
|
D |
|
6 |
3 |
|
8 |
|
E |
4 |
2 |
|
8 |
|
Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
AEBCD = 4+2+2+3 = 11
Ответ: 11
9D618A
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
|
A |
B |
C |
D |
E |
|
A |
|
4 |
2 |
|
8 |
|
B |
4 |
|
7 |
|
|
|
C |
2 |
7 |
|
2 |
6 |
|
D |
|
|
2 |
|
3 |
|
E |
8 |
|
6 |
3 |
|
Определите длину кратчайшего пути между пунктами B и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение:
По таблице А соединяется с В, С, Е; В дополнительно с С; С дополнительно с D, Е; D с Е.
Подпишите длины отрезков на рисунке, чтобы легче было сориентироваться.
ВА = 4
АС = 2
АЕ = 8
ВС = 7
СD = 2
СЕ = 6
ЕD = 3
Пытаемся идти, собирая самые короткие дороги.
ВАСDЕ = 4 + 2 + 2 + 3 = 11 км - кратчайший путь
Ответ: 11
3D3982
В старом банке ФИПИ есть так же вопросы с выбором вариантов ответа, но их нет в новом ОБЗ и не будет на реальном экзамене.
