577
правок
Изменения
→Помеченные графы
Иными словами, количество способов пометить вершины графа можно вычислить, зная количество и порядки групп помеченных графов, изоморфных друг другу (внутри одной группы). Например, для дерева-цепочки, состоящей из двух и более вершин, такая группа включает два элемента: тождественную перестановку и отражение относительно середины. Следовательно, ее порядок равен двум.
{| cellpadding="2"
| || [[Файл:Перечисл2.jpg|thumb|left|720px|Рис. 2. Помеченные деревья с четырьмя вершинами.]]
|}
Рассмотрим пример. На рисунке 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>.
== Теорема перечисления Пойа ==
