Известия Саратовского университета. Новая серия.
ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)


теория графов

Вершинные расширения 4-слойных графов и гиперкубов

Дж. П. Хейз предложил математическую модель отказоустойчивых реализаций технических систем на основе графов, которой в более абстрактном виде соответствуют вершинные и рёберные расширения графов. Граф $G^*$ называется вершинным $k$"-расширением графа $G$, если граф $G$ вкладывается в каждый граф, полученный из $G^*$ удалением любых $k$ вершин. Если никакая собственная часть графа $G^*$ не является вершинным $k$-расширением графа $G$, то расширение $G^*$ называется неприводимым.

Оптимальная эйлерова реконструкция ориентированных графов методом добавления дуг

В работе решается следующая задача: дан орграф, необходимо добавить минимальное число дуг, чтобы орграф стал эйлеровым