Разработка и реализация на языке высокого уровня алгоритма выделения сильносвязных компонент ориентированного графа
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
ой и конечной вершиной v3;
цепь (v2,v1), (v3,v2), (v3,v4), (v4,v3) с начальной вершиной v1 и конечной v3 не является простой, так как содержит внутри себя цикл (v3,v4), (v4,v3).
Граф называется связным, если в нем для каждой пары вершин найдётся соединяющая их цепь.
Связный и несвязный граф представлен на рис.3.9.
Любой граф можно рассматривать как некоторую совокупность связных графов. Каждый из этих графов называется компонентом исходного графа.
Несвязный граф, изображённый на рис. 3.9, имеет два компонента.
Множество дуг, исключение которых из графа увеличивает число его компонентов, называется разрезом.
Для связного графа, изображенного на рис. 3.9, разрезом является выделенная дуга e, так как её удаление увеличивает число компонентов до двух.
Пусть G=(V,E), VV, тогда граф, множество вершин которого совпадает с V, а множество дуг включает все дуги множества E с концевыми вершинами в V, называется подграфом графа G, порождённым V.
Пусть EE, тогда граф, для которого множество дуг совпадает с E, а множество вершин включает вершины, инцидентные дугам из E, называется подграфом графа G, порождённым E.
Граф называется полным, если любые две его вершины смежные.
Граф G называется пустым, если в нём нет рёбер.
Граф, который не содержит циклов, называется ациклическим.
Связный неориентированный ациклический граф называется деревом, множество деревьев называется лесом.
Если рёбра, составляющие дерево, заменить ориентированными дугами, то получим ориентированное дерево. Если из контекста ясно, о каком дереве идет речь, то в дальнейшем слово ориентированное будем опускать.
Для ориентированного дерева имеет смысл ввести понятие корня. Минимальное по мощности множество вершин ориентированного дерева, из которых существуют пути во все оставшиеся вершины, будем называть множеством корней.
Покрывающим (остовным) деревом графа G называется дерево, являющееся подграфом графа G и содержащее все его вершины.
Если граф G несвязен, то множество, состоящее из основных деревьев каждой компоненты, называется покрывающим (остовным) лесом.
Обобщением графа является гиперграф.
В гиперграфе, в отличие от графа, рёбрами могут быть не только двухэлементные, но и любые подмножества вершин.
Подобные объекты в математике известны давно, однако введение термина гиперграф связано с успешным рассмотрением на них ряда важных понятий и методов теории графов.
Пустым называется граф без рёбер. Полным называется граф, в котором каждые две вершины смежные. Граф называется связным, если для любых двух вершин существует путь, соединяющий эти вершины.
.1 Теоремы
.Вершины графа называются смежными , если существует ребро , их соединяющее.
.Два ребра G1 и G2 называются смежными, если существует вершина, инцидентная одновременно G1 и G2.
.Каждый граф можно представить в пространстве множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам (или дугам - в последнем случае направление обычно указывается стрелочками). - такое представление называется укладкой графа..
.Конечная последовательность необязательно различных рёбер E1,E2,...En называется маршрутом длины n, если существует последовательность V1, V2, ... Vn необязательно различных вершин, таких, что
Ei = (Vi-1,Vi ).
1.Если совпадают, то маршрут замкнутый.
2.Маршрут, в котором все рёбра попарно различны, называется цепью.
3.Замкнутый маршрут, все рёбра которого различны, называется циклом. Если все вершины цепи или цикла различны, то такая цепь или цикл называются простыми.
4.Цикл, в котором все вершины, кроме первой и последней, попарно различны, называется простым циклом.
5.Степень вершины - число ребер, которым инцидентна вершина V, обозначается D(V).
.2 Способы задания графа
Пусть G(V, E) - связный неориентированный граф, каждому ребру которого приписан некоторый вес отличный от 0 (рис. 1). Существуют различные способы задания графа: в виде матрицы весов, матрицы смежности или инцидентности, списка ребер. Каждый из этих способов имеет свои преимущества и недостатки.
E2E4E5
E3
E1 E7
E6
E8
E9
Рис. 1Пример неориентированного графа
Матрицей весов называется квадратная матрица размерности nхn (n- количество вершин), элемент которой стоящий в i строке и j столбце определяется по правилу:
Матрица смежности - это булева матрица (иногда ее называют двоичной или битовой) порядка n: R=||r[ij]||, в которой строкам и столбцам поставлены в соответствие вершины графа G, и r[ij]=1,если вершины vi, vjV смежные, и r[ij]=0 в противном случае. Так для неориентированного графа, представленного на рис. 1, матрица смежности имеет вид таблицы 1.
Таблица 1. Матрица смежности
V1V2V3V4V5V6V70110001V11010000V21110101V30000000V40010001V50000001V61010110V7
Матрица инцидентности - это также булева матрица Q=||q[ij]|| размера nxm, в которой строкам поставлены в соответствие вершины графа, а столбцам - ребра. Если граф - неориентированный ,то матрица инцидентности такого графа является булевой матрицей, в которой q[ij]=1, если вершина vi инцидентна ребру еj, и q[ij]=0 в противном случае. Так для неориентированного графа, представленного на рис. 1, матрица инцидентности имеет вид, как в таблице 2.
Таблица 2. Матрица инцидентности
Е1Е2Е3Е4Е5Е6Е7Е8Е9