ГДЗ по вероятности и статистике, 7 класс, Высоцкий, номер 125: Графы

Сумма степеней всех вершин в любом графе равна удвоенному числу рёбер (лемма о рукопожатиях). Вычислим сумму степеней:

Так как сумма чётная (12), то число рёбер будет целым: m=12/2=6. Таким образом, нам нужно построить два не изоморфных графа с 6 вершинами и 6 рёбрами, у которых степени вершин соответствуют заданному списку.

Попробуем построить связный граф. Обозначим вершины по их степеням: A_1,B₁ (степень 1), C_2,D₂ (степень 2), E_3,F₃ (степень 3).

Вершины степени 3 (E и F) должны быть соединены между собой или через другие вершины. Пусть E и F соединены ребром. Тогда каждой из них осталось добавить по 2 связи к другим вершинам.

• Соединим E с C и D.
• Соединим F с C и D.

Теперь посмотрим на степени текущих вершин: - E: связана с F,C,D -> степень 3 (готово). - F: связана с E,C,D -> степень 3 (готово). - C: связана с E,F -> степень 2 (готово). - D: связана с E,F -> степень 2 (готово). - A_1,B₁: пока изолированы (степень 0).

Нам нужно подключить A₁ и B₁, чтобы они имели степень 1, но при этом не нарушить степени остальных. Однако в текущей конфигурации все вершины C,D,E,F уже достигли нужной степени. Значит, этот конкретный способ соединения E-F-C-D-E (цикл длины 4 с хордой EF?) нет, это полный двудольный K_2,2 плюс ребро? Нет, E,F связаны, C,D связаны с обоими. Это цикл E-C-F-D-E плюс диагональ EF? Нет, CD не связано. Структура: E соединена с F,C,D. F соединена с E,C,D. Это образует треугольник E-F-C? Нет, если E-C есть, F-C есть, E-F есть, то это треугольник. И ещё E-D,F-D. То есть D тоже соединена с E и F. Получается, что C и D симметричны относительно пары E,F. Вершины C,D,E,F образуют подграф, где каждая пара (E,F) соединена, а C,D соединены с обеими E,F. Степени внутри этого блока: E(3),F(3),C(2),D(2). Всё верно. Но тогда куда деть A₁ и B₁? Если мы добавим ребро A₁-B₁, то их степени станут 1, но граф станет несвязным (компонента из 4 вершин и компонента из 2 вершин). Задача не требует связности, но обычно "различные графы" подразумевают разные структуры. Давайте сделаем первый граф несвязным , так как это проще всего реализовать для данного набора степеней.

Граф 1 (Несвязный): Компонента 1: Цикл из 4 вершин C-D-E-F-C? Нет, степени в цикле все 2. Нам нужны степени 3. Давайте пересмотрим. Набор степеней 1,1,2,2,3,3 допускает разложение на компоненты. Если взять компоненту с вершинами степеней 3,3,2,2, то сумма степеней 10, рёбер 5. Это может быть граф типа "бабочка" или просто две вершины степени 3, соединенные друг с другом и с двумя вершинами степени 2. Как мы нашли выше: E и F соединены, обе соединены с C и D. Степени: E=3,F=3,C=2,D=2. Оставшиеся вершины A и B имеют степени 1. Соединим их ребром A-B. Их степени станут 1. Граф состоит из двух компонент: одна с 4 вершинами, другая с 2 вершинами.

Построим теперь связный граф с теми же степенями. Чтобы граф был связным, вершины степени 1 (A и B) должны быть присоединены к остальной части графа.

Пусть основная часть снова содержит вершины E,F (степень 3) и C,D (степень 2). Но теперь мы будем использовать A и B для увеличения степеней других вершин или изменения структуры связей.

Рассмотрим цепочку или дерево с дополнительными рёбрами. 1. Начнём с вершины E (степень 3). Соединим её с A (степень 1), C (степень 2) и F (степень 3). - Текущие степени: E(3) — готово? Пока да, если больше никуда не вести. A(1) — готово. C(1) — нужно ещё 1. F(1) — нужно ещё 2. 2. Теперь работаем с F. Она уже имеет связь с E. Нужно добавить 2 связи. Соединим F с D (степень 2) и B (степень 1)? - Если соединить F-B, то B получит степень 1 (готово). F получит вторую связь (всего 2: с E и B). Ей нужна третья. - Соединим F с C? - Тогда C получает связь от E и F. Степень C становится 2 (готово). - F получает связи от E,B,C. Степень F становится 3 (готово). - Что с D? Мы упомянули D, но пока не использовали. У нас остались вершина D со степенью 0 и потребность в ней. - Пересчитаем использованные вершины: A,B,C,E,F. Осталась D. В условии 6 вершин. Я забыл про D в шаге 1.

Давайте аккуратно построим связный граф заново.

Вершины: v_1,v₂ (степень 1), v_3,v₄ (степень 2), v_5,v₆ (степень 3).

Идея: "Змейка" с петлями или ветвлениями. Соединим v₅ и v₆ ребром. Они главные узлы. v₅ должна иметь ещё 2 связи. v₆ должна иметь ещё 2 связи. Пусть v₅ соединена с v₁ (лист) и v₃. Пусть v₆ соединена с v₂ (лист) и v₄. Текущие степени: v₁:1 (ок) v₂:1 (ок) v₅:2 (нужно 3, есть связи с v_6,v_1,v₃) -> стоп, я сказал v₅-v₆, v₅-v₁, v₅-v₃. Степень v₅=3. Ок. v₆:2 (есть связи с v_5,v_2,v₄). Степень v₆=3. Ок. Остались v₃ и v₄. Сейчас у них степень 1 (связь только с v₅ и v₆ соответственно). Им нужно довести степень до 2. Соединим v₃ и v₄ ребром. Тогда: v₃ связана с v₅ и v₄. Степень 2. Ок. v₄ связана с v₆ и v₃. Степень 2. Ок. Все условия выполнены. Граф связен.

Структура: Две "звезды" с центрами v_5,v₆, соединённые между собой, и внешние концы v_3,v₄ замкнуты в цепочку v₃-v₄.

Мы получили два различных графа: 1. Первый граф является несвязным (состоит из двух компонент связности: одной с 4 вершинами и одной с 2 вершинами). 2. Второй граф является связным (все вершины достижимы из любой другой).

Так как один граф связен, а другой нет, они точно не изоморфны, то есть являются различными. Оба удовлетворяют условию наличия вершин со степенями 1,1,2,2,3,3.