Вычислительные технологии и математические модели в науке, технике и образовании

Алма-Ата, Казахстан, 18-20 сентября 2002 года

Тезисы докладов

О точном вычислении вероятности связности графа

Родионов А.С., Родионова О.К.

Институт вычислительной математики и математической геофизики СО РАН (Новосибирск)

В докладе рассматривается вопрос применения формулы Мура-Шеннона для точного расчета вероятности связности графов сетей реальной размерности. Алгоритм имеет экспоненциальную сложность, но применение различных приемов, учитывающих особенности графов, динамически возникающих в процессе нисходящих рекурсий, позволяют существенно снизить число операций, что дает возможность расчитывать графы с числом ребер до сотен при средней степени вершины порядка 5-6.

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

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

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

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии
Обратная связь

[Головная страница]
[Конференции]