Авиасообщение

[wpoms.]

В стране Лимонии есть двадцать городов. Между городами совершают авиарейсы самолёты двух авиационных компании – «Красные соколы» и «Голубая стрела». Об имеющихся авиарейсах известно, что: • для любых двух городов, одна и только одна из двух компаний имеет прямые рейсы (в обоих направлениях и без остановок) между двумя городами. Кроме того: • есть два города А и В, между которыми пассажир не может летать (с возможными пересадками), используя только самолеты авиакомпании «Красные соколы». Докажите, что для любых двух городов Лимонии, существует маршрут движения, по которому пассажир может путешествовать, используя только самолеты авиакомпании «Голубая стрела», и сделав не более одной остановки в каком-нибудь третьем городе.

@темы: Теория графов, Дискретная математика

Comments

[Дилетант]

wpoms., в первом условии "одна и только одна"?

[wpoms.]

Дилетант, в первом условии "одна и только одна"? - исправил на дословный перевод. А ведь хотел литературности

[Дилетант]

wpoms.,

[Adjirranirr]

Рассмотрим полный граф `G = (V,\ E)`, `|V| = 20`. По условию, `E = E_r \cup E_b`, где `E_r` — множество ребер-рейсов авиакомпании «Красные соколы», `E_b` — множество ребер-рейсов авиакомпании «Голубая стрела».
Так как существуют две вершины из `V` такие, что между ними нет пути, целиком вложенного в `E_r`, то граф `(V,\ E_r)` имеет по меньшей мере 2 компоненты связности.
Рассмотрим граф `(V,\ E_b)` и произвольную пару вершин `(v_1,\ v_2)`. Если `(v_1,\ v_2) \in E_b`, то это и есть искомый путь. Предположим `(v_1,\ v_2) \in E_r`. Так как `(V,\ E_r)` несвязен, то существует вершина `v_3`, не лежащая в компоненте связности, в которой лежат `v_1` и `v_2`. Но тогда по условию `(v_1,\ v_3) \notin E_r -> (v_1,\ v_3) \in E_b` и `(v_2,\ v_3) \notin E_r -> (v_2,\ v_3) \in E_b`, и искомый путь — `(v_1,\ v_3,\ v_2)`.