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

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

Введение

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

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

Решение многих задач перечисления графов сводится к подсчету числа классов эквивалентностей. Эффективный метод решения таких задач базируется на известной теореме Пойа.

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

Задачи исследования:

. Изучить такие основополагающие понятия теории графов и теории групп, как граф, группа подстановок и её цикловой индекс.

. Рассмотреть определение эквивалентности, порождаемое группой подстановок, и доказать лемму Бернсайда о числе классов такой эквивалентности.

. Разобрать определение перечня конфигурации и доказать теорему Пойа.

. Рассмотреть задачу о перечислении графов и метод её решения с помощью теоремы Пойа.

Объектом исследования: теория графов.

Предмет исследования: группы подстановок и методы решения комбинаторных задач с помощью теоремы Пойа. Работа состоит из двух разделов - теоретической и практической части. В ходe работы нами использовались слeдующиe мeтоды исслeдования: изучeниe научной, учeбной и мeтодичeской литeратуры, Интeрнeт-источников, анализ, обобщeниe и систематизация.

1. Теорема Пойа и перечисление графов .1 Понятия теории графов и теории групп В математической теории графов и информатике граф - это совокупность непустого множества вершин и множества пар вершин (связей между вершинами). Объекты представляются как вершины, или узлы графа, а связи - как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах [2].

Граф, или неориентированный граф- это упорядоченная пара , для которой выполнены следующие условия:

-это непустое множество вершин или узлов,

-это множество пар (в случае неориентированного графа - неупорядоченных) вершин, называемых рёбрами.

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

Вершины и рёбра графа называются также элементами графа, число вершин в графе -порядком, число рёбер- размером графа.

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

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