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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 43: Строка 43:
  
 
Пусть <tex>A</tex> {{---}} группа подстановок, действующая на множестве <tex>X</tex>. Для всякого элемента <tex>x \in X</tex> '''орбитой''' <tex>\Theta(x)</tex> элемента <tex>x</tex> называется подмножество множества <tex>X</tex>, состоящее из всех элементов <tex>y \in X</tex> таких, что <tex>\alpha \cdot x = y</tex> для некоторой подстановки <tex>\alpha</tex> из <tex>A</tex>. '''Стабилизатором''' <tex>A(x)</tex> элемента <tex>x</tex> называется подгруппа группы <tex>A</tex>, состоящая из всех подстановок из <tex>A</tex>, оставляющих элемент <tex>x</tex> неподвижным. Теорема является следствием соотношения <tex>|A| = |\Theta(x)|\cdot|A(x)|</tex> и его интерпретации в настоящем контексте.}}
 
Пусть <tex>A</tex> {{---}} группа подстановок, действующая на множестве <tex>X</tex>. Для всякого элемента <tex>x \in X</tex> '''орбитой''' <tex>\Theta(x)</tex> элемента <tex>x</tex> называется подмножество множества <tex>X</tex>, состоящее из всех элементов <tex>y \in X</tex> таких, что <tex>\alpha \cdot x = y</tex> для некоторой подстановки <tex>\alpha</tex> из <tex>A</tex>. '''Стабилизатором''' <tex>A(x)</tex> элемента <tex>x</tex> называется подгруппа группы <tex>A</tex>, состоящая из всех подстановок из <tex>A</tex>, оставляющих элемент <tex>x</tex> неподвижным. Теорема является следствием соотношения <tex>|A| = |\Theta(x)|\cdot|A(x)|</tex> и его интерпретации в настоящем контексте.}}
 +
 +
Иными словами, количество способов пометить вершины графа можно вычислить, зная количество и порядки групп помеченных графов, изоморфных друг другу (внутри одной группы). Например, для дерева-цепочки, состоящей из двух и более вершин, такая группа включает два элемента: тождественную перестановку и отражение относительно середины. Следовательно, ее порядок равен двум.
 +
 +
Рассмотрим пример. На рисунке 2 изображены все помеченные деревья с четырьмя вершинами. Всего их <tex>16</tex>. Среди них <tex>12</tex> изоморфны цепи <tex>P_{4}</tex> и <tex>4</tex> {{---}} графу <tex>K_{1, 3}</tex>. Порядок группы <tex>\Gamma(P_{4})</tex>, как было сказано выше, равен <tex>2</tex>. Порядок группы <tex>K_{1, 3} = 6</tex>. Так как <tex>p = 4</tex>, то имеем <tex dpi = "160">\frac{4!}{|\Gamma(P_{4})|} = 12</tex> и <tex dpi = "160">\frac{4!}{|\Gamma(K_{1, 3})|} = 4</tex>.
 +
 +
{| cellpadding="2"
 +
| || [[Файл:Перечисл2.jpg|thumb|left|720px|Рис. 2. Помеченные деревья с четырьмя вершинами.]]
 +
|}
 +
 +
== Теорема перечисления Пойа ==

Версия 22:30, 27 декабря 2015

Перечисления графов

Помеченные графы

Определение:
Помеченный граф с [math]n[/math] вершинами — граф, у которого каждая вершина помечена целым числом от [math]1[/math] до [math]n[/math].


Более формально определить это понятие можно так: назовем распределением [math]f[/math] меток в графе [math]G[/math] с [math]n[/math] вершинами биекцию между множеством вершин графа и множеством [math]\{1 \cdots n\}[/math]. Тогда помеченным графом называется пара [math](G, f)[/math].


Определение:
Два помеченных графа [math](G_{1}, f_{1})[/math] и [math](G_{2}, f_{2})[/math] изоморфны, если существует изоморфизм между [math]G_{1}[/math] и [math]G_{2}[/math], сохраняющий распределение меток.


Все помеченные графы с тремя вершинами показаны на рисунке 1. [math]4[/math] различных графа с [math]3[/math] вершинами приводят к [math]8[/math] различным помеченным графам.

Рис. 1. Помеченные графы с тремя вершинами.

Для нахождения числа помеченных графов с [math]p[/math] вершинами нужно заметить, что каждое из [math] p\choose 2[/math] возможных ребер либо принадлежит графу, либо нет.

Теорема (1):
Число помеченных графов с [math]p[/math] вершинами равно [math] 2^{p\choose 2}[/math].

Следовательно, число помеченных графов с [math]q[/math] ребрами равно [math] {p\choose 2}\choose q[/math].

Теорема (Кэли):
Число помеченных деревьев с [math]p[/math] вершинами равно [math] p^{p - 2}[/math].
Теорема (2):
Данный граф [math]G[/math] можно пометить [math]\frac{p!}{|\Gamma(G)|}[/math] способами.
Доказательство:
[math]\triangleright[/math]

Приведем набросок доказательства.

Пусть [math]A[/math] — группа подстановок, действующая на множестве [math]X[/math]. Для всякого элемента [math]x \in X[/math] орбитой [math]\Theta(x)[/math] элемента [math]x[/math] называется подмножество множества [math]X[/math], состоящее из всех элементов [math]y \in X[/math] таких, что [math]\alpha \cdot x = y[/math] для некоторой подстановки [math]\alpha[/math] из [math]A[/math]. Стабилизатором [math]A(x)[/math] элемента [math]x[/math] называется подгруппа группы [math]A[/math], состоящая из всех подстановок из [math]A[/math], оставляющих элемент [math]x[/math] неподвижным. Теорема является следствием соотношения [math]|A| = |\Theta(x)|\cdot|A(x)|[/math] и его интерпретации в настоящем контексте.
[math]\triangleleft[/math]

Иными словами, количество способов пометить вершины графа можно вычислить, зная количество и порядки групп помеченных графов, изоморфных друг другу (внутри одной группы). Например, для дерева-цепочки, состоящей из двух и более вершин, такая группа включает два элемента: тождественную перестановку и отражение относительно середины. Следовательно, ее порядок равен двум.

Рассмотрим пример. На рисунке 2 изображены все помеченные деревья с четырьмя вершинами. Всего их [math]16[/math]. Среди них [math]12[/math] изоморфны цепи [math]P_{4}[/math] и [math]4[/math] — графу [math]K_{1, 3}[/math]. Порядок группы [math]\Gamma(P_{4})[/math], как было сказано выше, равен [math]2[/math]. Порядок группы [math]K_{1, 3} = 6[/math]. Так как [math]p = 4[/math], то имеем [math]\frac{4!}{|\Gamma(P_{4})|} = 12[/math] и [math]\frac{4!}{|\Gamma(K_{1, 3})|} = 4[/math].

Рис. 2. Помеченные деревья с четырьмя вершинами.

Теорема перечисления Пойа