СПРОСИ ПРОФИ
👍
0
👎 00

Теория графов, неизоморфные графы

Всем добрый день! Несколько дней маюсь с этой задачей, помогите, пожалуйста :(
Условие: «Сколько существует попарно неизоморфных графов порядка 9, в которых ровно по 3 вершины степени 2?»
Пыталась решить по следующему алгоритму:
1. Выбор 3 вершин из 9 на роль вершин со степенью 2: число сочетаний из 9 по 3 = 84 способа
2. Рассмотрение вариантов расположения рёбер между выбранными 3 вершинами: 0 рёбер, 1 ребро, 2 ребра, 3 ребра
3. Для каждого количества рёбер между 3 вершинами степени 2 рассматриваем варианты. Например, для 1 ребра (таких вариантов 3: ребро между 1 и 2, 1 и 3, 2 и 3): тогда получаем, что для 2 вершин обеспечена степень 1 (это те, которые соединены ребром), а для 3-ей степень 0. Значит нужно выбрать по 1 вершине из множества, условно, вершин 4-9 для вершин со степенью 1, и 2 вершины из того же множества для вершины со степенью 0, чтобы обеспечить всем трём вершинам степени 2.
Выбор одной вершины из 6: число сочетаний из 6 по 1 = 6 способов.
Выбор двух вершин из 6: число сочетаний из 6 по 2 = 15 способов
Получим 6*6*15 способов обеспечения степени 2 трём вершинам. Но нужно учесть случаи, в которых может быть выбрана одна и та же вершина из множества 4-9, т.к. от трёх вершин к одной не может идти 4 ребра, максимум 3. Таких случаев (со степенью 4 для выбранной вершины из множества 4-9) 6, т.к. это одна из 6 вершин.
Тогда способов обеспечения степени 2 трём изначально выбранным вершинам: 6*6*15-6 = 6*89
Также учтём, что то самое одно ребро между тремя вершинами 2 степени может располагаться 3 способами. Значит получим 3*6*89 способов обеспечения степени 2.

Схожий анализ для 0, 2 и 3 рёбер между вершинами 2 степени, где на случай с 2 ребрами придётся домножение на 3, т.к. 2 ребра могут быть выбраны 3 способами.
Вот здесь я и торможу, т.к. такое ощущение, что какой-то слишком запутанный алгоритм. Но иной в голову не приходит
Далее планировалось:
4. 84 способа выбрать 3 вершины * (3*6*89 способов обеспечить степень 2 при 1 ребре между этими 3 вершинами + кол-во способов при 2 рёбрах + количество способов при 3 рёбрах + количество способов при 0 рёбер) * 2^15...
2^15 — это количество вариантов расстановки оставшихся возможных 15 рёбер. Т.к. после обеспечения степени 2 трём выбранным вершинам вне зависимости от количества рёбер между ними максимально степень у вершин из множества 4-9 может быть 3 (т.к. 3 вершины выбрано), при этом граф 9 порядка, значит степень у вершины может быть максимум 8. Во множестве вершин 4-9 вершин 6, значит от каждой может быть проведено максимум 5 рёбер, т.е. как раз максимально достижимая степень 8. Таким образом, на каждый из способов сформировать неизоморфные графы будет приходиться по 2^15 вариантов за счёт добавления рёбер (15 рёбер, т.к. ситуация как при формировании полного графа на 6 вершинах: 6*5/2 = 15).
5. Каким-то образом учесть те случаи, где на выходе получается граф с больше, чем тремя вершинами степени 2. Соответственно, подсчитать количество таких случаев с учётом чётности суммы степеней вершин, далее вычесть это количество из результата умножения 84 способов на способы обеспечения степени 2 (начало пункта 4.)
Скажите, пожалуйста, мои размышления верны, или где-то есть ошибки? И нет ли способа попроще/покороче? Заранее преогромное спасибо за помощь!!!

Задайте свой вопрос по высшей математике
профессионалам

Сейчас онлайн 75 репетиторов по высшей математике
Получите ответ профи быстро и бесплатно
ASK.PROFI.RU © 2020-2024