Читать курсовая по математике: "Практическое применение теоремы Пойа и перечисления графов" Страница 7

(Назад) (Cкачать работу)

,

а область значений это множество из двух элементов {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, 2) и (3, 4) неподвижны; (1, 3) → (2, 4) → (1, 3); (1, 4) →2, 3) → (1, 4). Соответствующий одночлен - . Так как в S4 три 2,2-цикла, то они дают в цикловый индекс вклад . Пример. Пусть n = 4. Мы знаем, что . Имеется 5 разбиений числа 4: 4, 3 + 1, 2 + 2, 2 + 1 + 1, 1 + 1 + 1 + 1.

· Первое разбиение отвечает случаю связного графа - таких графов 6.

· Второе разбиение отвечает случаю двух компонент связности - с тремя вершинами и с одной вершиной. Таких графов 2.

Похожие работы