Цициашвили, М. А. Осипова, А. С. Лосев Дальневосточный федеральный университет, Институт прикладной математики ДВО РАН Поступила в редакцию 12.11.2014 г. Аннотация. <...> В настоящей работе строятся последовательные алгоритмы выделения компонент связности вершин в неориентированного графе и компонент сильной связности вершин в ориентированном графе. <...> На каждом шаге работы алгоритма поступает информация об очередной вершине графа и о ребрах, соединяющих ее хотя бы с одной из вершин в каждой из выделенных ранее компонент связности. <...> В ориентированном графе в процессе работы алгоритма на каждом шаге определяется отношение частичного порядка между компонентами сильной связности. <...> В отличии от известных в литературе алгоритмов выделения компонент связности, основанных на поиске в глубину или в ширину, предложенный в данной работе алгоритм не возвращается повторно к уже обработанным вершинам в "дереве поиска" и не определяет для каждой вершины из "дерева поиска" всех смежных с ней. <...> Ключевые слова: отношение частичного порядка, компоненты связности, компоненты сильной связности, факторизация. <...> In this paper sequantial algorithms of connectivity components separation in nondirected graphs and components of strong connectivity in directed graphs are constructed. <...> In comparison with known algorithms of connectivity components separation based on a search in a depth or in a width suggested algorithm does not return iteratively to processed nodes in "search tree" and does not define for each node from "search tree" all incident nodes. <...> Keywords: a relation of a partial order, a component of a connectivity, a component of a strong connectivity, a factorization. <...> ВВЕДЕНИЕ Известные в литературе [1], [2] алгоритмы выделения компонент связности в неориентированных графах основаны на поиске в глубину или в ширину, а алгоритмы выделения компонент сильной связности в орграфах - на вариации алгоритма поиска в глубину (алгоритмы Косарайю, Тарьяна). <...> Эти алгоритмы определяют все вершины, достижимые из выбранной s при построении "дерева поиска" , которое является компонентой связности, содержащей вершину s <...>