Разработка и реализация на языке высокого уровня алгоритма выделения сильносвязных компонент ориентированного графа
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
?пом void *);
;">функции, возвращающие объединения и структуры;
имена полей данных структур в разных пространствах имён для каждой структуры;
присваивания структур;
(const);">спецификатор констант (const);
,,;">стандартная библиотека , реализующая большую часть функций, введённых различными производителями;
перечислимый тип (enum);
дробное число одинарной точности (float).
граф программа алгоритм
1. Основные понятия и определения теории графов
Теория графов представляет собой раздел математики, имеющий широкое практическое применение. В её терминах формулируется большое число задач, связанных с дискретными объектами. Такие задачи возникают при проектировании интегральных схем и схем управления, электрических цепей, блок-схем программ, в экономике, статистике, химии, биологии и в других областях. Теория графов становится одной из существенных частей математического аппарата кибернетики, языком дискретной математики.
В отличие от других научных дисциплин, теория графов имеет вполне определенную дату рождения. Первая работа по теории графов, написанная швейцарским математиком Леонардом Эйлером (1707-1783), была опубликована в 1736 году в Трудах Академии наук в Санкт-Петербурге.
Граф - Пара объектов
= ( X , Г ) ,
где Х - конечное множество ,а Г -конечное подмножество прямого произведения Х*Х . При этом Х называется множеством вершин , а Г - множеством дуг графа G .
Любое конечное множество точек (вершин), некоторые из которых попарно соединены стрелками , (в теории графов эти стрелки называются дугами), можно рассматривать как граф.
Если в множестве Г все пары упорядочены, то такой граф называют ориентированным.
Дуга- ребро ориентированного графа.
Вершина Х называется инцидентной ребру G , если ребро соединяет эту вершину с какой-либо другой вершиной.
Подграфом G(V1, E1) графа G(V, E) называется граф с множеством вершин V1 ?V и множеством ребер (дуг) E?? E, - такими, что каждое ребро (дуга) из E1 инцидентно (инцидентна) только вершинам из V1 . Иначе говоря, подграф содержит некоторые вершины исходного графа и некоторые рёбра (только те, оба конца которых входят в подграф).
Мультиграф - это пара (V,E), где V - непустое множество, а E - семейство подмножеств множества V{2}.
Употребление термина семейство вместо подмножество означает, что элементы множества V{2} могут в E повторяться, то есть допускаются кратные рёбра.
Пример мультиграфа показан на рис. 3.3.
Дальнейшее обобщение состоит в том, что кроме кратных рёбер допускаются еще петли, то есть рёбра, соединяющие вершину саму с собой.
Такой граф называется псевдографом. Его пример приведен на рис. 3.4.
Псевдограф - это пара (V,E), где V - непустое множество (вершин), а E - некоторое семейство неупорядоченных пар вершин (рёбер), не обязательно различных.
Различают также ориентированные и смешанные графы.
Пусть V(2) - множество упорядоченных пар элементов множества V. Тогда ориентированный граф (или орграф) - это пара (V,А), где V - множество вершин, АV(2) - множество ориентированных рёбер, которые называются дугами.
Если пара (v1,v2) - дуга, то вершины v1 и v2 называются её началом и концом соответственно.
На рисунке дуги отмечаются стрелками, указывающими направление от начала к концу.
Орграф G=(V,E), V={v1,v2,v3,v4}, E={(v1,v2), (v1,v4), (v2,v3), (v2,v4), (v3,v4)} представлен графически на рис.3.5.
Ориентированный мультиграф и ориентированный псевдограф определяются аналогично.
Смешанные графы имеют как дуги, так и неориентированные рёбра.
Пример смешанного графа представлен на рис. 3.6.
Ради сокращения речи термин граф употребляется вместо терминов мультиграф, орграф и др., но подобные случаи либо специально оговариваются, либо ясны из контекста.
Часто каждой дуге графа ставят в соответствие одно или несколько чисел. Такой граф называется взвешенным (или сетью). Пример взвешенного графа представлен на рис. 3.7.
Рассмотрим некоторые понятия теории графов.
Пусть v1,v2,…,vn,vn+1 - произвольная последовательность вершин орграфа.
Цепью называется любая последовательность дуг e1,e2,...,en, такая, что концевыми вершинами дуги ei являются вершины vi и vi+1, то есть ei=(vi,vi+1) или ei=(vi+1,vi) для i=1,2,…,n.
Цепь, для которой ei=(vi,vi+1) при всех i=1,2,…,n, называется путём.
Циклом называется цепь, у которой начальная и конечная вершины совпадают.
Контуром называется путь, у которого начальная и конечная вершины совпадают.
Цепь, путь, цикл или контур называются простыми, если они не содержат внутри себя циклов.
У графа, изображенного на рис. 3.8.
дуги (v2,v1), (v2,v2), (v3,v2), (v3,v4) образуют цепь, соединяющую вершину v1 с вершиной v4;
дуги (v2,v2), (v2,v4), (v4,v3) образуют путь, соединяющий вершины v2 и v3;
дуги (v3,v2), (v2,v4), (v3,v4) образуют цикл с начальной и конечной вершиной v3;
дуги (v3,v2), (v2,v4), (v4,v3) образуют контур с начальн