Количество графов c пронумерованными вершинами...

Сообщение №6054 от Alexander V. Kil 17 декабря 2002 г. 17:11
Тема: Количество графов c пронумерованными вершинами...

Нетрудно догадаться, что количество разных графов с пронумерованными вершинами равно 2^(n(n-1)/2). А как вычислить Np(n) - количество таких же графов, содержащих Kp (полный подграф из p вершин)?


Отклики на это сообщение:

> Нетрудно догадаться, что количество разных графов с пронумерованными вершинами равно 2^(n(n-1)/2). А как вычислить Np(n) - количество таких же графов, содержащих Kp (полный подграф из p вершин)?

У такого графа, очевидно, фиксировано существует p(p-1)/2 ребер, а остальные ребра могут выбираться произвольно. Т.о. число таких графов зависит от выбранных p вершин, которые составят K_p, и выбранных оставшихся ребер, и равно С_n^p*2^{n(n-1)/2-p(p-1)/2}



> У такого графа, очевидно, фиксировано существует p(p-1)/2 ребер, а остальные ребра могут выбираться произвольно. Т.о. число таких графов зависит от выбранных p вершин, которые составят K_p, и выбранных оставшихся ребер, и равно С_n^p*2^{n(n-1)/2-p(p-1)/2}

Сабж, потому что при таком подсчете некоторые графы будут считаться несколько раз. Простейший случай - K_n будет учитываться аж C_n^p раз!


> > У такого графа, очевидно, фиксировано существует p(p-1)/2 ребер, а остальные ребра могут выбираться произвольно. Т.о. число таких графов зависит от выбранных p вершин, которые составят K_p, и выбранных оставшихся ребер, и равно С_n^p*2^{n(n-1)/2-p(p-1)/2}

> Сабж, потому что при таком подсчете некоторые графы будут считаться несколько раз. Простейший случай - K_n будет учитываться аж C_n^p раз!

Но вы же считаете помеченные графы, а не графы с точностью до изоморфизма! Для помеченных графов моя формула верна. Формула 2^{n(n-1)/2} также дает число помеченных графов на n вершинах, а не число попарно неизоморфных графов. Для числа графов с точностью до изоморфизма точной формулы не существует, существуют лишь ассимптотические, например, формула Пойа. Поэтому могу предположить, что и для вашей задачи, если считать графы попарно неизоморфными, точной формулы не будет.


Прошу прощения, что без цитаты, но все и так понятно. Для начала могу предложить вычислить число графов с n вершинами, содержащих полный подраф из 2 вершин. По Вашей формуле C_n^2*2^(n(n-1)/2-2(2-1)/2) = C_n^2*2^(n(n-1)/2), то есть число таких графов в C_n^2=n(n-1)/2 раз больше чем вообще помеченных графов! Не находите ли это сущим бредом?
А дело все в том, как я и сказал, что многие графы считаются несколько раз. Так как не рисуя табличек это объяснить сложно, а здесь их рисовать неудобно, прошу самостоятельно до этого дойти. Извините...


> Прошу прощения, что без цитаты, но все и так понятно. Для начала могу предложить вычислить число графов с n вершинами, содержащих полный подраф из 2 вершин. По Вашей формуле C_n^2*2^(n(n-1)/2-2(2-1)/2) = C_n^2*2^(n(n-1)/2), то есть число таких графов в C_n^2=n(n-1)/2 раз больше чем вообще помеченных графов! Не находите ли это сущим бредом?
> А дело все в том, как я и сказал, что многие графы считаются несколько раз. Так как не рисуя табличек это объяснить сложно, а здесь их рисовать неудобно, прошу самостоятельно до этого дойти. Извините...


Ладно, ваша правда. Ошибся. Кстати, не кажется ли вам сущим бредом, что
n(n-1)/2-2(2-1)/2 = n(n-1)/2 ?

А теперь правильный ответ. Будем перебирать p-элементные подмножества, составляющие K_p, так, чтобы каждое последующее отличалось от предыдущего только одним элементом. Тогда имеем: для первого множества число помеченных графов с ним в качестве K_p равно 2^{n(n-1)/2-p(p-1)/2}, для второго-
2^{n(n-1)/2-p(p-1)/2-1}, для третьего - 2^{n(n-1)/2-p(p-1)/2-2} и т.д. Суммируя, имеем (2^{n(n-1)/2-p(p-1)/2})*(1-1/2^{C_n^k})*2.


>
> Ладно, ваша правда. Ошибся. Кстати, не кажется ли вам сущим бредом, что
> n(n-1)/2-2(2-1)/2 = n(n-1)/2 ?

> А теперь правильный ответ. Будем перебирать p-элементные подмножества, составляющие K_p, так, чтобы каждое последующее отличалось от предыдущего только одним элементом. Тогда имеем: для первого множества число помеченных графов с ним в качестве K_p равно 2^{n(n-1)/2-p(p-1)/2}, для второго-
> 2^{n(n-1)/2-p(p-1)/2-1}, для третьего - 2^{n(n-1)/2-p(p-1)/2-2} и т.д. Суммируя, имеем (2^{n(n-1)/2-p(p-1)/2})*(1-1/2^{C_n^k})*2.

В последней формуле вместо k читайте p.


> Ладно, ваша правда. Ошибся. Кстати, не кажется ли вам сущим бредом, что
> n(n-1)/2-2(2-1)/2 = n(n-1)/2 ?

Да, здесь я лопухнулся, думал одно, а писал другое (-1 забыл поставить). Сорри...


> > А теперь правильный ответ. Будем перебирать p-элементные подмножества, составляющие K_p, так, чтобы каждое последующее отличалось от предыдущего только одним элементом. Тогда имеем: для первого множества число помеченных графов с ним в качестве K_p равно 2^{n(n-1)/2-p(p-1)/2}, для второго-
> > 2^{n(n-1)/2-p(p-1)/2-1}, для третьего - 2^{n(n-1)/2-p(p-1)/2-2} и т.д.

Т.е. N_p(n) = (2^{n(n-1)/2-p(p-1)/2})*(1-1/2^{C_n^p})*2.
Фантастика! Я подставил числа и ответ получился очень похожим на правду!

Одна только маленькая проблемка (вернее 2):
1) я не совсем понимаю, как это так получается (не могли бы вы объяснить по-подробнее?)
2) если проходить все подмножества так, чтобы каждое отличалось от предыдущего на один элемент, получаем задачку об обходе каждой вершины графа только один раз. (Гамильтонова цепь) Я просто не помню критериев ее существования...


Я попробовал вычислить N_3(6) и получилось дробное число (!) Отсюда следует 2 варианта - либо неверно посчитана сумма, либо я не так распознал формулу...


> Я попробовал вычислить N_3(6) и получилось дробное число (!) Отсюда следует 2 варианта - либо неверно посчитана сумма, либо я не так распознал формулу...


Да, не получается. Обидно. Надо еще додумать. Идея вроде правильная.


Физика в анимациях - Купить диск - Тесты по физике - Графики on-line

Реклама:
Rambler's Top100