Другими словами, функции (19) образуют базис в пространстве решений рекуррентного соотношения (14). Ранее без доказательства было сформулировано, что решениями этого соотношения являются линейные комбинации функций

Можно показать, что функции (19) линейно выражаются через функции (20). Например, при

.

Таким образом, метод производящих функций позволил строго обосновать сформулированную ранее процедуру решения линейного рекуррентного соотношения

11. 
    Подстановки, группы подстановок и циклы. Цикловой индекс группы подстановок. Лемма Бернсайда. Теорема Пойа. Примеры применения теории Пойа
    

Пусть – произвольное множество. Подстановкой называется биекция (биективное отображение) множества на себя: .

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

.

Обозначим через тождественное отображение: .

Отображение, обратное , обозначим : .

Введенная на операция композиции удовлетворяет трем законам:

1. .

2. .

3. .

Множество, на котором задана операция, удовлетворяющая законам 1 – 3, называется группой. Множество подстановок называется симметрической группой на множестве

Если , то группа называется симметрической группой степени и обозначается , а каждая ее подгруппа – группой подстановок степени .

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

.

Цикловым индексом группы подстановок называется многочлен . (1)

Элементы и из называются -эквивалентными (обозначение ), если существует подстановка такая, что (или ). Классы -эквивалентности называются транзитивными множествами, или орбитами.

Лемма Бернсайда. Число орбит в множестве , определяемых группой , определяется равенством . (2)

Пусть и – конечные множества, а и – группы подстановок соответственно в и . Степенная группа состоит из всевозможных пар , где , , и действует на множестве всех функций . При этом по определению . Пусть на множестве задана весовая функция и – число элементов веса в . Производящая функция называется

---

перечисляющим рядом для фигур. Все функции определяются равенством . Функции называются эквивалентными (обозначение ), если . Если , то они имеют одинаковый вес. Поэтому можно определить вес класса эквивалентности как вес любого элемента . Пусть – число классов эквивалентности веса в . Производящая функция называется перечисляющим рядом для функций (или перечисляющим рядом для конфигураций).

Теорема Пойа. , (3)где , – цикловой индекс группы , а подставляется в на место переменной .

Следствие.Пусть – группа подстановок множества , – число классов неэквивалентных -элементных подмножеств , – производящая функция последовательности . Тогда .

11. 
    Теоретико-множественное определение графа. Геометрическая интерпретация и реализация графов. Степени вершин. Теорема о сумме степеней вершин графа.
    

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

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

Если в графе пара вершин такова, что , то вершины называются смежными; в этой ситуации каждая из них называется инцидентной ребру , а ребро называется инцидентным каждой из вершин . Если вершина и ребро инцидентны, то пишут .

Количество ребер, инцидентных данной вершине , называется ее степенью

---

или локальной степенью графа в вершинеиобозначают через . Для неориентированного графа . Вершина с нулевой степенью называется изолированной. Вершина, степень которой равна единице, называется висячей.

Если ребро (дуга) инцидентно только одной вершине, то его называют петлей. Ребра называют кратными, если они инцидентны одним и тем же вершинам.

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

Теорема 2. Сумма степеней вершин -графа равна удвоенному числу его ребер: .

11. 
    Матрицы смежности и инциденций. Подграфы. Изоморфизм графов. Инварианты.
    

Матрицей смежности -графа называется квадратная матрица размера , которая определяется следующим образом:

Матрица смежности полностью определяет структуру графа. Например, , ,

Множество столбцов, имеющих 1 в -ой строке, есть множество , а множество строк, которые имеют 1 в -ом столбце, совпадает с множеством .

Матрицей инциденций -графа называется прямоугольная матрица размерности , определяемая следующим образом:

Пусть , – два графа, для которых , ; тогда говорят, что является подграфом графа . В свою очередь, граф по отношению к своему подграфу является надграфом. Если и , то такой подграф называется остовным. Любой остовный подграф графа может быть получен путем удаления подмножества ребер надграфа.

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

