Определите два населённых пункта, дорога между которыми есть на графе
Условие
| На рисунке схема дорог изображена в виде графа, в таблице звёздочкой отмечено наличие дороги между двумя населёнными пунктами. Так как таблицу и схему рисовали независимо друг от друга, нумерация пунктов в таблице никак не связана с буквенными обозначениями на графе. Кроме того, при заполнении таблицы одну дорогу случайно пропустили. Определите два населённых пункта, дорога между которыми есть на графе, но не отмечена в таблице. В ответе запишите номера этих пунктов в таблице в порядке возрастания, без разделителей между ними, как двузначное число. Например, если бы в таблице была пропущена дорога между пунктами П1 и П2, в ответе следовало бы написать число 12. | П1 | П2 | П3 | П4 | П5 | П6 | П7 | П8 |
|---|---|---|---|---|---|---|---|---|
| П1 | ⁎ | ⁎ | ⁎ | |||||
| П2 | ⁎ | ⁎ | ||||||
| П3 | ⁎ | ⁎ | ||||||
| П4 | ⁎ | ⁎ | ⁎ | |||||
| П5 | ⁎ | ⁎ | ⁎ | ⁎ | ||||
| П6 | ⁎ | ⁎ | ||||||
| П7 | ⁎ | ⁎ | ⁎ | ⁎ | ⁎ | |||
| П8 | ⁎ | ⁎ | ⁎ |
Ответ
Ответ и полный разбор откроются после входа
Посмотреть ответ){kind=link}
Решение по шагам
Как рассуждать
Решение. На рисунке есть один пункт степени 6 - И. В таблице есть пункт степени 5, это пункт П7, следовательно, это и есть населенный пункт И у которого пропущена одна дорога. На графике есть два пункта (Е и Б) степени 4, а в таблице такой пункт только один. Следовательно, пропущена одна из двух дорог И-Е или И-Б. На графике есть два пункта степени 2 имеющие общие дороги с пунктом И, это пункты П2 и П3. Следовательно, пункт В это пункт П6. Так как пункт Е единственный пункт степени 4 имеющий общие дороги с двумя пунктами степени 2, то это пункт П4. Так как в таблице у пункта П4 только 3 дороги, следовательно, пропущена дорога И-Е, П4-П7. Ответ
Осталось ещё 1 шаг
Приведём решение Юрия Красильникова на языке…
Бесплатно · займёт минуту