Решение: Максимальное число ребер в несвязном графе с n вершинами

Задание 4. Вариант 1. Вопрос: Какое наибольшее число ребер может быть в несвязном графе с \(n\) вершинами? Решение: Чтобы простой граф (без петель и кратных ребер) с \(n\) вершинами был несвязным и при этом имел максимальное количество ребер, он должен состоять из двух компонент связности: 1. Полный граф \(K_{n-1}\), включающий в себя \(n-1\) вершину. 2. Одна изолированная вершина (отделенная от всех остальных). Количество ребер в полном графе с \(k\) вершинами вычисляется по формуле: \[ E = \frac{k(k-1)}{2} \] Подставим \(k = n - 1\): \[ E_{max} = \frac{(n-1)(n-1-1)}{2} = \frac{(n-1)(n-2)}{2} \] Ответ: \(\frac{(n-1)(n-2)}{2}\). Задание 5. Вариант 1. Дан граф матрицей смежности \(8 \times 8\). Обозначим вершины цифрами от 1 до 8. 1. Определим степени вершин (сумма единиц в каждой строке): \(deg(1) = 3\) (соседи: 2, 4, 8) \(deg(2) = 4\) (соседи: 1, 3, 7, 8) \(deg(3) = 3\) (соседи: 2, 4, 6) \(deg(4) = 3\) (соседи: 1, 3, 5) \(deg(5) = 2\) (соседи: 4, 7) \(deg(6) = 2\) (соседи: 3, 7) \(deg(7) = 4\) (соседи: 2, 5, 6, 8) \(deg(8) = 3\) (соседи: 1, 2, 7) 2. Проверка на Эйлеровость: Связный граф является Эйлеровым (содержит цикл, проходящий по всем ребрам по одному разу), если степени всех его вершин четны. В данном графе вершины 1, 3, 4, 8 имеют нечетную степень (3). Следовательно, граф не является Эйлеровым. 3. Проверка на Гамильтоновость: Граф называется Гамильтоновым, если он содержит цикл, проходящий через каждую вершину ровно один раз. Попробуем построить такой цикл вручную, перебирая пути: Начнем с вершины 1: \(1 \to 4 \to 5 \to 7 \to 6 \to 3 \to 2 \to 8 \to 1\) Проверим наличие этих ребер в матрице: - (1,4): есть - (4,5): есть - (5,7): есть - (7,6): есть - (6,3): есть - (3,2): есть - (2,8): есть - (8,1): есть Все ребра существуют, цикл проходит через все 8 вершин по одному разу и возвращается в исходную. Ответ: Граф не является Эйлеровым (есть вершины с нечетными степенями). Граф является Гамильтоновым. Гамильтонов цикл: \(1-4-5-7-6-3-2-8-1\).