Дано $%N$% помеченных вершин, посчитать сколько всего простых неориентированных графов без изолированных вершин?

вот здесь есть формула

Есть ли доказательство простыми человеческими рассуждениями типа индукции?

задан 7 Мар 20:04

Если нет ограничения насчёт изолированных вершин, то для k вершин ответом будет 2^{k(k-1)/2}. Далее стандартно применяем формулу включений и исключений, которая и даёт вот это:

a(n) = Sum_{k=0..n} (-1)^(n-k)binomial(n, k)2^binomial(k, 2).

Индукция как таковая тут не нужна, то есть не надо выражать a(n+1) через a(n).

(7 Мар 21:29) falcao

@falcao непонятно, почему именно такая формула. То есть нужно от общего числа возможных графов отнять случаи когда есть одна изолированная вершина, две и так далее.

(7 Мар 23:25) Bazalt

@Bazalt: Вам надо посмотреть в учебнике вывод формулы включений и исключений. Это стандартное комбинаторное средство. Понять её в общем виде проще, чем для частного случая.

(7 Мар 23:33) falcao

@falcao, да я понять не могу какие случаи мы учитываем дважды.

(7 Мар 23:36) Bazalt

@Bazalt: это нельзя понять без изучения техники включений и исключений. Там всё устроено сложнее. Почитайте этот материал в книжках -- их много. Есть у М.Холла в "Комбинаторике", есть у Верещагина и Шеня в "Началах теории множеств", и много где ещё. Это само по себе интересно и полезно.

(7 Мар 23:40) falcao

@falcao общий случай понятен. До в данном, например есть 4 вершины, всего может быть 64 графа, теперь надо отнять случаи, когда как минимум 1 вершина изолирована, мы можем 4 способами изолировать одну из вершин, при этом для оставшихся трех есть 8 способов нарисовать граф. Я не понимаю следующий момент, уже на данном этапе мы имеем 4 графа, где все вершины изолированы и их надо отнять от 64 графов, где такой был только 1. Помогите пожалуйста сформулировать свойтво объектов которые вычитаются и прибавляются...

(8 Мар 9:15) Bazalt

@Bazalt: проблема вот в чём. Когда мы полагаем 1-ю вершину изолированной, и рассматриваем граф на остальных, то в нём также могут быть изолированные вершины. Поэтому, после вычитания четырёх величин (для каждой из них), кое-что вычитается дважды. Потом оно возвращается: делаем две вершины фиксированными (по всем парам), и рассматриваем граф на остальных. Оказывается, что и это не даёт верный ответ, и надо прибавить те случаи, когда три вершины фиксированы, и рассмотрен граф на остальных. И так далее. Это я на популярном уровне описал, что такое идея включений и исключений. Далее см. учебник.

(8 Мар 13:47) falcao

@falcao Да мне сама идея понятна, как доказать то, что когда мы что-то вычитаем, а что-то прибавляем, то мы все случаи рассмотрим и в результате мы получим то что надо в единственном экземпляре? Если задача такая простая, что-же к ней решения то нет нигде, второй день ищу?

(8 Мар 14:07) Bazalt

@Bazalt: ответ на вопрос, как это доказать, как раз и содержится в формуле включений и исключений. Желая проверить это каким-то прозрачным и очевидным способом, Вы зря теряете время. Это важный теоретический факт, его полезно один раз капитально изучить. И потом уже применять к многим задачам -- включая эту.

Задача, кстати, не простая, но она сравнительно легко следует из общей формулы. Которую даже искать не надо -- она много где есть.

(8 Мар 16:29) falcao
показано 5 из 9 показать еще 4
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,463
×629
×369
×34
×16

задан
7 Мар 20:04

показан
162 раза

обновлен
8 Мар 16:29

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru