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

Сумма степеней вершин равна 1+2+2+2+3+4=14. Поскольку сумма степеней должна быть чётной (равна удвоенному числу рёбер), такой граф существует. Число рёбер m=14/2=7.

Обозначим вершины по их степеням: v₁ (степень 1), v_2a,v_2b,v_2c (степень 2), v₃ (степень 3), v₄ (степень 4).

Построим граф так, чтобы вершина максимальной степени v₄ была связана с вершиной минимальной степени v₁. Это создаст «висячую» ветку от центра.

• Вершина v₄ имеет степень 4. Соединим её с v₁, v₃, v_2a и v_2b.
• Вершина v₁ исчерпала свою степень (связана только с v₄).
• Вершина v₃ имеет степень 3. Одна связь уже есть с v₄. Осталось две связи. Соединим v₃ с v_2c и ещё раз с v_2a? Нет, лучше создать цикл. Пусть v₃ связана с v_2c и v_2b.
• Проверим степени промежуточных вершин:
• v_2a связана с v₄. Нужна ещё одна связь. Соединим v_2a с v_2c.
• v_2b связана с v₄ и v₃. Степень 2 достигнута.
• v_2c связана с v₃ и v_2a. Степень 2 достигнута.

Структура G₁: Есть треугольник v₄-v₃-v_2b-v₄? Нет, давайте пересчитаем связи аккуратно.

Давайте проще: пусть v₄ соединена с v_3,v_2a,v_2b,v_2c. Тогда у v₄ степень 4. У v₃ пока 1 связь, нужно ещё 2. У всех v₂ пока по 1 связи, нужно по 1.

Добавим ребра между остальными вершинами так, чтобы получить нужные степени. Пусть v₃ соединена с v_2a и v_2b. Теперь степень v₃=1+2=3 (готово). Теперь у v_2a связи: с v₄ и v₃ (степень 2, готово). У v_2b связи: с v₄ и v₃ (степень 2, готово). Осталась вершина v_2c (связана с v₄, степень 1) и v₁ (степень 0). Соединим v_2c с v₁. Теперь степень v_2c=2, степень v₁=1. Все степени совпадают: v₄(4),v₃(3),v_2a(2),v_2b(2),v_2c(2),v₁(1).

Особенность G₁: Вершина v₁ (степень 1) присоединена к вершине v_2c (степень 2), которая в свою очередь присоединена к v₄ (степень 4). Путь от конца до центра: v₁-v_2c-v₄.

Чтобы граф был неизоморфным первому, изменим структуру так, чтобы вершина степени 1 (v₁) была присоединена непосредственно к вершине степени 4 (v₄), а не через промежуточную вершину степени 2, или изменим окружение вершины степени 3.

Попробуем другой вариант: пусть v₄ соединена с v_1,v_3,v_2a,v_2b. Степень v₁=1 (готово). Степень v₄=4 (готово). Остались v₃ (нужно 3 связи, есть 1 с v₄), v_2a (нужно 2, есть 1 с v₄), v_2b (нужно 2, есть 1 с v₄), v_2c (нужно 2, есть 0). Нужно добавить 3 ребра среди оставшихся вершин v_3,v_2a,v_2b,v_2c. Пусть v₃ соединена с v_2a и v_2b. Теперь степень v₃=1+2=3 (готово). Степень v_2a=1+1=2 (готово). Степень v_2b=1+1=2 (готово). Осталась изолированная пока v_2c (нужна степень 2). Но все остальные вершины уже закрыты! Значит, этот набор связей невозможен без изменения предыдущих шагов или создания цикла из v_2c. Давайте построим G₂ иначе. Пусть вершины степени 2 образуют цепочку или цикл. В G₁ мы имели путь v₁-v_2c-v₄. В G₂ сделаем так, чтобы v₁ была присоединена к v₃ (вершине степени 3). Конструкция G₂: 1. v₄ соединена с v_3,v_2a,v_2b,v_2c. (Степень v₄=4). 2. v₃ соединена с v₄ и v₁. (Пока степень 2, нужна 3). 3. v₁ соединена с v₃. (Степень 1, готово). 4. Нам нужно добить степени v₃ (нужно +1), v_2a,v_2b,v_2c (у каждой пока 1, нужно +1). 5. Соединим v₃ с v_2a. Теперь степень v₃=3 (готово). Степень v_2a=2 (готово). 6. Остались v_2b и v_2c, у которых степень 1. Соединим их между собой: v_2b-v_2c. 7. Теперь степень v_2b=2, степень v_2c=2. Проверка степеней G₂: v₄: 4 связи (v_3,v_2a,v_2b,v_2c) v₃: 3 связи (v_4,v_1,v_2a) v₁: 1 связь (v₃) v_2a: 2 связи (v_4,v₃) v_2b: 2 связи (v_4,v_2c) v_2c: 2 связи (v_4,v_2b) Набор степеней: 4,3,2,2,2,1. Совпадает.

Сравним окрестности вершины степени 1 (v₁) в обоих графах.

• В графе G₁: Вершина v₁ соседствует с вершиной v_2c, которая имеет степень 2. Эта вершина v_2c соседствует с v₁ и v₄ (степень 4). То есть путь от v₁ до вершины максимальной степени проходит через вершину степени 2: v₁-v_2c(2)-v₄(4).
• В графе G₂: Вершина v₁ соседствует с вершиной v₃, которая имеет степень 3. Эта вершина v₃ соседствует с v₁, v₄ (степень 4) и v_2a (степень 2). То есть путь от v₁ до вершины максимальной степени проходит через вершину степени 3: v₁-v₃(3)-v₄(4).

В любом изоморфном отображении вершина степени 1 должна перейти в вершину степени 1. Её единственный сосед должен перейти в единственного соседа соответствующей вершины. В G₁ сосед вершины степени 1 имеет степень 2. В G₂ сосед вершины степени 1 имеет степень 3. Так как степени соседей различаются (2≠3), графы не могут быть изоморфны.