АЛГОРИТМЫ КЛАСТЕРИЗАЦИИ ГРАФОВ

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

• Цициашвили Г.Ш.
• Лосев А.С.
• Осипова М.А.

• Прикладные науки. Медицина. Технология

• Естественные науки
• Физико-математические науки