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

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

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

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

Следовательно,= 11.

На языке производящих рядов эту конструкцию можно описать так. Количество графов с n вершинами равно коэффициенту при tn в произведении рядов

(1+ t +++. . .) × (1+ + +. . .)×(1+++. . .)×. . .

Здесь коэффициент равен числу графов, состоящих из j связных компонент, причем каждая компонента имеет i вершин. Тоесть - это количество способов выбрать j связных графов из , причем в выборке могут быть и одинаковые графы.

Таким образом,

и i-й сомножитель в произведении есть Следовательно Перейдем к логарифмам Разложим каждый логарифм в ряд и приведем подобные. Легко видеть, что в разложениив степенной ряд слагаемое появляется лишь в том случае, когда i - делитель n. Тогда соответствующий коэффициент равен . Следовательно,

Где Здесь сумма берется по всем делителям числа n. Таким образом, Правило перехода отдостаточно простое. Действительно, продифференцируем это равенство. Имеем (2.10)

Теперь сравниваем коэффициенты при : Так как , то мы получили рекуррентную формулу для вычисления чисел

Пример. Найти количество ожерелий, составленных из n бусинок двух цветов. Ожерелья, совпадающие при повороте, считаются одинаковыми.

Пусть множествосоответствует номерам бусинок в ожерелье, а- множество возможных цветов. Весовую функцию положим равной для всех . Во множествеимеется один элемент веса 0 и один - веса 1, то естьи . Откуда .

Пусть- множество всех функций изв . Любая функциязадает некоторое ожерелье и, наоборот, каждое ожерелье задаётся некоторой функцией из . При этом вес функции равен количеству бусинок цвета 1 в соответствующем ожерелье.

На множестведействует группа поворотов , порожденная циклической перестановкой , которая определяет отношение эквивалентности на . Тогда ожерелья совпадающие при повороте будут в точности соответствовать эквивалентным функциям, и задача сводится к подсчёту числа орбит.

Цикловой индекс группыравен , где- функция Эйлера,- наибольший общий делитель чисели .

По теореме Редфилда-Пойа Число орбит веса(то есть различных ожерельев сбусинками цвета 1) равно , коэффициенту прив : . Общее число различных орбит (или ожерелий) равно

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

Графами являются блок-схемы программ для ЭВМ, сетевые графики строительства. С помощью графов решается задача о назначении на должности.

Изучая теорию перечисления графов приходится решать проблемы изоморфизмов для многих классов графов. Теорема перечисления Пойа, когда она

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