10–11 классы Изоморфные графы. Плоские и планарные графы § 10. Изоморфные графы. Плоские и планарные графы

ГДЗ по вероятности и статистике, 10 класс, Высоцкий, номер 90: Изоморфные графы. Плоские и планарные графы

Математическая вертикаль: 10-11-е классы: углублённый уровень: учебник по вероятности и статистике для физико-математических классов; 1-е издание — Высоцкий И.Р., Ященко И.В.; под редакцией Ященко И.В.

Ольга Кузнецова, методист по вероятности Шпаргача обновлено 11 сентября 2026

← 89 91 →

Условие

Может ли у графа существовать ровно два неизоморфных остовных дерева? Если да, привести пример.

Номер как в учебнике. Условие — полный пересказ редакции: те же пункты, числа и факты, не цитата из книги.

Пошаговое решение

Для решения задачи необходимо вспомнить определение остовного дерева и понятие изоморфизма графов. Остовное дерево связного графа G — это подграф, который является деревом и содержит все вершины графа G. Два графа называются изоморфными, если существует взаимно однозначное соответствие между их вершинами, сохраняющее смежность.

Шаг 1. Анализ минимальных случаев

Рассмотрим простейшие связные графы:

Граф с 2 вершинами (K₂): Единственное остовное дерево — сам граф. Количество неизоморфных деревьев: 1.
Граф с 3 вершинами:
- Если это путь P₃, то единственное остовное дерево — он сам. Результат: 1.
- Если это треугольник K₃, то удаление любого ребра дает путь P₃. Все полученные деревья изоморфны друг другу (все они являются путями длины 2). Результат: 1.
Граф с 4 вершинами:
- Цикл C₄: удаление любого ребра дает путь P₄. Все деревья изоморфны. Результат: 1.
- Звезда S₃ (центр + 3 листа): только одно остовное дерево (сама звезда). Результат: 1.
- Полный граф K₄: имеет 16 остовных деревьев. Они делятся на два класса изоморфизма: "звезды" (степени вершин 3,1,1,1) и "пути" (степени 2,2,1,1). Есть еще тип "T-образная форма"? Нет, для 4 вершин есть только два типа деревьев: путь P₄ и звезда K_1,3. В K₄ можно получить оба типа. Значит, количество неизоморфных остовных деревьев равно 2.

Шаг 2. Проверка примера K₄

Рассмотрим полный граф K₄ с вершинами extA,B,C,D.

Остовное дерево на 4 вершинах может иметь следующие распределения степеней вершин (сумма степеней равна 2·(4-1)=6):

Тип "Путь" (P₄): Степени вершин 1,2,2,1. Пример: рёбра (A,B),(B,C),(C,D). Это дерево существует в K₄.
Тип "Звезда" (K_1,3): Степени вершин 3,1,1,1. Пример: рёбра (A,B),(A,C),(A,D). Это дерево также существует в K₄.

Других типов деревьев на 4 вершинах не существует. Поскольку P₄ и K_1,3 имеют разные последовательности степеней, они неизоморфны .

Таким образом, у графа K₄ ровно два класса изоморфизма остовных деревьев.

Шаг 3. Формулировка ответа

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

В качестве другого примера можно рассмотреть граф, состоящий из двух треугольников, соединенных общим ребром (ромб с диагональю), но там тоже могут быть нюансы. Однако K₄ — самый канонический и простой пример.

Ответ

Да, например, у полного графа K₄.

Задача требует знания теории графов. Ключевой момент — перебор всех возможных типов деревьев на малом числе вершин. Для n=4 существуют только два неизоморфных дерева: путь P4 и звезда K1,3. Полный граф K4 содержит остовные деревья обоих типов.

Как решение?

Двойная оценка: понятность и подробность. Можно выбрать одно или оба.

Подробность

У вас другое условие?

Загрузите фото — учтём ваши числа и редакцию.

Решить по фото

Частые вопросы

Это точный номер 90 из моего учебника?

Номер совпадает с учебником «Математическая вертикаль: 10-11-е классы: углублённый уровень: учебник по вероятности и статистике для физико-математических классов; 1-е издание», Высоцкий И.Р., Ященко И.В.; под редакцией Ященко И.В.. Формулировка — пересказ редакции, не дословная цитата. Если в вашей редакции другие числа — загрузите фото.

Какой ответ в задании 90?

Краткий ответ: Да, например, у полного графа K_4.

Как пользоваться этим разбором?

Сначала прочитайте условие и чертёж, затем шаги решения по порядку и сверьте свой ход с кратким ответом внизу.

Какой учебник имеется в виду?

«Математическая вертикаль: 10-11-е классы: углублённый уровень: учебник по вероятности и статистике для физико-математических классов; 1-е издание», Высоцкий И.Р., Ященко И.В.; под редакцией Ященко И.В.. Проверьте часть, год и автора на обложке. Тема в учебнике: § 10. Изоморфные графы. Плоские и планарные графы.

Можно ли списать ответ без решения?

Лучше сначала решить самостоятельно, а разбор использовать для проверки хода и поиска ошибки.