Упражнения

1. Перечислить все деревья, которые можно получить для 2, 3, 4, 5, 6 вершин.

2. Для графа, приведенного на рисунке построить все остовы.

Рис.1 Рис.2 Рис.3

3. Для дерева приведенного на рисунке 7 определить вершины максимального типа, найти все диаметральные цепи. Убедится в том, что они проходят через центр.

4. Для графов, приведенных на рисунке определить: цикломатическое число, число внутренней устойчивости и число внешней устойчивости.

Рис. 1 Рис. 2 Рис. 3

5. Источник информации может передавать код из 4-х различных однобуквенных сигналов . Эти сигналы, в результате возникающего при передаче возмущения, воспринимаются на приемной станции как сигналы , причем могут иметь двойное истолкование, как, например, на рисунке 1.

Рис.1

Определить, из каких сигналов надо составить код, чтобы исключить неправильное восприятие на приемной станции. Найти максимальное количество таких сигналов.

6. В пунктах могут быть расположены источники излучения. Если источники расположенные в пунктах и влияют друг на друга, то они соединены на рисунке ребром (см. рис. 2).

Рис. 2

Можно ли расположить в каких либо из данных пунктов 4 или 3 источника, не поражающих друг друга?

7. Объекты расположены так, как показано на рисунке 3.

Рис. 3

Объекты, которые просматриваются друг из друга, соединены на рисунке ребром. Определить, в какие объекты достаточно поместить наблюдателей, чтобы они в совокупности просматривали все объекты.

6. Для частично ориентированной сети привести два различных потока в сети, найти величину каждого потока. Перечислить все простые сечения сети. Определить максимальную величину потока, пользуясь теоремой Форда-Фалкерсона.