Инвариантом называют некоторую числовую характеристику графа , которая принимает одно и то же значение для любого графа, изоморфного . Только при совпадении значений инвариантов переходят к перебору допустимых вариантов нумерации вершин. Тривиальными инвариантами графа являются и . К числу инвариантов относится и степенная последовательность графа, т. к. при изоморфизме степень вершины не изменяется. Есть множество других инвариантов, однако не известна (возможно не существует) система инвариантов, позволяющая решать задачу изоморфизма для всех видов графов.

---

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

11. 
    Маршруты, цепи и циклы. Связность графа и компоненты связности.
    

Ориентированным маршрутом (или путем) орграфа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей

Ориентированной цепью (или орцепью) называется путь, в котором каждая дуга используется не больше одного раза. Так, например, пути (2) и (3) являются орцепями, а путь (1) не является таким, поскольку дуга в нем используется дважды.

Простой называется орцепь, в которой каждая вершина используется не более одного раза..

Маршрут есть неориентированный двойник пути, т. е. последовательность ребер , в которой каждое ребро , за исключением первого и последнего, связано концевыми вершинами с ребрами и . Черта над символом дуги означает, что ее рассматривают как ребро.

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

Орграф называют сильно связным или сильным, если любые две вершины в нем взаимно достижимы

Орграф называется односторонне связным или односторонним, если в любой паре его вершин хотя бы одна достижима из другой.

Графы являются связными и в сумме дают граф . Эти графы называются компонентами связности графа . Число – еще одна числовая характеристика графа. Для связного графа , если граф несвязный, то .

11. 
    Метрические характеристики графа. Матрицы достижимостей и контрадостижимостей.
    

Матрица достижимостей определяется следующим образом:

Множество вершин графа , достижимых из заданной вершины , состоит из таких элементов , для которых -й элемент в матрице равен 1. Это множество можно представить в виде .

Матрица контрадостижимостей (обратных достижимостей) определяется следующим образом:

Аналогично построению достижимого множества можно сформировать множество , используя следующее выражение: .

---

Из определений следует, что -й столбец матрицы совпадает с -й строкой матрицы , т. е. , где – матрица, транспонированная к матрице

11. 
    Постановка задачи о кратчайшем пути в графе. Задача о кратчайшем пути в ненагруженном графе и волновой алгоритм ее решения. Задача о кратчайшем пути в нагруженном графе и ее решение на основе алгоритма Дейкстры.
    

1. 
   Постановка задачи о кратчайшем пути
   

В практических приложениях имеет большое значение задача о нахождении кратчайшего пути между двумя вершинами связного неориентированного графа.

Формулировка задачи может иметь несколько вариантов.

Вариант 1. Дана сеть автомобильных дорог, например, Тульской области. Найти кратчайшие пути от Тулы до каждого города области (если двигаться можно только по дорогам).

Вариант 2. Имеется некоторое количество авиарейсов между городами мира. Для каждого известна стоимость. Найти маршрут минимальной стоимости (возможно с пересадками), например, из Торонто в Новосибирск.

Вариант 3. Есть план города с нанесенными на него местами расположения пожарных частей. Определить ближайшую к каждому дому пожарную станцию.

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

2. 
   Задача о кратчайшем пути в ненагруженном графе и волновой алгоритм ее
   

решения

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

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

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

1. 
   начальной вершине присваивается индекс ;
   
2. 
   всем вершинам, смежным с вершиной , присваиваем индекс 1;
   
3. 
   всем вершинам, смежными с вершинами, имеющими индекс 1, присваиваем индекс 2, и так далее, пока не будет помечена вершина . Сам кратчайший путь найдем, если будем двигаться из конечной вершины в направлении убывания индексов.
   

---

Смотрите также файлы

• Правила проектирования и оформления проектов стандартизованы в Единой системе конструкторской документации (ескд), которая устанавливает пять стадий разработки конструкторской документации.pptx

• Министерство образования и науки государственное образовательное учреждение высшего профессионального образования.docx

• Закон противоречия и споры вокруг него.docx

• Основная образовательная программа начального (основного) общего образования. 1)срок получения ооо 5 лет (не установлено сокращение).docx

• Темам 4 Тема Практическое занятие Требования к соблюдению основных принципов работы психолога Ситуация 4.docx