Main menu

Линейная алгебра в теории графов: матрица смежности и лапласиан

Теория графов, изучающая узлы (вершины) и связи между ними (ребра), на первый взгляд кажется чисто комбинаторной дисциплиной, далекой от векторов и матриц. Однако алгебраическая теория графов доказывает обратное. Любую сеть — будь то маршруты интернета, социальные связи пользователей, транспортные развязки или молекулярная структура химических соединений — можно полностью закодировать с помощью квадратных матриц. Как только граф превращается в матрицу, к нему немедленно можно применить всю колоссальную мощь линейной алгебры: спектральный анализ, сингулярное разложение и возведение в степень. Это позволяет алгоритмам за доли секунды выявлять скрытые кластеры, находить важнейшие узлы и предсказывать пути распространения информации в сетях с миллионами вершин.

Подробнее

Соц. сети