отказоустойчивость

Граф $G=(V, \alpha, f)$ — это цветной граф с определенной на множестве его вершин функцией раскраски $f$. Цветной граф $G^*$ называется реберным $1$-расширением цветного графа $G$, если граф $G$ можно вложить с учетом цветов в каждый граф, получающийся из графа $G^*$ удалением любого его ребра. Реберное $1$-расширение $G^*$ графа $G$ называется минимальным, если граф $G^*$ имеет столько же вершин, сколько содержит исходный граф $G$, а среди всех реберных $1$-расширений графа $G$ граф $G^*$ имеет минимальное число ребер.

Минимальные вершинные 1-расширения графов можно рассматривать как модель оптимальной вершинной 1-отказоустойчивой реализации некоторой системы. Эта работа посвящена вершинным 1-расширениям графов специального класса – класса пальм. Приводится решение задачи нахождения минимального вершинного 1-расширения для двулистных пальм.

В 1993 г. Frank Harary и John P. Hayes предложили основанную на графах модель для исследования отказов связей элементов дискретных систем. Технической системе сопоставляется граф. Элементам системы соответствуют вершины графа, а связям между элементами — рёбра или дуги графа. Под отказом связи между элементами системы понимается удаление из графа системы соответствующего ребра (или дуги). Формализацией отказоустойчивой реализации системы является расширение графа.