minimal extensions of graphs.

Минимальные реберные расширения пальм

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