Обсуждение участника:178.70.143.94 - История изменений

31.134.191.82: /* Связные графы */

2020-06-21T13:14:57Z

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

178.70.143.94: /* Связные графы */

2020-06-21T13:11:17Z

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

178.70.143.94: Новая страница: «==Связные графы== {{Определение |definition= CONN_{n} - количество связных графов порядк…»

2020-06-19T19:48:21Z

Новая страница: «==Связные графы== {{Определение |definition= <tex dpi="130">CONN_{n}</tex> - количество связных графов порядк…»

Новая страница

==Связные графы==
{{Определение
|definition=
<tex dpi="130">CONN_{n}</tex> - количество связных графов порядка <tex dpi="130">n</tex>.
}}

{{Лемма
|statement=
Количество помеченных графов порядка <tex dpi="150">n</tex> равно <tex dpi="150">2^{\binom{n}{2}}</tex>. Обозначается как <tex dpi="150">G_{n}</tex>.
}}

{{Утверждение
|statement=
<tex dpi="150">CONN_{n}=G_{n} - \frac{1}{n}\sum\limits_{k=1}^{n-1}k\binom{n}{k}G_{n-k}CONN_{k}</tex>, {{---}} количество связных графов порядка n.
|proof=

Рассмотрим соотношение количества связных и несвязных графов. Очевидно, что <tex dpi="150">CONN_{n}=G_{n}-X_{n}</tex>, где <tex dpi="150">X_{n}</tex> {{---}} количество несвязных графов. Также <tex dpi="150">X_{n}=\dfrac{Y_{n}}{n}</tex>, где <tex dpi="150">Y_{n}</tex> {{---}} количество корневых<ref>[[wikipedia:Rooted_graph | Wikipedia {{---}} Корневой граф]]</ref> несвязных графов.

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

Итого, для фиксированного <tex dpi="150">k</tex> количество корневых несвязных графов:

<tex dpi="150">Y_{n}=k\binom{n}{k}CONN_{k}G_{n-k}</tex>.

Значит, количество несвязных графов с <tex dpi="150">n</tex> вершинами равно:

<tex dpi="150">X_{n}=\frac{1}{n}\sum\limits_{k=1}^{n-1}k\binom{n}{k}CONN_{k}G_{n-k}</tex>

Таким образом количество связных графов порядка <tex dpi="130">n</tex>:

<tex dpi="150">CONN_{n}=G_{n}-\frac{1}{n}\sum\limits_{k=1}^{n-1}k\binom{n}{k}G_{n-k}CONN_{k}</tex>
}}

@@ Строка 7: / Строка 7: @@
 {{Лемма
 |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> вершинами.
 }}

@@ Строка 2: / Строка 2: @@
 {{Определение
 |definition=
-<tex dpi="130">CONN_{n}</tex> - количество связных графов порядка <tex dpi="130">n</tex>.
+<tex dpi="130">CONN_{n}</tex> - количество связных графов с <tex dpi="130">n</tex> вершинами.
 }}
 {{Лемма
 |statement=
-Количество помеченных графов порядка <tex dpi="150">n</tex> равно <tex dpi="150">2^{\binom{n}{2}}</tex>. Обозначается как <tex dpi="150">G_{n}</tex>.
+Количество помеченных графов с <tex dpi="130">n</tex> вершинами равно <tex dpi="150">2^{\binom{n}{2}}</tex>. Обозначается как <tex dpi="150">G_{n}</tex>.
 }}
 {{Утверждение
 |statement=
-<tex dpi="150">CONN_{n}=G_{n} - \frac{1}{n}\sum\limits_{k=1}^{n-1}k\binom{n}{k}G_{n-k}CONN_{k}</tex>, {{---}} количество связных графов порядка n.
+<tex dpi="150">CONN_{n}=G_{n} - \frac{1}{n}\sum\limits_{k=1}^{n-1}k\binom{n}{k}G_{n-k}CONN_{k}</tex>, {{---}} количество связных графов с <tex dpi="130">n</tex> вершинами.
 |proof=
 Рассмотрим соотношение количества связных и несвязных графов. Очевидно, что <tex dpi="150">CONN_{n}=G_{n}-X_{n}</tex>, где <tex dpi="150">X_{n}</tex> {{---}} количество несвязных графов. Также <tex dpi="150">X_{n}=\dfrac{Y_{n}}{n}</tex>, где <tex dpi="150">Y_{n}</tex> {{---}} количество корневых<ref>[[wikipedia:Rooted_graph | Wikipedia {{---}} Корневой граф]]</ref> несвязных графов.
-Вычислим <tex dpi="150">Y_{n}</tex>. Заметим, что, так как граф является несвязным, то в нём найдётся компонента связности, внутри которой лежит корневая вершина, а остальной граф будет представлять собой одну или более компонент связности. Переберем количество вершин в компоненте связности, содержащей корневую вершину. <tex dpi="150">(k=1\ldots n-1)</tex>. Для каждого <tex dpi="150">k</tex> посчитаем количество таких графов. Количество способов выбрать <tex dpi="150">k</tex> вершин из <tex dpi="150">n</tex> равно <tex dpi="150">\binom{n}{k}</tex>. Оставшийся граф является произвольным, таким образом количество помеченных графов в нем равно <tex dpi="150">G_{n-k}</tex>. Количество способов выделить корневую вершину в компоненте связности из <tex dpi="150">k</tex> вершин равно <tex dpi="150">k</tex>. Также количество связных графов в компоненте связности с корневой вершиной равно <tex dpi="150">CONN_{k}</tex>.
+Вычислим <tex dpi="150">Y_{n}</tex>. Заметим, что, так как граф является несвязным, то в нём найдётся компонента связности, внутри которой лежит корневая вершина, а остальной граф будет представлять собой одну или более компонент связности. Переберем количество вершин в компоненте связности, содержащей корневую вершину. <tex dpi="150">(k=1\ldots n-1)</tex>. Для каждого <tex dpi="150">k</tex> посчитаем количество таких графов. Количество способов выбрать <tex dpi="150">k</tex> вершин из <tex dpi="150">n</tex> равно <tex dpi="150">\binom{n}{k}</tex>. Оставшийся граф является произвольным, таким образом, количество помеченных графов в нем равно <tex dpi="150">G_{n-k}</tex>. Количество способов выделить корневую вершину в компоненте связности из <tex dpi="150">k</tex> вершин равно <tex dpi="150">k</tex>. Также количество связных графов в компоненте связности с корневой вершиной равно <tex dpi="150">CONN_{k}</tex>.
 Итого, для фиксированного <tex dpi="150">k</tex> количество корневых несвязных графов:
@@ Строка 27: / Строка 27: @@
 <tex dpi="150">X_{n}=\frac{1}{n}\sum\limits_{k=1}^{n-1}k\binom{n}{k}CONN_{k}G_{n-k}</tex>
-Таким образом количество связных графов порядка <tex dpi="130">n</tex>:
+Таким образом, количество связных графов с <tex dpi="130">n</tex> вершинами:
 <tex dpi="150">CONN_{n}=G_{n}-\frac{1}{n}\sum\limits_{k=1}^{n-1}k\binom{n}{k}G_{n-k}CONN_{k}</tex>
 }}