ЕГЭ задание 1. Теория графов
На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).
| Номер пункта | ||||||||
|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | ||
| Номер пункта | 1 | 30 | 3 | 5 | ||||
| 2 | 21 | 13 | ||||||
| 3 | 39 | 53 | 2 | |||||
| 4 | 30 | 21 | ||||||
| 5 | 3 | 39 | 8 | |||||
| 6 | 13 | 53 | 8 | |||||
| 7 | 5 | 2 | ||||||
Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта D в пункт G и из пункта A в пункт C. В ответе запишите целое число.
На рисунке справа схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).
| Номер пункта | ||||||||
|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | ||
| Номер пункта | 1 | 5 | 4 | 6 | ||||
| 2 | 8 | 9 | 7 | |||||
| 3 | 8 | 12 | ||||||
| 4 | 5 | 9 | 12 | |||||
| 5 | 4 | 13 | 11 | |||||
| 6 | 7 | 13 | 10 | |||||
| 7 | 6 | 11 | 10 | |||||
Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта Г впункт К.
На рисунке схема дорог N-ского района изображена в виде графа, в таблице звёздочкой обозначено наличие дороги между населёнными пунктами. Отсутствие звёздочки означает, что дороги нет.
| Номер пункта | ||||||||
|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | ||
| Номер пункта | 1 | \( * \) | \( * \) | \( * \) | ||||
| 2 | \( * \) | \( * \) | ||||||
| 3 | \( * \) | \( * \) | ||||||
| 4 | \( * \) | \( * \) | ||||||
| 5 | \( * \) | \( * \) | \( * \) | |||||
| 6 | \( * \) | \( * \) | \( * \) | |||||
| 7 | \( * \) | \( * \) | \( * \) | |||||
Каждому населённому пункту на схеме соответствует номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам G и D на схеме. В ответе запишите номера этих пунктов в порядке возрастания без пробелов и знаков препинания.
На рисунке справа схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).
| Номер пункта | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | ||
| Номер пункта | 1 | 18 | 32 | 31 | |||||
| 2 | 25 | 23 | |||||||
| 3 | 25 | 71 | 13 | ||||||
| 4 | 18 | 39 | |||||||
| 5 | 71 | 39 | |||||||
| 6 | 13 | 16 | |||||||
| 7 | 32 | 16 | 27 | ||||||
| 8 | 31 | 23 | 27 | ||||||
Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта D в пункт Е и из пункта D в пункт G. В ответе запишите целое число.
На рисунке изображена схема дорог N-ского района. В таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.
| Номер пункта | ||||||||
|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | ||
| Номер пункта | 1 | \( * \) | \( * \) | \( * \) | ||||
| 2 | \( * \) | \( * \) | \( * \) | |||||
| 3 | \( * \) | \( * \) | ||||||
| 4 | \( * \) | \( * \) | \( * \) | |||||
| 5 | \( * \) | \( * \) | \( * \) | |||||
| 6 | \( * \) | \( * \) | \( * \) | \( * \) | \( * \) | |||
| 7 | \( * \) | \( * \) | \( * \) | |||||
Каждому населённому пункту на схеме соответствует номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам А и F на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.
На рисунке изображена схема дорог N-ского района. В таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.
| Номер пункта | ||||||||
|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | ||
| Номер пункта | 1 | \( * \) | \( * \) | \( * \) | \( * \) | \( * \) | \( * \) | |
| 2 | \( * \) | \( * \) | ||||||
| 3 | \( * \) | \( * \) | \( * \) | |||||
| 4 | \( * \) | \( * \) | \( * \) | |||||
| 5 | \( * \) | \( * \) | \( * \) | |||||
| 6 | \( * \) | \( * \) | ||||||
| 7 | \( * \) | \( * \) | \( * \) | |||||
Каждому населённому пункту на схеме соответствует номер в таблице, но неизвестно, какой именно номер. Определите, какие номера в таблице могут соответствовать населённым пунктам E и F на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.