Пример 16. Авиакомпания «Авиаграф» выполняет полеты между пятью городами. Столбцы и строки таблицы соответствуют городам. Если в таблице клетка закрашена, то существует рейс между соответствующими городами. Нарисуйте граф рейсов этой компании. Верно ли, что из каждого города можно добраться в каждый (может быть, с пересадками)?

Сначала построим граф, где вершины соответствуют городам, а ребра - авиарейсам между ними. Наличие закрашенной клетки в таблице означает, что между соответствующими городами есть рейс. Граф будет выглядеть следующим образом: * Акатск соединен с Береградом. * Береград соединен с Акатском, Восточным и Гориполем. * Восточный соединен с Береградом и Гориполем. * Гориполь соединен с Береградом, Восточным и Двинском. * Двинск соединен с Гориполем. Теперь проверим, можно ли добраться из каждого города в каждый (возможно, с пересадками). * Из Акатска можно добраться до: * Акатска (самому в себя) * Береграда (прямой рейс) * Восточного (через Береград) * Гориполя (через Береград) * Двинска (через Береград и Гориполь) * Из Береграда можно добраться до: * Береграда (самому в себя) * Акатска (прямой рейс) * Восточного (прямой рейс) * Гориполя (прямой рейс) * Двинска (через Гориполь) * Из Восточного можно добраться до: * Восточного (самому в себя) * Береграда (прямой рейс) * Гориполя (прямой рейс) * Акатска (через Береград) * Двинска (через Гориполь) * Из Гориполя можно добраться до: * Гориполя (самому в себя) * Береграда (прямой рейс) * Восточного (прямой рейс) * Двинска (прямой рейс) * Акатска (через Береград) * Из Двинска можно добраться до: * Двинска (самому в себя) * Гориполя (прямой рейс) * Береграда (через Гориполь) * Восточного (через Гориполь) * Акатска (через Гориполь и Береград) Поскольку из каждого города можно добраться до любого другого (возможно, с пересадками), утверждение верно. **Ответ:** Да, из каждого города можно добраться в каждый (может быть, с пересадками).