Применение теории графов для структурного анализа

Введение
Структурный анализ - это область дискретной математики, целью которой является исследование статических характеристик системы путём выделения в ней подсистем и элементов различного уровня и определения отношений, и связей между ними. Объектами исследования структурного анализа являются различные варианты формируемых в процессе декомпозиции системы структур, позволяющие всесторонне оценить свойства системы.
Прикладная теория графов - это область дискретной математики, целью которой является исследование прикладных моделей графов. Граф представляет собой совокупность вершин и ребер, соединяющих вершины. В виде граф могут представлены информационные и материальные ценности, карта города и страны, компьютерные программы, модели мозга человека и животных, химические соединения и т.д. Применение результатов изучения прикладной теории графов имеет широкое применение в науке и промышленности.
Теория графов, как правило, не используется отдельно, а является надстройкой или разделом других теорий, которые характерны тем, что в них так или иначе отражается содержательное представление о потоках вещества, энергии, информации, существующих в рассматриваемом технологическом объекте. В ряде надстроек графовая структура интерпретируется как описание сложного объекта или системы, делая упор на внутренние связи и зависимости между элементами.
Структурно-топологический анализ системы необходим для получения информации о характере функционирования сложной системы в задачах оптимизации, планирования или синтеза системы. Зная топологию системы и характер информационных потоков, исследователь получает информацию, необходимую для принятия решения по оптимизации процесса функционирования, получения, передачи, распределения информации, синтезу сложных иерархических, многоуровневых систем. 
1. Что такое теория графов
Граф представляет собой непустое множество точек и множество отрезков, оба конца которых принадлежат заданному множеству точек. Обозначают граф буквой Г.
Точки иначе называют вершинами, отрезки – рёбрами графа.
Виды графов:
• Ориентированный (ребрам присвоено направление)
• Неориентированный (у ребер нет направлений)
• Смешанный (встречаются как ориентированные, так и неориентированные рёбра)
• Связный (между любой парой вершин этого графа существует как минимум один путь.)
• Дерево (между любой парой вершин имеется только по одному пути)
• Полный (любые две вершины соединены ребром)
• Двудольный (множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части.)
• K – дольный (его вершины можно разбить на непересекающихся)
• Планарный (граф можно изобразить диаграммой на плоскости без пересечений рёбер)
• Взвешенный (каждому ребру графа поставлено в соответствие некоторое число, называемое весом ребра)
В общем смысле граф представляется как множество вершин, соединённых рёбрами. Графы бывают полными и неполными. Полный граф - это простой граф, каждая пара различных вершин которого смежна. Неполный граф – это граф, в котором хотя бы 2 вершины не смежны.
Граф, являющийся неполным, можно преобразовать в полный с теми же вершинами, добавив недостающие рёбра. Проведя недостающие рёбра, получим полный граф. Вершины графа Г и рёбра, которые добавлены, тоже образуют граф. Такой граф называют дополнением графа Г и обозначают его Г.
Г: Г:

Дополнением графа Г называется граф Г с теми же вершинами, что и граф Г, и с теми и только с теми рёбрами, которые необходимо добавить графу Г, чтобы получился полный граф. Является ли граф полным или нет, это его характеристика в целом.
Рассмотрим теперь характеристики его вершин. Вершины, которые не принадлежат ни одному ребру, называются изолированными. Вершины в графе могут отличаться друг от друга степенью. Степенью вершины называется число рёбер графа, которым принадлежит эта вершина. Вершина называется нечётной, если её степень – число нечётное. Вершина называется четной, если её степень – четное число.
Имея даже общее представление о графе, иногда можно судить о степенях его вершин. Так, степень каждой вершины полного графа на единицу меньше числа его вершин. При этом некоторые закономерности, связанные со степенями вершин, присущи не только полным графам.
С вершинами графов связаны 4 теоремы, докажем их с помощью задач:
№1. Участники пионерского слёта, познакомившись, обменялись конвертами с адресами. Докажите, что:
1) всего было передано четное число конвертов;
2)число участников, обменявшихся конвертами нечетное число раз, четное.
Решение. Обозначим участников слёта А1, А2, А3…., Аn – вершины графа, а ребра соединяют на рисунке пары вершин, изображающих ребят, которые обменялись конвертами:
1) Степень каждой вершины Аj показывает количество конвертов, переданных участником Аj своим знакомым, значит общее число переданных конвертов N равно сумме степеней всех вершин графа. N = степ. А1 + степ. А2 + … + степ. Аn-1 + степ. Аn, N = 2р (р – число ребер графа), то есть N – четное число. Из этого следует, что было передано четное число конвертов;
2) Мы доказали, что N – четное, а N = степ. А1 + степ. А2 + …. + степ. Аn-1 + степ. Аn , т.е N – количество участников. Мы знаем, что сумма нечетных слагаемых должна быть четной, а это возможно только в том случае, если число нечетных слагаемых четно. Значит, что число участников, которые обменялись конвертами нечетное число раз, четное.
В ходе решения задачи доказаны две теоремы.
1. В графе сумма степеней всех его вершин – число чётное, равное удвоенному числу рёбер графа. ∑ степ. Аj = степ. А1 + степ. А2 + … + степ. Аn = 2р, где р – число ребер графа Г, n – число его вершин.
2. Число нечётных вершин любого графа чётно.
№2. Девять шахматистов проводят турнир в один круг. Покажите, что в любой момент найдутся двое закончившие одинаковое число партий.
Решение. Переведем условие задачи на язык графов. Каждому из шахматистов поставим соответствующую ему вершину графа, соединим рёбрами попарно вершины, соответствующие шахматистам, которые уже сыграли между собой партию. Мы получили граф с девятью вершинами. Степень каждой вершины соответствует числу партий, сыгранных соответствующим игроком. Докажем, что в любом графе с девятью вершинами всегда есть хотя бы две вершины с одинаковой степенью.
Каждая вершина графа с девятью вершинами может иметь степень, равную 0, 1, 2, …, 7, 8. Предположим, что существует граф Г, все вершины которого имеют разную степень, т. е. каждое из чисел последовательности 0, 1, 2, …, 7, 8 является степенью одной и только одной из его вершин. Но этого не может быть. Действительно, если в графе есть вершина А со степенью 0, то в нем не найдется вершина В со степенью 8, так как эта вершина В должна быть соединена ребрами со всеми остальными вершинами графа, в том числе и с А. Иначе говоря, в графе с девятью вершинами не могут быть