Основы синтеза и диагностирования автоматов. Воронин В.В. - 70 стр.

UptoLike

Составители:

Рубрика:

скная способность. Указать маршрут между двумя пунктами (любы-

ми), который бы обеспечивал максимальный транспортный поток.

Задана структурная схема САУ, найти передаточную функцию

между двумя любыми сигналами этой схемы и др.

Формулировка задач на языке теории графов часто облегчает

процесс вычислений и позволяет на едином языке формулировать

задачи, кажущиеся очень далекими друг

от друга в своей первона-

чальной постановке.

Рассмотрим содержательную постановку задачи о Кёнигсберг-

ских мостах, решенную Эйлером в 1736 г. В Кёнигсберге было два

острова, соединенных семью мостами с берегами реки и друг с дру-

гом так, как показано на рис. 2.33.

Задача состоит в следующем: найти маршрут

прохождения всех

четырех частей суши, который начинался бы с любой из них, кон-

чался на этой же части и ровно один раз проходил по каждому мос-

ту. Можно эмпирически пробовать решить эту задачу. Эйлер доказал

невозможность такого маршрута. Для доказательства он перешел к

графу, в котором части суши обозначил вершинами, а

мосты - реб-

рами (рис. 2.34). Он доказал, что для существования специального

пути, необходимо, чтобы граф был связным и каждая его вершина

должна быть инцидентна четному числу ребер. Данный граф связ-

ный, но не каждая его вершина инцидентна четному числу ребер.

Рис. 2.34

Рис. 2.33