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

[taki_net]

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

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

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

Comments

[mi-b.livejournal.com]

это неверно чисто математически. Формализация этого "лучше" - это что-то вроде того, что у нас есть множество графов с выделенными вершинами и на этих графах есть отношение частичного порядка "лучше". Дано, что это отношение удовлевторяет свойству, что если два графа отличаются только тем, что между какими-то двумя выделенными вершинами на одном графе единственный путь без циклов, а на другом - не единственный, то второй граф лучше. Из этого не следует, что граф с тремя путями между этими узлами лучше графа с двумя. Это видно уже на контрпримере, когда на первом графе всего две вершины, соединенных одним ребром, а на втором графе - они же соединены двумя ребрами. Второй лучше первого, но это не значит, что граф с тремя ребрами между этими же вершинами будет лучше второго.

[taki-net.livejournal.com]

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

[mi-b.livejournal.com]

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

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

[taki-net.livejournal.com]

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