Контрольная работа по разделу «Теория графов»

Контрольная работа по разделу «Теория графов»

Задание 1. Раскрасьте вершины графа в минимальное количество цветов так, чтобы смежные вершины получали бы разные цвета. Для каждого графа укажите минимальное количество используемых цветов.

Задание 2. В стране Озёрная 7 озер, соединенных между собой 10 непересекающимися каналами, причём от каждого озера можно доплыть до любого другого. Сколько в этой стране островов? Нарисуйте получившийся граф.

Задание 3. Опишите граф с помощью матрицы смежности. Постройте матрицу инцидентности.

Задание 4. Подпишите типы и виды графов, укажите на примере одного графа вершину, начальную вершину, конечную вершину, дугу, ребро, петлю.

Задание 5. Найдите в данном графе эйлеров и гамильтонов цикл: