Саратовским государственным университетом получено свидетельство о государственной регистрации компьютерной программы «Проверка линейного графа на шпернеровость». Автором программы является студентка шестого курса КНиИТ Е.Н. Новокшонова.

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

Линейный граф называется шпернеровым, если среди его максимальных по длине антицепей имеется хотя бы одна, все элементы которой располагаются на одном уровне. Предложенная программа принимает на вход линейный граф, заданный в виде двоичного вектора длины n-1, где n – количество вершин в графе. Программа призвана ответить на вопрос, является ли заданный линейный граф шпернеровым. В случае положительного ответа программа выдаёт ответ «Yes» и какую-то из наибольших по количеству входящих в неё вершин правильных антицепей в виде последовательности номеров вершин, входящих в неё.