В таблице показаны внутрироссийские рейсы авиакомпании "Аврора". Постройте граф, в котором вершины соответствуют городам и две вершины связаны ребром, только если между соответствующими городами имеется авиарейс авиакомпании "Аврора". Среди данных графов выберите тот, который соответствует условию задачи.

Решение:

Чтобы построить граф, нам нужно представить города как вершины, а авиарейсы как рёбра между ними. Каждое рёбро соединяет два города, между которыми есть прямой рейс.

Список рейсов:

• Откуда: Хабаровск, Куда: Владивосток
• Откуда: Хабаровск, Куда: Южно-Сахалинск
• Откуда: Хабаровск, Куда: Новосибирск
• Откуда: Хабаровск, Куда: Красноярск
• Откуда: Хабаровск, Куда: Иркутск
• Откуда: Хабаровск, Куда: Магадан
• Откуда: Хабаровск, Куда: Благовещенск
• Откуда: Владивосток, Куда: Южно-Сахалинск
• Откуда: Южно-Сахалинск, Куда: Иркутск

Граф должен содержать следующие вершины и рёбра:

Вершины: Хабаровск, Владивосток, Южно-Сахалинск, Новосибирск, Красноярск, Иркутск, Магадан, Благовещенск.

Рёбра:

• (Хабаровск, Владивосток)
• (Хабаровск, Южно-Сахалинск)
• (Хабаровск, Новосибирск)
• (Хабаровск, Красноярск)
• (Хабаровск, Иркутск)
• (Хабаровск, Магадан)
• (Хабаровск, Благовещенск)
• (Владивосток, Южно-Сахалинск)
• (Южно-Сахалинск, Иркутск)

Ответ: Граф, соответствующий условию задачи, будет иметь 8 вершин (городов) и 9 рёбер (авиарейсов), как показано на схеме выше.