О задаче соединения элементов вычислительной системы

Статья посвящена рассмотрению сформулированной Ю. Г. Решетняком задачи о минимальной степени информационного графа. Установлено, что эта степень равна по порядку $\frac{\log n}{\log\log n}$, где $n$ – количество вершин графа. Приводятся исторические сведения о возникновении этой задачи и возможных ее приложениях.