Теоретическая часть к курсовому проекту

Теоретическая часть к курсовому проекту. Глава1 Теория графов Понятие графа Графом GX,U называется совокупность двух объектов некоторого множества X и отображения этого множества в себя Г. При геометрическом представлении графа элементы множества Х изображаются точками плоскости и называются вершинами графа.

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

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

Две вершины х и у смежны, если они различны и существует дуга, идущая от одной из них к другой. Вершина называется изолированной, если она не соединена дугами с другими вершинами графа. Если дуга U исходит из вершины х или заходит в х, то дуга U называется инцидентной вершине х, а вершины х инцидентной дуге U. Общее число дуг, инцидентной вершине х, являются степенью вершины х Рх. Вершины, степень которых Рх 2, называются узлом, а со степенью Рх 2 - антиузлом. Полустепень захода Рх вершины х - количество дуг, заходящих в данную вершину.

Полустепень исхода Р-х - количество дуг, исходящих из данной вершины. Последовательность линий на графе Путь - последовательность дуг U1, U2, Un, в которой конец каждой предыдущей дуги совпадает с началом последующей. Путь может быть конечным и бесконечным. Путь называется простым, если в нем никакая дуга не встречается дважды, и составным, если любая из дуг встречается более одного раза. Путь, в котором ни одна из вершин не встречается более одного раза, называется элементарным путем.

Гамильтонов путь - путь проходящий через все вершины, но только по одному разу, Эллеров путь - путь содержащий все дуги графа, при этом только по одному разу. Длинна пути - число дуг последовательности U1, U2, Un. Ветвь - путь, в котором начальная и конечная вершины являются узлами. Дуга x, y называется замыкающей, если удаление ее не приводит к аннулированию пути из x в y. Контур - конечный путь, начинающийся и заканчивающийся в одной и той же вершине.

Контур единичной длинны называется петлей. Ориентированный граф - граф, у которого вершины соединяются направляющими стрелками. Графы можно рассматривать с учетом или без учета ориентации его дуг. Разновидности графов Нуль-граф - граф X,U, состоящий только из изолированных вершин. Однородный граф - если степени всех вершин графа одинаковы и Px P- x 0. Симметрический граф - граф, в котором две любые смежные вершины соединены только двумя противоположно ориентированными дугами.

Антисимметрический - граф, в котором каждая пара смежных вершин соединена только в одном направлении. Полный - граф, в котором любая пара вершин соединена одинаковым числом дуг. Мультиграф - граф, в котором хотя бы две смежные вершины соединены более чем одной дугой. Наибольшее число дуг, соединяющих смежные вершины графа называется кратностью. Подмножества графов Подграфом графа GX,U называется граф GA,UA, определяемый следующим образом 1. Вершинами A подграфа GA,UA является некоторое подмножество вершин графа GX,U 2. Отображением каждой вершины подграфа является пересечение отображения той же вершины в графе GX,U со всем подмножеством вершин A подграфа GA,UA. Частичным графом для графа GX,U называется граф GX,U, в котором содержатся все вершины и некоторое подмножество дуг исходного графа.

Частичный подграф - это частичный граф от подграфа. Фактором графа GX,U называется частичный граф GX,U, в котором каждая вершина обладает полустепенями исхода и захода, равными единице, имеются одна заходящая и одна исходящая дуги. Базисным графом называется ориентированный частичный граф, образованный из исходного удалением петель и замыкающих дуг. Связность графа В общем случае граф может быть представлен несколькими отдельными графами, не имеющими общих дуг. Тогда граф GX,U называется несвязным, а каждый из составляющих его графов G1 , G2 Gn - компонентами связности.

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

Операции над графами 1. Объединение графов G3X3,Гх3 G1X1,Г1х1 G2X2,Г2х2, где X3X1X2, а Гx3Г1x1Г2x2 Пример Рис 1.1. Рис 1.1 2. Пересечение графов G3X3,Гх3 G1X1,Г1х1 G2X2,Г2х2, где X3X1 X2, а Гx3Г1x1Г2x2 Пример рис 1.2. Рис 1.2 4. Прямое декартово произведение графов. Прямым произведением множеств Хx1 xn и Y называется множество Z, элементами которого являются всевозможные пары вида xi, yj, где xiX, yjY. Обозначают ZX x Y. G3X3,Гх3 G1X1,Г1х1 G2X2,Г2х2, где X3X1X2, а Гx3Г1х1Г2х2 Пример. рис 2.3 G1X,ГхG1X1,Гх1 G2Y,Гy G2X2,Гх2 Xx1 x2 x3 Yy1 y2 Гх10 Гу1y1 y1 Гх2x1 x3 Гу2y1 Гх30 ZX x Yx1 y1, x1y2, x2y1, x2y2, x3y1, x3y2 Zz1 z2 z3 z4 z5 z6 Рис 2.3 7. Расширение графа.

Расширение графа - это превращение, линии, соединяющей любые две вершины графа в элементарный путь введением новых промежуточных вершин на этой линии. 8. Сжатие графа. Сжатие графа - это превращение элементарного пути, соединяющего две любые вершины графа, в линию. 9. Стягивание графа.

Если граф содержит вершины Х1 и Y1 , то операцией стягивания называется исключение всех дуг между вершинами Х1 и Y1 и превращение всех вершин в одну общую вершину Х. Некоторые числа теории графов Пусть существует мультиграф с b вершинами, p ребрами, и R компонентами связности, тогда цикломатическое число мультиграфа определяется равенством V p-bR Матрицы для графов Матрицей смежности графа GX,Гх, содержащего n вершин называется квадратная бинарная матрица АG n x n, c нулями на диагонали.

Число единиц в строке равно степени соответствующей вершины. Матрицей инциденций ориентированного графа GX,U называется прямоугольная матрица порядка m x n n - мощность множества Х, m - мощность множества U. Каждый элемент которой определяется следующим образом 1, если хi - начало дуги Uj aij -1, если хi - конец дуги Uj 0, если хi - не инцидентна дуге Uj Пример. Построим матрицы смежности М1 и инциденций М2 для графа GX,U рис 2.1. Рис 2.1 Дополнительная матрица графа GX,U представляет собой квадратную матрицу А1 , которая получается из матрицы смежности этого графа путем замены всех нулей единицами и наоборот. Деревья и прадеревья Деревом называется неориентированный связный граф с числом вершин не менее двух, не содержащий петель и циклов.

Вершины, инцидентные только одной дуге дерева, называются висячими. Прадрево - ориентированное дерево. Корень прадерева - вершина у которой Рх0. Глава 2 Максимальные полные подграфы клики Максимальный полный подграф клика графа G есть порожденный подграф, построенный на подмножестве S вершин графа и являющийся полным и максимальным в том смысле, что любой другой подграф графа G, построенный на множестве вершин H, содержащих S, не является полным.

Следовательно, в клике все вершины попарно смежны. Возможно также определить кликовое число графа известное также как густота или плотность - это максимальное число вершин в кликах данного графа. Часть 2