4. Нарисуйте граф, в котором 5 вершин и три компоненты связности. Постройте его матрицу смежности. Сколько существует разных графов, удовлетворяющих условию задачи?

Возьмём вершины \(1,2,3,4,5\) и рёбра \(\{1,2\},\{2,3\}\). Тогда компоненты связности: \(\{1,2,3\}\), \(\{4\}\), \(\{5\}\).

Матрица смежности:

Для неориентированных простых графов с фиксированными пятью вершинами считаем по типам размеров компонент:

• размеры \(3,1,1\): \(\binom53\cdot4=40\) графов;
• размеры \(2,2,1\): \(5\cdot3=15\) графов.

Итого: \(40+15=55\).

Ответ: пример приведён выше; всего существует 55 различных помеченных простых неориентированных графов.