Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 4 ] |
|
Автор | Сообщение | |
---|---|---|
roboq6 |
|
|
Цитата: Граф, степени всех вершин которого одинаковы и равны числу l, на- зывается однородным степени l. ... Сколько существует однородных степени 2 графов с шестью вершинами? Под графами тут фактически имеются в виду НЕорграфы. Я думаю об том как решить эту задачу, но в голову приходит только топорный метод перебора (например, через построение дерева). Можно ли эту задачу решить более элегантным путём, то есть через формулы? И если да, то не могли бы дать мне подсказку? Единственное что я тут смог выяснить так это что число рёбер должен быть равно 6. |
||
Вернуться к началу | ||
roboq6 |
|
|
[Подумал что решил задачу, написал тут решение, а потом обнаружил что оно неправильно. Сейчас посмотрю в чём дело и либо напишу правильное решение, либо распишу подробно место об которое споткнулся.]
|
||
Вернуться к началу | ||
roboq6 |
|
|
Получил 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 графов. |
||
Вернуться к началу | ||
roboq6 |
|
|
Цитата: при всей свой замысловатости это фактически замкнутые кривые Пардон, здесь и далее под "замкнутой кривой" я имел в виду "замкнутую ломанную". |
||
Вернуться к началу | ||
[ Сообщений: 4 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Алгоритм решения однородных уравнений
в форуме Алгебра |
46 |
1203 |
22 мар 2023, 14:56 |
|
Системы линейных однородных уравнений
в форуме Линейная и Абстрактная алгебра |
4 |
233 |
18 дек 2018, 17:34 |
|
Задача на степени | 2 |
228 |
12 апр 2019, 01:41 |
|
Замена в линейных однородных дифференциальных уравнениях | 4 |
339 |
08 авг 2020, 10:45 |
|
Задача с корнем 5й степени
в форуме Тригонометрия |
10 |
577 |
03 апр 2017, 10:56 |
|
Найти координаты центра тяжести однородных пластинок
в форуме Интегральное исчисление |
4 |
768 |
27 ноя 2017, 22:49 |
|
Задача физмат класса на степени с рациональным показателем
в форуме Алгебра |
4 |
92 |
16 мар 2024, 04:00 |
|
Найти остаток от деления числа в степени в степени
в форуме Теория чисел |
7 |
1586 |
03 мар 2020, 16:51 |
|
Как из степени (-1/у) перейти к степени (1-у)/у
в форуме Начала анализа и Другие разделы школьной математики |
2 |
436 |
13 фев 2015, 10:45 |
|
Степени
в форуме Алгебра |
1 |
574 |
21 дек 2014, 14:36 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 21 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |