Обсуждение участника:178.70.143.94 — различия между версиями
(Новая страница: «==Связные графы== {{Определение |definition= <tex dpi="130">CONN_{n}</tex> - количество связных графов порядк…») |
(→Связные графы) |
||
| (не показана 1 промежуточная версия 1 участника) | |||
| Строка 2: | Строка 2: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
| − | <tex dpi="130">CONN_{n}</tex> - количество связных графов | + | <tex dpi="130">CONN_{n}</tex> - количество связных графов с <tex dpi="130">n</tex> вершинами. |
}} | }} | ||
{{Лемма | {{Лемма | ||
|statement= | |statement= | ||
| − | + | <tex dpi="150">G_{n} = 2^{\binom{n}{2}}</tex>, где <tex dpi="150">G_{n}</tex> {{---}} количество помеченных графов с <tex dpi="130">n</tex> вершинами. | |
}} | }} | ||
{{Утверждение | {{Утверждение | ||
|statement= | |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>, {{---}} количество связных графов | + | <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= | |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">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> количество корневых несвязных графов: | Итого, для фиксированного <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="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> | <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> | ||
}} | }} | ||
Текущая версия на 16:14, 21 июня 2020
Связные графы
| Определение: |
| - количество связных графов с вершинами. |
| Лемма: |
, где — количество помеченных графов с вершинами. |
| Утверждение: |
, — количество связных графов с вершинами. |
|
Рассмотрим соотношение количества связных и несвязных графов. Очевидно, что , где — количество несвязных графов. Также , где — количество корневых[1] несвязных графов. Вычислим . Заметим, что, так как граф является несвязным, то в нём найдётся компонента связности, внутри которой лежит корневая вершина, а остальной граф будет представлять собой одну или более компонент связности. Переберем количество вершин в компоненте связности, содержащей корневую вершину. . Для каждого посчитаем количество таких графов. Количество способов выбрать вершин из равно . Оставшийся граф является произвольным, таким образом, количество помеченных графов в нем равно . Количество способов выделить корневую вершину в компоненте связности из вершин равно . Также количество связных графов в компоненте связности с корневой вершиной равно . Итого, для фиксированного количество корневых несвязных графов: . Значит, количество несвязных графов с вершинами равно:
Таким образом, количество связных графов с вершинами: |
