Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 4 ] 
Автор Сообщение
 Заголовок сообщения: Задача об неорграфах однородных степени 2
СообщениеДобавлено: 09 окт 2016, 11:42 
Не в сети
Продвинутый
Зарегистрирован:
18 сен 2016, 11:50
Сообщений: 55
Cпасибо сказано: 11
Спасибо получено:
1 раз в 1 сообщении
Очков репутации: 3

Добавить очки репутацииУменьшить очки репутации
Цитирую свой учебник:

Цитата:
Граф, степени всех вершин которого одинаковы и равны числу l, на-
зывается однородным степени l. ... Сколько существует однородных степени
2 графов с шестью вершинами?


Под графами тут фактически имеются в виду НЕорграфы. Я думаю об том как решить эту задачу, но в голову приходит только топорный метод перебора (например, через построение дерева). Можно ли эту задачу решить более элегантным путём, то есть через формулы? И если да, то не могли бы дать мне подсказку? Единственное что я тут смог выяснить так это что число рёбер должен быть равно 6.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача об неорграфах однородных степени 2
СообщениеДобавлено: 11 окт 2016, 11:54 
Не в сети
Продвинутый
Зарегистрирован:
18 сен 2016, 11:50
Сообщений: 55
Cпасибо сказано: 11
Спасибо получено:
1 раз в 1 сообщении
Очков репутации: 3

Добавить очки репутацииУменьшить очки репутации
[Подумал что решил задачу, написал тут решение, а потом обнаружил что оно неправильно. Сейчас посмотрю в чём дело и либо напишу правильное решение, либо распишу подробно место об которое споткнулся.]

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача об неорграфах однородных степени 2
СообщениеДобавлено: 12 окт 2016, 15:50 
Не в сети
Продвинутый
Зарегистрирован:
18 сен 2016, 11:50
Сообщений: 55
Cпасибо сказано: 11
Спасибо получено:
1 раз в 1 сообщении
Очков репутации: 3

Добавить очки репутацииУменьшить очки репутации
Получил 80, правильный ли у меня результат?

Как я к нему пришёл:

Сначала я был вообще без понятия что делать, но потом я решил методом перебора найти количество неорграфов (далее просто графов) для n<6 в надежде что я увижу какие-нибудь закономерности которые помогут мне решить туже задачу при n=6. Я нашёл все графы при n равных 3 и 4. Я правда лишь частично нашёл графы для n=5. Но я заметил там закономерность каждая ветка дерева решений которую я проработал дала мне по два графа. Всего у меня было 6 веток, из них я проработал только две, следовательно итого графов должно получится 12 при n=5.

Делая перебор для n=4 и, в особенности, для n=5, я заметил такую вещь как тупиковые ветви. Эти ветви получались если я соединял несколько точек графа в виде замкнутой ломаной, но при этом несколько других точек оставались без рёбер. Оставшиеся без рёбер точки с одной стороны не могли соединиться с теми точками, но и соединение между собой, эдакий клуб отверженных, тоже было бесмысленно ибо их было слишком мало (одна или две) чтобы сформировать замкнутую ломанную. Вот если бы их было хотя бы 3... Хотя постойте-ка, ведь если n=6, то такое вполне возможно! Граф тогда будет выглядеть как два отдельных треугольника.

Анализируя вид тех графов что я получил перебором, а также тупиковые ветви, я заметил что при всей свой замысловатости это фактически замкнутые кривые, один граф - одна замкнутая кривая. Итого существует два общих случая для n=6, граф либо одна замкнутая кривая, либо же это два отдельных треугольника. Соответсвенно чтобы найти все возможные графы мы должны найти кардинальное число каждого из этих двух множеств, а потом их суммировать.

С треугольниками всё просто, мы используем комбинаторическую формулу для сочетаний БЕЗ повторений, r=3 n=6. В самом деле, нам достаточно выбрать лишь три вершины для первого треугольника, а второй треугольник автоматически получится из оставшихся вершин. Ну и разумеется порядок выбранных вершин безразличен, "a,b,c" ничем не лучше, и не хуже, чем "b,a,c"

