Текст задания

Все графы, фигурирующие в контрольной работе, обыкновенные, без петель и кратных ребер.

4.1. Существует ли граф с заданным набором степеней вершин? Если ответ да, то нарисовать подходящий граф, если нет — объяснить почему.

а) 1, 1, 2, 2, 2, 4;

б) 1, 2, 2, 3, 3, 4;

в) 2, 2, 3, 3, 4, 4.

4.2. На рис. 1 представлены 3 графа. Имеются ли среди них одинаковые? Если да, то перечислить буквы, которыми они обозначены; если нет, то для каждого графа, не имеющего пары, объяснить, почему данный граф не совпадает ни с каким из оставшихся.

Рис. 1

4.3. Сколько циклов длины 4 имеет граф, изображенный на рис. 1б?

4.4. Укажите мосты и точки сочленения для графа, представленного на рис. 2.

Рис. 2

4.5. Для графа, изображенного на рис. 3, построить: а) каркас наименьшего веса; б) каркас наибольшего веса.

Рис. 3

4.6. Некоторые графы из четырех, изображенных на рис. 4, описаны также некоторыми из таблиц 1–3. Укажите, какие именно. Ответ записать в виде: номер таблицы — буква рисунка (например, 3б), а на соответствующем рисунке расставить буквы от А до G, обозначающие вершины.

Рис. 4

Таблица 1

Таблица 2

Таблица 3

Решение

Решение контрольной работы оформлено в виде отчета в Word. Для получения решения необходимо оформить заказ и оплатить его.