Main menu

Спектральная теория графов: экспандеры и неравенство Чигера

Матричная алгебра способна извлекать колоссальные объемы информации не только из физических уравнений, но и из абстрактных топологических сетей (графов). Спектральная теория графов изучает свойства матриц смежности и лапласианов сетей для ответов на важнейшие вопросы топологии: насколько хорошо перемешивается информация в социальной сети? Насколько сложно разорвать интернет-соединение пополам? В центре этой теории находятся так называемые экспандеры — уникальный класс графов, которые сочетают в себе на первый взгляд несочетаемое: они имеют крайне мало ребер (очень разреженные, дешевые в постройке), но при этом обладают невероятно высокой алгебраической связностью, обеспечивая фантастическую скорость распространения сигнала.

Подробнее

Соц. сети