А вот со вторым множеством всё оказалось сложней. Сначала я по наивности подумал что оно находится как перестановка без повторений из 6 элементов, то есть факториал шести. В самом деле, ведь если у нас все вершины соединены последовательно, то при обходе графа мы переходим от одной вершины к другой как если бы они были членами некого упорядоченного списка.

Вроде бы всё верно, но я решил проверить этот подход на примитивнейшем графе n=3. И получил неверный ответ. При n=3 возможен только один граф, а ведь 3!=6. Откуда лишние варианты? Потом меня осенило: да, для нас порядок символов важен, но далеко не всякий. Некоторые перестановки могут описывать фактически один и тот же граф. Разные записи одно и того же графа возникают при начале движения с разных вершин. Мы можем первым делом посетить вершину "а", потом вершину "b", и наконец вершину "с". Однако, мы также можем сперва посетить вершину "b", потом "с" и наконец "a". Или "с", потом "а" и напоследок "b". Во всех трёх случаях граф один и тот же. В общем случае если у нас n вершин, то у нас n вариантов для выбора начальной вершины для обхода, и следовательно n дублей. Поэтому чтобы избавиться от них мы должны n! разделить на n.

Однако этого недостаточно. Если n=3, то деление n! на n даст 2. Но мы-то знаем что граф один. Откуда лишний граф? Оказывается соль в том, что даже если мы начнём движение с одной и той же вершины, мы можем получить другую последовательность символов при движении в противоположном направлении. Например, если нашей первой вершиной является "а", то мы можем получить две разные последовательности символов. Если мы будем двигаться в одном направлении, то получим "аbc", а в другом - "acb". Чтобы избавиться от такой двойственности надо разделить n! на 2. Итого получаем что n! надо разделить на 2n.

Ну а теперь время подсчёта. При n=6 множество треугольников состоит из 20 графов, а множество замкнутых ломаных кривых состоит из 60 графов. 20+60=80. Итого 80 графов.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача об неорграфах однородных степени 2
СообщениеДобавлено: 13 окт 2016, 15:28 
Не в сети
Продвинутый
Зарегистрирован:
18 сен 2016, 11:50
Сообщений: 55
Cпасибо сказано: 11
Спасибо получено:
1 раз в 1 сообщении
Очков репутации: 3

Добавить очки репутацииУменьшить очки репутации
Цитата:
при всей свой замысловатости это фактически замкнутые кривые


Пардон, здесь и далее под "замкнутой кривой" я имел в виду "замкнутую ломанную".

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 4 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Алгоритм решения однородных уравнений

в форуме Алгебра

TsaAst

46

1203

22 мар 2023, 14:56

Системы линейных однородных уравнений

в форуме Линейная и Абстрактная алгебра

Viktoriya9977

4

233

18 дек 2018, 17:34

Задача на степени

в форуме Задачи со школьных и студенческих олимпиад

Fireman

2

228

12 апр 2019, 01:41

Замена в линейных однородных дифференциальных уравнениях

в форуме Дифференциальные и Интегральные уравнения

CookKostia

4

339

08 авг 2020, 10:45

Задача с корнем 5й степени

в форуме Тригонометрия

mielofon

10

577

03 апр 2017, 10:56

Найти координаты центра тяжести однородных пластинок

в форуме Интегральное исчисление

letuswedge

4

768

27 ноя 2017, 22:49

Задача физмат класса на степени с рациональным показателем

в форуме Алгебра

Martin_haus

4

92

16 мар 2024, 04:00

Найти остаток от деления числа в степени в степени

в форуме Теория чисел

hejihe4135

7

1586

03 мар 2020, 16:51

Как из степени (-1/у) перейти к степени (1-у)/у

в форуме Начала анализа и Другие разделы школьной математики

afraumar

2

436

13 фев 2015, 10:45

Степени

в форуме Алгебра

dsgalyamov

1

574

21 дек 2014, 14:36


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 21


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved