омогою теореми Пойа
Ми будемо перераховувати графи з n вершинами. Ми вважаємо, що задана якась нумерація множини вершин V, тобто . Безліч X, з яким ми будемо працювати, це безліч функцій, область визначення яких - це безліч пар вершин (тобто пар чисел)
,
а область значень це безліч з двох елементів {0,1}. Така функція повністю описує граф: якщо i-а і j-я вершини не з'єднані ребром а якщо - то з'єднані. Інакше це можна описати так: розглянемо повний граф, тобто граф з n вершинами, де кожна пара вершин з'єднана ребром. Розфарбуємо безліч ребер графа в два кольори - чорний і білий. Тепер видалимо білі ребра.
Група перестановок діє на безлічі V (перенумерація вершин). Але вона діє і на безлічі такий спосіб. Перестановку s ми розглядаємо як відображення безлічі {1, 2,. . . , N} в себе. Так перестановка s=2, 4, 1, 3 - це відображення s: {1, 2, 3, 4}? {1, 2, 3, 4}: s (1)=2, s (2)=4, s (3)=1, s (4)=3. Перестановка s діє на безлічі так: s переводить пару (i , j) в пару (s (i), s (j)), якщо s (i) < s (j), і в пару (s (j), s (i)) в іншому випадку. У термінах теореми Пойя безліч - це безліч M, а безліч X - це безліч розмальовок елементів у два кольори - чорний і білий. Вибір розмальовки задає граф, а перенумерація вершин дає іншу розмальовку, але ізоморфний граф.
Приклад. Нехай n=4. Перестановка s=2, 4, 1, 3 діє на так:
s ((1,2))=(2,4), s ((1,3))=(1,2), s ((1,4))=(2,3), s ( (2,3))=(1,4) s ((2,4))=(3,4)), s ((3,4))=(1, 3).
Якщо ((1, 2))=0, f ((1, 3))=1, f ((1, 4))=0, f ((2, 3))= 0, f ((2, 4))=1, f ((3, 4))=1, то ((1, 2))=1, g ((1, 3))=1, g ((1 , 4))=0, g ((2, 3))=0, g ((2, 4))=0, g ((3, 4))=1,
де g=s (f).
Функції f і g задають такі графи
Рисунок 2.1 - граф f. Рисунок 2.2 - граф g.
Зрозуміло ці графи ізоморфні.
Число графів - це число орбіт дії групи Sn на безлічі раскраскок безлічі в два кольори. Щоб знайти число орбіт нам потрібно обчислити циклової індекс дії на.
Приклад. n=3. Розглянемо дію групи на. Маємо
· s=e. Дія s: () ()) ().
· s=(1, 2) (3). Дія s: () (,).
· s=(1, 3) (2). Дія s: (,)).
· s=(1) (2, 3). Дія s: (,) ().
· s=(1, 2, 3). Дія s: ().
· s=(1, 3, 2). Дія s: ().
Таким чином,. Нехай змінна x відповідає білому кольору, а y - чорному.
(2.1)
Це означає, що у нас є чотири графа з трьома вершинами: один граф без ребер, один з одним ребром, один з двома ребрами і один з трьома ребрами.
Приклад. n=4. Розглянемо дію групи на. одночлен -.
· 2-цикл, наприклад (1, 2) (3) (4), діє так: (1, 2) і (3, 4) нерухомі; (1, 3)? (2, 3)? (1, 3); (1, 4)? (2, 4)? (1, 4). Відповідний одночлен -. Так як в шість 2-циклів, то вони дають в циклових індекс внесок
· 3-цикл, наприклад (1, 2, 3) (4), діє так: (1, 2)? (2, 3)? (1, 3)? (1, 2); (1, 4)? (2, 4)? (3, 4)? (1, 4). Відповідний одночлен -. Так як у вісім 2-циклів, то вони дають в циклових індекс внесок 8.
· 4-цикл, наприклад (1, 2, 3, 4), діє так: (1, 2)? (2, 3)? (3, 4)? (1, 4)? (1, 2); (1, 3)? (2, 4)? (1, 3). Відповідний одночлен -. Так як в шість 4-циклів, то вони дають в циклових індекс вклад.
· 2,2-цикл, наприклад (1, 2) (3, 4), діє так: (1...
