отказоустойчивая реализация

О НИЖНЕЙ ОЦЕНКЕ ЧИСЛА РЕБЕР МИНИМАЛЬНОГО РЕБЕРНОГО 1-РАСШИРЕНИЯ СВЕРХСТРОЙНОГО ДЕРЕВА

Граф G∗ называется реберным 1-расширением графа G, если граф G можно вложить в каждый граф, получающийся из графа G∗ , удалением любого его ребра. Реберное 1-расширение G∗ графа G называется минимальным, если графы G и G∗ имеют одинаковое число вершин, а среди всех реберных 1-расширений графа G с тем же числом вершин граф G∗ имеет минимальное число ребер. Дерево называется сверхстройным, если только одна его вершина имеет степень больше двух.

О числе дополнительных ребер минимального вершинного 1-расширения сверхстройного дерева

Граф G* называется вершинным 1-расширением графа G, если граф G можно вложить в каждый граф, получающийся из графа G* удалением любой его вершины вместе с инцидентными ребрами. Вершинное 1-расширение G* графа G называется минимальным, если граф G* имеет на одну вершину больше, чем граф G, а среди всех вершинных 1-расширений графа G с тем же числом вершин граф G* имеет минимальное число ребер. Дерево называется сверхстройным (звездоподобным), если только одна его вершина имеет степень больше двух.

Характеризация орграфов с малым числом дополнительных дуг минимального вершинного 1-расширения

: Граф G∗ называется вершинным 1-расширением графа G, если граф G можно вложить в каждый граф, получающийся из графа G∗ удалением любой его вершины вместе с инцидентными ребрами. Вершинное 1-расширение G∗графа G называется минимальным, если граф G∗ имеет на одну вершину больше, чем граф G, а среди всех вершинных 1-расширений графа G с тем же числом вершин граф G∗ имеет минимальное число ребер. Рассматривается задача описания ориентированных графов, минимальное вершинное 1-расширение которых имеет заданное число дополнительных дуг.