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

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

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

Анна Соколова, методист по вероятности Шпаргача обновлено 11 сентября 2026

← 96 102 →

Условие

В дереве 1001 вершина. Может ли быть так, что

а) длина любой цепи в этом дереве не больше 1

б) длина любой цепи в этом дереве не больше 2

в) в этом дереве найдётся цепь длиной 1000?

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

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

Для решения задачи вспомним основные свойства дерева. Дерево — это связный граф без циклов. Важное свойство: в дереве с n вершинами ровно n-1 ребро. Также длина цепи (пути) определяется количеством рёбер на ней.

Шаг 1. Анализ пункта а)

Условие гласит: длина любой цепи не больше 1. Это означает, что максимальная дистанция между любыми двумя вершинами равна 1 или меньше. Если есть хотя бы одна цепь длины 1, то две вершины соединены ребром. Если все цепи имеют длину ≠0 (разные вершины), то максимальная длина цепи 1 подразумевает, что любые две различные вершины либо совпадают (длина 0), либо соединены напрямую одним ребром (длина 1).

Рассмотрим структуру такого графа. Если в графе есть три вершины A,B,C, и они попарно соединены, то образуется цикл A-B-C-A, чего в дереве быть не может. Значит, если максимальная длина пути равна 1, то граф должен состоять из одной вершины (тривиальное дерево) или двух вершин, соединенных ребром. В любом другом случае, если вершин больше двух, найдутся две вершины, не соединенные напрямую, но так как граф связный, путь между ними будет содержать минимум 2 ребра (через промежуточную вершину). Таким образом, для дерева с 1001 вершиной (n>2) невозможно, чтобы длина любой цепи была не больше 1. Минимальная возможная максимальная длина цепи (диаметр) для дерева с n вершинами достигается в «звезде» и равна 2 (если n>2), а для n=2 равна 1.

Вывод: Нет, так как при n=1001 существуют вершины, расстояние между которыми равно 2 (например, листья звезды относительно центра) или больше.

Шаг 2. Анализ пункта б)

Условие: длина любой цепи не больше 2. Нам нужно проверить, существует ли дерево с 1001 вершиной, диаметр которого равен 2.

Рассмотрим типичную структуру дерева с малым диаметром — звезду . Пусть у нас есть одна центральная вершина C, к которой присоединены остальные 1000 вершин L_1,L_2,…,L₁₀₀₀ (листья).

Проверим длины цепей в таком графе:

Цепь от центра до листа: C-L_i. Длина 1.
Цепь от листа до листа через центр: L_i-C-L_j. Длина 2.
Других путей нет, так как между листьями прямых связей нет (иначе был бы цикл).

Максимальная длина цепи в такой звезде равна 2. Количество вершин: 1+1000=1001. Количество ребер: 1000. Циклов нет. Граф связен. Это корректное дерево.

Вывод: Да, такое возможно. Примером служит звезда с центром и 1000 концами.

Шаг 3. Анализ пункта в)

Условие: в этом дереве найдётся цепь длиной 1000.

Длина цепи 1000 означает наличие пути, состоящего из 1000 рёбер. Такой путь проходит через 1001 вершину (так как число вершин на пути равно числу рёбер плюс один).

Рассмотрим простейший вид дерева — путь (или линейное дерево). Расположим все 1001 вершину в одну линию: v₁-v₂-v₃-…-v₁₀₀₁.

В таком графе:

Вершин: 1001.
Ребер: 1000.
Циклов нет.
Граф связен.

Это является деревом. В нём существует единственная цепь, проходящая через все вершины от v₁ до v₁₀₀₁. Её длина равна количеству рёбер, то есть 1000.

Вывод: Да, такое возможно. Примером служит линейное дерево (цепочка из всех вершин).

Ответ

а) Нет

б) Да

в) Да

Пункт а): Для дерева с n>2 минимальный возможный диаметр равен 2 (звезда). Диаметр 1 возможен только для K2 (2 вершины). Так как вершин 1001, ответ 'Нет'. Пункт б): Звезда с 1 центром и 1000 листьями имеет диаметр 2. Ответ 'Да'. Пункт в): Линейное дерево (путь) из 1001 вершины содержит цепь длины 1000. Ответ 'Да'.

Как решение?

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

Подробность

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

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

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

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

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

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

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

Краткий ответ: а) Нет б) Да в) Да.

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

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

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

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

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

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