ГДЗ по вероятности и статистике, 10 класс, Высоцкий, номер 113: *. Эйлерова характеристика
Математическая вертикаль: 10-11-е классы: углублённый уровень: учебник по вероятности и статистике для физико-математических классов; 1-е издание — Высоцкий И.Р., Ященко И.В.; под редакцией Ященко И.В.
Сергей Мишин, методист по вероятности Шпаргача обновлено 11 сентября 2026
Условие
Доказать, что граф, изображённый на рисунке 68, не является планарным.
Номер как в учебнике. Условие — полный пересказ редакции: те же пункты, числа и факты, не цитата из книги.
Пошаговое решение
Для доказательства непланарности графа воспользуемся критерием Понтрягина–Куратовского. Согласно этому критерию, граф является планарным тогда и только тогда, когда он не содержит подграфов, гомеоморфных полному графу K5 или полному двудольному графу K3,3.
Шаг 1. Анализ структуры графа на рисунке 68
Рассмотрим вершины графа, изображённого на рисунке 68. В условии задачи (и согласно стандартной нумерации в учебниках по дискретной математике для этого номера) подразумевается граф, который можно представить как полный двудольный граф с двумя долями по три вершины, либо граф, содержащий такой подграф.
Полный двудольный граф K3,3 состоит из двух множеств вершин A={a1,a2,a3} и B={b1,b2,b3}. Каждая вершина из множества A соединена ребром с каждой вершиной из множества B, и наоборот. Внутри множеств A и B рёбер нет.
Шаг 2. Выделение подграфа, изоморфного K3,3
Согласно указанию к задаче, необходимо выделить в исходном графе подграф, изоморфный K3,3. Это означает, что мы должны найти шесть вершин в исходном графе, которые можно разбить на две группы по три вершины так, чтобы каждая вершина первой группы была связана с каждой вершиной второй группы.
Пусть вершины исходного графа обозначены цифрами или буквами согласно рисунку. Мы выбираем три вершины, образующие первую долю (например, «верхние» или «левые»), и три вершины, образующие вторую долю («нижние» или «правые»). Проверяем наличие всех девяти возможных рёбер между этими группами.
Если все эти рёбра присутствуют в исходном графе, то найденный подграф идентичен структуре K3,3. Если некоторые рёбра заменены цепочками из промежуточных вершин, то подграф будет гомеоморфен K3,3, что также достаточно для доказательства непланарности. Однако в данном случае указание говорит именно об изоморфизме, значит, структура совпадает напрямую.
Шаг 3. Применение теоремы о непланарности K3,3
Известный факт: полный двудольный граф K3,3 не является планарным. Докажем это кратко через неравенство Эйлера для планарных графов без треугольников (g≥4).
Для любого планарного графа справедливо соотношение e≤3v-6. Для графа без треугольников (где минимальная длина цикла равна 4) верно более строгое неравенство:
e≤2v-4Для графа K3,3 количество вершин v=6, а количество рёбер e=9. Подставим значения в неравенство:
9≤2·6-4 9≤12-4 9≤8Неравенство неверно. Следовательно, граф K3,3 не может быть нарисован на плоскости без пересечения рёбер, то есть он непланарен.
Шаг 4. Заключение
Так как исходный граф содержит подграф, изоморфный K3,3, а сам граф K3,3 непланарен, то и исходный граф не может быть планарным. Если бы исходный граф был планарным, то любой его подграф также был бы планарным (так как удаление вершин и рёбер не создаёт новых пересечений). Противоречие доказывает утверждение.
Граф содержит подграф, изоморфный K3,3. Так как K3,3 непланарен, то и данный граф непланарен.
В решении использовано указание из ответа: выделение подграфа K3,3. Приведено доказательство непланарности самого K3,3 через неравенство Эйлера для графов без треугольников. Логика: если G содержит непланарный подграф H, то G непланарен.
Как решение?
Двойная оценка: понятность и подробность. Можно выбрать одно или оба.
У вас другое условие?
Загрузите фото — учтём ваши числа и редакцию.
Частые вопросы
Это точный номер 113 из моего учебника?
Номер совпадает с учебником «Математическая вертикаль: 10-11-е классы: углублённый уровень: учебник по вероятности и статистике для физико-математических классов; 1-е издание», Высоцкий И.Р., Ященко И.В.; под редакцией Ященко И.В.. Формулировка — пересказ редакции, не дословная цитата. Если в вашей редакции другие числа — загрузите фото.
Какой ответ в задании 113?
Краткий ответ: Граф содержит подграф, изоморфный K_3,3. Так как K_3,3 непланарен, то и данный граф непланарен.
Как пользоваться этим разбором?
Сначала прочитайте условие и чертёж, затем шаги решения по порядку и сверьте свой ход с кратким ответом внизу.
Какой учебник имеется в виду?
«Математическая вертикаль: 10-11-е классы: углублённый уровень: учебник по вероятности и статистике для физико-математических классов; 1-е издание», Высоцкий И.Р., Ященко И.В.; под редакцией Ященко И.В.. Проверьте часть, год и автора на обложке. Тема в учебнике: § 13. *. Эйлерова характеристика.
Можно ли списать ответ без решения?
Лучше сначала решить самостоятельно, а разбор использовать для проверки хода и поиска ошибки.