Упражнение на принцип математической индукции

[taki_net]

Дано:
(1) согласно экономической науке, две дороги (дублирующих - с одинаковым началом и концом) ВСЕГДА лучше, чем одна http://taki-net.livejournal.com/2315886.html?thread=47882862#t47882862

(2) в рыночной экономике реализуются более выгодные варианты.

Доказать: между любыми двумя пунктами со временем будет построено бесконечно много дорог (точнее: большее, чем любое наперед заданное число N).

Comments

[mi-b.livejournal.com]

по ссылке написано лишь "Да в любом случае две альтернативные дороги выгоднее, чем одна." А где написано про любой граф, который станет лучше от добавления еще одного ребра?

Если хочется сузить определение "лучше" с общих частичных порядков и получить что-нибудь более экономическое, можно посмотреть на упорядочивания, которые не любят графы, которые легко распадаются на несвязные. Например, на каждом графе определить функцию полезности, которая убывает с добавлением каждого нового ребра, но сильно наказывает графы, которые распадаются на несвязные с удалением одного ребра. Например, функция -[число ребер] - 10*[число ребер, удаление которых нарушит связность]. Такая функция задает отношение порядка, и осмысленна экономически, если изредка происходят "аварии", которые временно перекрывают одно ребро, стоимость полной изоляции одной из верщин много больше стоимости нового ребра, а вероятность двойной аварии мала. С таким отношением порядка две дороги лучше одной, но три хуже двух.

[taki-net.livejournal.com]

Весь диалог читать надо.