Обсуждение участника:178.70.143.94 — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Связные графы)
(Связные графы)
 
Строка 7: Строка 7:
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
Количество помеченных графов с <tex dpi="130">n</tex> вершинами равно <tex dpi="150">2^{\binom{n}{2}}</tex>. Обозначается как <tex dpi="150">G_{n}</tex>.
+
<tex dpi="150">G_{n} = 2^{\binom{n}{2}}</tex>, где <tex dpi="150">G_{n}</tex> {{---}} количество помеченных графов с <tex dpi="130">n</tex> вершинами.
 
}}
 
}}
  

Текущая версия на 16:14, 21 июня 2020

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

Определение:
[math]CONN_{n}[/math] - количество связных графов с [math]n[/math] вершинами.


Лемма:
[math]G_{n} = 2^{\binom{n}{2}}[/math], где [math]G_{n}[/math] — количество помеченных графов с [math]n[/math] вершинами.
Утверждение:
[math]CONN_{n}=G_{n} - \frac{1}{n}\sum\limits_{k=1}^{n-1}k\binom{n}{k}G_{n-k}CONN_{k}[/math], — количество связных графов с [math]n[/math] вершинами.
[math]\triangleright[/math]

Рассмотрим соотношение количества связных и несвязных графов. Очевидно, что [math]CONN_{n}=G_{n}-X_{n}[/math], где [math]X_{n}[/math] — количество несвязных графов. Также [math]X_{n}=\dfrac{Y_{n}}{n}[/math], где [math]Y_{n}[/math] — количество корневых[1] несвязных графов.

Вычислим [math]Y_{n}[/math]. Заметим, что, так как граф является несвязным, то в нём найдётся компонента связности, внутри которой лежит корневая вершина, а остальной граф будет представлять собой одну или более компонент связности. Переберем количество вершин в компоненте связности, содержащей корневую вершину. [math](k=1\ldots n-1)[/math]. Для каждого [math]k[/math] посчитаем количество таких графов. Количество способов выбрать [math]k[/math] вершин из [math]n[/math] равно [math]\binom{n}{k}[/math]. Оставшийся граф является произвольным, таким образом, количество помеченных графов в нем равно [math]G_{n-k}[/math]. Количество способов выделить корневую вершину в компоненте связности из [math]k[/math] вершин равно [math]k[/math]. Также количество связных графов в компоненте связности с корневой вершиной равно [math]CONN_{k}[/math].

Итого, для фиксированного [math]k[/math] количество корневых несвязных графов:

[math]Y_{n}=k\binom{n}{k}CONN_{k}G_{n-k}[/math].

Значит, количество несвязных графов с [math]n[/math] вершинами равно:

[math]X_{n}=\frac{1}{n}\sum\limits_{k=1}^{n-1}k\binom{n}{k}CONN_{k}G_{n-k}[/math]

Таким образом, количество связных графов с [math]n[/math] вершинами:

[math]CONN_{n}=G_{n}-\frac{1}{n}\sum\limits_{k=1}^{n-1}k\binom{n}{k}G_{n-k}CONN_{k}[/math]
[math]\triangleleft[/math]