Страница 53 номер 79, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни
Постройте два неизоморфных графа, в каждом из которых по 6 вершин со степенями 1, 2, 2, 2, 3, 4.
Сумма данных степеней \(1 + 2 + 2 + 2 + 3 + 4 = 14\) равна удвоенному числу рёбер, поэтому в каждом графе должно быть \(14 : 2 = 7\) рёбер.
Первый граф: вершины \(A\), \(B\), \(C\), \(D\), \(E\), \(F\) и рёбра \(AB\), \(AC\), \(AD\), \(AF\), \(BC\), \(BE\), \(DE\); степени вершин: \(A\) — 4, \(B\) — 3, \(C\) — 2, \(D\) — 2, \(E\) — 2, \(F\) — 1.
Второй граф: те же вершины и рёбра \(AB\), \(AC\), \(AD\), \(AE\), \(BC\), \(BD\), \(EF\); степени вершин: \(A\) — 4, \(B\) — 3, \(C\) — 2, \(D\) — 2, \(E\) — 2, \(F\) — 1.
В обоих графах по 6 вершин, по 7 рёбер и один и тот же набор степеней 1, 2, 2, 2, 3, 4.
При изоморфизме соответствующие вершины имеют равные степени: соответствие рёбер взаимно однозначно и переводит рёбра при вершине в рёбра при соответствующей вершине, поэтому вершина участвует в записи рёбер столько же раз, сколько и соответствующая ей вершина.
Предположим, что графы изоморфны. Вершина степени 1 в каждом графе ровно одна — это \(F\), значит, эти вершины соответствуют друг другу. Единственное ребро при вершине \(F\) первого графа — \(AF\), второго — \(EF\), значит, соответствуют друг другу и их вторые концы: вершина \(A\) первого графа и вершина \(E\) второго.
Но степень вершины \(A\) равна 4, а степень вершины \(E\) равна 2, тогда как у соответствующих вершин степени должны быть равны, — получилось противоречие, значит, графы не изоморфны.
Ответ: годятся граф с рёбрами \(AB\), \(AC\), \(AD\), \(AF\), \(BC\), \(BE\), \(DE\) и граф с рёбрами \(AB\), \(AC\), \(AD\), \(AE\), \(BC\), \(BD\), \(EF\): в обоих по 6 вершин со степенями 1, 2, 2, 2, 3, 4, но в первом вершина степени 1 соединена с вершиной степени 4, а во втором — с вершиной степени 2, поэтому графы не изоморфны.
Постройте два неизоморфных графа, в каждом из которых по 6 вершин со степенями 1, 2, 2, 2, 3, 4.
Сумма данных степеней равна \(1 + 2 + 2 + 2 + 3 + 4 = 14\). По теореме о сумме степеней вершин она равна удвоенному числу рёбер, поэтому в каждом из графов должно быть \(14 : 2 = 7\) рёбер.
В первом графе возьмём вершины \(A\), \(B\), \(C\), \(D\), \(E\), \(F\) и рёбра \(AB\), \(AC\), \(AD\), \(AF\), \(BC\), \(BE\), \(DE\). Степени вершин: \(A\) — 4, \(B\) — 3, \(C\) — 2, \(D\) — 2, \(E\) — 2, \(F\) — 1.
Во втором графе возьмём те же вершины и рёбра \(AB\), \(AC\), \(AD\), \(AE\), \(BC\), \(BD\), \(EF\). Степени вершин: \(A\) — 4, \(B\) — 3, \(C\) — 2, \(D\) — 2, \(E\) — 2, \(F\) — 1.
В обоих графах по 6 вершин, по 7 рёбер и один и тот же набор степеней 1, 2, 2, 2, 3, 4.
Осталось проверить, что эти графы не изоморфны.
Заметим, что при изоморфизме соответствующие вершины имеют равные степени. В самом деле, соответствие рёбер взаимно однозначно и переводит рёбра при вершине в рёбра при соответствующей вершине, поэтому вершина участвует в записи рёбер столько же раз, сколько и соответствующая ей вершина.
Предположим, что графы изоморфны. В первом графе ровно одна вершина степени 1 — это \(F\), и во втором ровно одна — тоже \(F\). Значит, они соответствуют друг другу.
Единственное ребро при вершине \(F\) первого графа — \(AF\), а единственное ребро при вершине \(F\) второго графа — \(EF\). Значит, эти рёбра соответствуют друг другу, а тогда соответствуют друг другу и их вторые концы: вершина \(A\) первого графа и вершина \(E\) второго.
Но степень вершины \(A\) в первом графе равна 4, а степень вершины \(E\) во втором равна 2, тогда как у соответствующих вершин степени должны быть равны. Получилось противоречие, значит, графы не изоморфны.
Ответ: годятся граф с рёбрами \(AB\), \(AC\), \(AD\), \(AF\), \(BC\), \(BE\), \(DE\) и граф с рёбрами \(AB\), \(AC\), \(AD\), \(AE\), \(BC\), \(BD\), \(EF\): в обоих по 6 вершин со степенями 1, 2, 2, 2, 3, 4, но в первом вершина степени 1 соединена с вершиной степени 4, а во втором — с вершиной степени 2, поэтому графы не изоморфны.
