О СПЕКТРАЛЬНЫХ ПОРТРЕТАХ МАТРИЦ ИНЦИДЕНТНОСТИ ГРАФОВ БЛИЖАЙШИХ СОСЕДЕЙ

В работе исследуется возможность применения метода С.К. Годунова построения спектрального портрета матрицы для оценки ранга матриц специального вида, которые появляются в ряде приложений, таких, как анализ структур графов ближайших соседей, теория конечных автоматов и оценка спектра разреженных матриц. Описан вычислительный алгоритм генерации ансамбля матриц случайных расстояний и связанных с ним графов ближайших соседей. На основе вычислительного эксперимента оценены параметры распределения степеней вершин случайных графов ближайших соседей. Оценки удается получить вследствие того, что указанное распределение не зависит от функции распределения случайных расстояний и является многомерным нормальным распределением. Доказано, что ранг матрицы инцидентности графа ближайших соседей равен суммарному числу вершин со степенями 0 и 1 по входящим ребрам, и получено распределение ранга такой матрицы. Показано, что в данной задаче определения ранга матрицы весьма эффективным является также метод, основанный на анализе распределения степеней вершин. Библ. 17. Фиг. 4.

граф ближайших соседей, распределение степеней вершин, спектральный портрет, распределение ранга матрицы