Главная
Библиотека
Высшая математика
Какие утверждения верны? (1) Если в графе есть подграф, являющийся полным графом, то у графа нет плоской укладки. (2) Для...

Какие утверждения верны? (1) Если в графе есть подграф, являющийся полным графом, то у графа нет плоской укладки. (2) Для любого графа существует диаграмма в трехмерном пространстве, в которой ребра не имеют внутренних точек пересечения. (3) Если в каждой

«Какие утверждения верны? (1) Если в графе есть подграф, являющийся полным графом, то у графа нет плоской укладки. (2) Для любого графа существует диаграмма в трехмерном пространстве, в которой ребра не имеют внутренних точек пересечения. (3) Если в каждой»

6 ноября 2025
Высшая математика

Условие:

Какие утверждения верны?
(1) Если в графе есть подграф, являющийся полным графом, то у графа нет плоской укладки..
(2) Для любого графа существует диаграмма в трехмерном пространстве, в которой ребра не имеют внутренних точек пересечения.
(3) Если в каждой компоненте связности графа число ребер на единицу меньше числа вершин, то граф планарный.

Ответ дайте в формате последовательности 0 и 1 (например, 001): на первом месте запишите 1, если утверждение (1) верное, в противном случае запишите 0; на втором месте 1, если утверждение (2) верное, в противном случае запишите 0; и т.д.

Решение:

Рассмотрим каждое утверждение по отдельности. 1. Утверждение (1): «Если в графе есть подграф, являющийся полным графом, то у графа нет плоской укладки.» Объяснение: Под «полным графом» понимают граф, в котором каждая пара различных вершин соединена ребром. Но не любой полный граф является непланарным. Например, K₃ и K₄ – полные графы, и они планарны (для K₄ существует плоская укладка, а K₃ – треугольник). Непланарными являются лишь K₅ (полный граф на 5 вершинах) и K₃,₃ (полный двудольный граф с равными размерами долей по 3 вершины), либо графы, содержащие их в качестве подразделений. Так...