Выбери верные утверждения

Предмет: Математика
Раздел: Теория графов

Рассмотрим каждое утверждение подробно.

1. Полный граф - гамильтонов.

Полный граф — это граф, в котором каждая пара вершин соединена ребром. Обозначим полный граф на ( n ) вершинах как ( K_n ).

Гамильтонов цикл — это цикл, проходящий через каждую вершину ровно один раз.

В полном графе ( K_n ) при ( n \geq 3 ) существует гамильтонов цикл, так как можно пройти по всем вершинам, переходя по ребрам, которые есть между любыми двумя вершинами.

Вывод: утверждение верно.

2. Эйлеров граф является гамильтоновым графом.

Эйлеров граф — граф, в котором существует эйлеров цикл, то есть цикл, проходящий по каждому ребру ровно один раз.

Гамильтонов граф — граф, в котором существует гамильтонов цикл.

Наличие эйлерова цикла не гарантирует наличие гамильтонова цикла, и наоборот. Это разные свойства.

Пример: граф, состоящий из двух треугольников, соединенных одной вершиной, может быть эйлеровым, но не гамильтоновым.

Вывод: утверждение неверно.

3. Самодополняемый граф - не содержит изолированных вершин.

Самодополняемый граф — граф, изоморфный своему дополнению.

Изолированная вершина — вершина без ребер.

Если в графе есть изолированная вершина, то в дополнении к ней будет вершина, соединённая со всеми остальными (то есть степень ( n-1 )). Такие структуры не изоморфны.

Вывод: утверждение верно.

4. Полный граф - эйлеров.

Эйлеров граф существует, если и только если граф связен и степень каждой вершины чётна.

В полном графе ( K_n ) степень каждой вершины равна ( n-1 ).

• Если ( n ) — чётное, то ( n-1 ) — нечётное, значит степень вершин нечётна — эйлерова цикла нет.
• Если ( n ) — нечётное, то ( n-1 ) — чётное, значит степень всех вершин чётна — эйлеров цикл существует.

Вывод: полный граф эйлеров только при нечётном числе вершин.

Итог:

• Полный граф - гамильтонов: верно
• Эйлеров граф является гамильтоновым графом: неверно
• Самодополняемый граф - не содержит изолированных вершин: верно
• Полный граф - эйлеров: верно только при нечётном числе вершин

Если в условии не оговорено количество вершин, то утверждение о полном графе как эйлеровом графе в общем виде неверно.

Ответ:

Верны утверждения:

 \text{1. Полный граф - гамильтонов} \

 \text{3. Самодополняемый граф - не содержит изолированных вершин} \

 \text{4. Полный граф - эйлеров (только при нечётном числе вершин)} \

Неверно:

 \text{2. Эйлеров граф является гамильтоновым} \