связные графы

[max(Im)]

Как можно показать, что связных помеченных (по вершинам) графов на 6 вершинах больше, чем несвязных?
Перебором не получится, так как всего шестивершинных графов $2^{15}$ штук...
Есть рекуррентная формула для числа помеченных связных графов на $n$ вершинах, выведенная через производящую функцию. Ее можно даже вывести через корневые деревья. Но ей пользоваться неудобно, так как надо считать много. Но хочется сделать без нее совсем. Как быть?

[svv]

max(Im) писал(а):

всего шестивершинных графов $2^{15}$ штук

Откуда так много?

Может, это пригодится:
http://e-maxx.ru/algo/counting_connected_graphs

[Хорхе]

svv в сообщении #499157 писал(а):

max(Im) писал(а):

всего шестивершинных графов $2^{15}$ штук

Откуда так много?

Там писалось про помеченные графы. Их вот именно так много.

Ну а причина совсем простая. Дополнение к несвязному графу связно и даже двусвязно. Ч.т.д., так как, например, есть связные графы, не являющиеся двусвязными.

(На самом деле, почти все графы связны и даже почти все двусвязны: пропорция недвусвязных графов среди графов на $n$ вершинах экспоненциально убывает по $n$. См. Bolobas "Random graphs".)

-- Пт ноя 04, 2011 10:24:43 --

Впрочем, можно и без ссылки на книжку, поля не слишком узки. Для двух вершин вероятность того, что они не связаны путем длины 2, равна $(\frac34)^{n-2}$, поэтому вероятность недвусвязности не превосходит ${n\choose 2}(\frac34)^{n-2}$, то есть экспоненциально мала.

[max(Im)]

Хорхе
Спасибо! Про факт о связности одного из $G$ и $\overline{G}$ я и забыл, как раз из-за того, что доказывал, что почти все графы связны, и пытался на 6 вершинах сделать таким же подходом.

[svv]

Хорхе писал(а):

Ну а причина совсем простая. Дополнение к несвязному графу связно и даже двусвязно. Ч.т.д., так как, например, есть связные графы, не являющиеся двусвязными.

Наверное, можно и так:
Дополнение к несвязному графу связно. Ч.т.д., так как есть связные графы, дополнение к которым также связно.