Читать курсовая по математике: "Решения комбинаторных задач теории графов с помощью теоремы Пойа" Страница 1

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

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

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

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

Задачи: 1) изучить такие основополагающие понятия теории графов и теории групп, как граф, группа подстановок и ее цикловой индекс; 2) рассмотреть определение эквивалентности, порождаемой группой подстановок, и доказать лемму Бернсайда о числе классов такой эквивалентности; 3) разобрать определение перечня конфигурации и доказать теорему Пойа; 4) разобрать примеры и решить задачи. Глава 1. Основные понятия теории графов и теории групп .1 Основные понятия графа

теория граф теорема пойа

Граф - это совокупность непустого множества вершин и множества пар вершин (связей между вершинами). С формальной точки зрения граф представляет собой упорядоченную пару G = (V, Е) множеств, первое из которых состоит из вершин, или узлов, графа, а второе - из его ребер. Ребро связывает между собой две вершины. Графы часто описывают множество близких ситуаций. Самым привычным примером служит карта автодорог, на которой изображены перекрестки и связывающие их дороги. Перекрестки являются вершинами графа, а дороги - его ребрами. Иногда наши графы ориентированы (подобно улицам с односторонним движением) или взвешены - каждой дороге приписана стоимость путешествия по ней (если, например, дороги платные). Когда мы изучим язык графов подробнее, аналогия с картой автодорог станет еще более глубокой.

Граф может быть ориентированным или нет. Ребра неориентированного графа, чаще всего называемого просто графом, можно проходить в обоих направлениях. В этом случае ребро - это неупорядоченная пара вершин, его концов. В ориентированном графе, или орграфе, ребра представляют собой упорядоченные пары вершин: первая вершина - это начало ребра, а вторая - его конец. [1]

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

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