ГДЗ по вероятности и статистике, 10 класс, Высоцкий, номер 77: Изоморфные графы. Плоские и планарные графы
Математическая вертикаль: 10-11-е классы: углублённый уровень: учебник по вероятности и статистике для физико-математических классов; 1-е издание — Высоцкий И.Р., Ященко И.В.; под редакцией Ященко И.В.
Дмитрий Орлов, методист по вероятности Шпаргача обновлено 11 сентября 2026
Условие
а) Существует ли граф с 4 вершинами степеней 0, 1, 2, 3? Если да — приведите пример, если нет — докажите.
б) Существует ли такой же граф без петель и кратных рёбер?
Номер как в учебнике. Условие — полный пересказ редакции: те же пункты, числа и факты, не цитата из книги.
Пошаговое решение
Для решения задачи вспомним основные свойства графов. Сумма степеней всех вершин любого графа равна удвоенному количеству рёбер (лемма о рукопожатиях). Также важно различать понятия: граф может содержать петли и кратные рёбра, а простой граф — нет.
Шаг 1. Анализ пункта а) для общего графа
Нам даны степени четырёх вершин: 0,1,2,3. Проверим необходимое условие существования такого графа. Сумма степеней должна быть чётным числом, так как она равна 2m, где m — количество рёбер.
∑di=0+1+2+3=6Число 6 является чётным, значит, по теореме Эрдёша–Галлаи (или просто по лемме о рукопожатиях), такой мультиграф (граф с возможными петлями и кратными рёбрами) существует.
Пример построения:
- Обозначим вершины A,B,C,D со степенями d(A)=0,d(B)=1,d(C)=2,d(D)=3.
- Вершина A изолирована (степень 0).
- Вершина D имеет степень 3. Она не соединена с A. Значит, все её инцидентности приходятся на B и C.
- Пусть между D и B есть одно ребро. Тогда степень B становится 1 (так как B больше ни с кем не соединена, кроме D). Это подходит под условие d(B)=1.
- Осталось обеспечить степень D=3 и C=2. Сейчас у D уже есть связь с B (1 ребро). Нужно ещё 2 связи для D. У C пока 0 связей, нужно 2.
- Соединим D и C двумя рёбрами (кратное ребро).
- Проверка степеней в полученном графе:
- A: 0 рёбер →d(A)=0.
- B: 1 ребро к D →d(B)=1.
- C: 2 ребра к D →d(C)=2.
- D: 1 ребро к B и 2 ребра к C →d(D)=3.
Таким образом, граф с такими степенями существует.
Шаг 2. Анализ пункта б) для простого графа
В условии спрашивается, существует ли такой же граф без петель и кратных рёбер. Такой граф называется простым. В простом графе с n вершинами максимальная степень любой вершины не может превышать n-1, так как вершина может быть соединена максимум со всеми остальными n-1 вершинами ровно одним ребром.
У нас n=4 вершины. Максимально возможная степень вершины в простом графе равна 4-1=3. Дана степень 3, что допустимо.
Однако давайте проверим совместность всех степеней одновременно. Предположим, что такой простой граф существует. Вершины имеют степени 0,1,2,3.
- Пусть вершина V3 имеет степень 3. В простом графе из 4 вершин это означает, что V3 соединена со всеми остальными тремя вершинами (V0,V1,V2).
- Если V3 соединена с V0, то степень вершины V0 должна быть хотя бы 1 (так как есть ребро V3-V0).
- Но по условию степень вершины V0 равна 0. Это противоречие.
Изолированная вершина (степень 0) не может существовать в связной компоненте вместе с вершиной максимальной степени n-1, если только n=1. Для n=4 наличие вершины степени 3 обязывает все остальные вершины иметь степень не менее 1.
Следовательно, набор степеней (0,1,2,3) невозможен для простого графа.
а) Да, существует.
б) Нет, не существует.
Пункт а): сумма степеней четная (6), пример строится через кратные ребра или петли (в данном случае использованы кратные ребра для наглядности, но можно и петлю: например, D-B, D-C, петля на D? Нет, петля дает +2 к степени. Если петля на D, то d(D) увеличивается на 2. Вариант с петлей: A(0), B(1)-D, C(2)-D, D? Нет. Проще всего показать пример с кратными ребрами или объяснить через четность суммы. Пункт б): классическое противоречие. Вершина степени n-1 смежна со всеми, поэтому вершины степени 0 быть не может.
Как решение?
Двойная оценка: понятность и подробность. Можно выбрать одно или оба.
У вас другое условие?
Загрузите фото — учтём ваши числа и редакцию.
Частые вопросы
Это точный номер 77 из моего учебника?
Номер совпадает с учебником «Математическая вертикаль: 10-11-е классы: углублённый уровень: учебник по вероятности и статистике для физико-математических классов; 1-е издание», Высоцкий И.Р., Ященко И.В.; под редакцией Ященко И.В.. Формулировка — пересказ редакции, не дословная цитата. Если в вашей редакции другие числа — загрузите фото.
Какой ответ в задании 77?
Краткий ответ: а) Да, существует. б) Нет, не существует.
Как пользоваться этим разбором?
Сначала прочитайте условие и чертёж, затем шаги решения по порядку и сверьте свой ход с кратким ответом внизу.
Какой учебник имеется в виду?
«Математическая вертикаль: 10-11-е классы: углублённый уровень: учебник по вероятности и статистике для физико-математических классов; 1-е издание», Высоцкий И.Р., Ященко И.В.; под редакцией Ященко И.В.. Проверьте часть, год и автора на обложке. Тема в учебнике: § 10. Изоморфные графы. Плоские и планарные графы.
Можно ли списать ответ без решения?
Лучше сначала решить самостоятельно, а разбор использовать для проверки хода и поиска ошибки.