Производящие функции в теории графов

Введение

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

Согласно Р. Уилсону, граф – это представление некоторого множество точек и способа их соединения (рисунок 1).

Рисунок 1. Пример графа
Точки P, Q, R, S, T – вершины графа. Линии – ребра графа. Степенью вершины называется число ребер, концом которых является эта вершина.
Два графа считаются изоморфными, если существует взаимно однозначное соответствие между их вершинами, обладающее тем свойством, что две вершины соединены ребром в одном графе тогда и только тогда, когда соответствующие им вершины соединены ребром в другом [13, стр. 29]. Граф на рисунке 2 считается изоморфным графу на рисунке 1.

Рисунок 2. Пример графа
Ребра, соединяющие Q с S и S с T на графе рисунка 3, называются кратными, ребро, идущее из P в P, называют петлей.

Рисунок 3. Пример графа
Граф, не содержащий кратных ребер и петель, называется простым.
Если на ребрах графа указано направление движения, то он называется ориентированным или орграфом (рисунок 4).

Рисунок 4. Пример графа
Согласно М. Свами, маршрут в графе G=(V,E) представляет собой конечную чередующуюся последовательность вершин и ребер vo, e1, v1, e2,…, vk-1, ek, vk, начинающуюся и кончающуюся на вершинах, причем vi-1 и vi являются концевыми вершинами ребра ei, 1ik. С другой стороны, маршрут можно рассматривать как конечную последовательность таких вершин v0, v1, v2, …, vk, что (vi-1, vi), 1ik, ребро графа G. Такой маршрут обычно называется v0-vk – маршрутом, а v0 и vk – концевыми или терминальными вершинами маршрута. Все другие вершины маршрута называются внутренними. Заметим, что ребра и вершины в маршруте могут появляться более одного раза. Маршрут называется открытым, если его концевые вершины различны, в противном случае он называется замкнутым. Маршрут называется цепью, если все его ребра различны. Цепь называется открытой, если ее концевые вершины различны, в противном случае она называется замкнутой [11, стр. 203].
Открытая цепь называется путем, если все ее вершины различны. Замкнутая цепь называется циклом, если различны все ее вершины, за исключением концевых. Укажем следующие свойства путей и циклов:
1) Степень каждой неконцевой вершины пути равна 2, концевые вершины имеют степень, равную единице.
2) Каждая вершина цикла имеет степень 2 или другую четную степень. Обращение этого утверждения, а именно то, что ребра подграфа, в котором каждая вершина имеет четную степень, образуют цикл, - неверно.
3) Число вершин в пути на единицу больше числа ребер, тогда как в цикле число ребер равно числу вершин.
Связным графом называется такой граф, в котором любые две вершины соединены цепью.
Деревом называется ациклический (не содержащий циклов), связный граф. Деревом графа G называется связный ациклический подграф графа G. Остов графа G – это дерево графа G, содержащее все вершины G. Связный подграф дерева T называется поддеревом Т. В качестве примера рассмотрим граф G, изображенный на рисунке 5 а. Графы G1 и G2 (рисунок 5 б), являются деревьями графа G, графы G3 и G4 (рисунок 5 в) – остовами г