Образец для цитирования:
Комаров Д. Д. Минимальные реберные расширения пальм // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2013. Т. 13, вып. 3. С. 99-104. DOI: https://doi.org/10.18500/1816-9791-2013-13-3-99-104
Минимальные реберные расширения пальм
Минимальные реберные расширения графов можно рассматривать как модель оптимальной реберной отказоустойчивой реализацией некоторой системы. Задача нахождения минимальных реберных расширений произвольного графа является NP-полной, поэтому представляет интерес нахождение классов графов, для которых возможно построить минимальное реберное расширение аналитически. Эта работа посвящена реберным 1-расширениям графов специального класса—класса пальм. В этой работе приводится вид реберного 1-расширения для некоторых пальм и доказывается его минимальность.
1. Harary F., Hayes J. P. Edge fault tolerance in graphs // Networks. 1993. № 23. P. 135–142.
2. Абросимов М. Б. О сложности некоторых задач, связанных с расширениями графов // Мат. заметки. 2010.
Т. 88, № 5. С. 643–650.
3. Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. М. : Наука, 1997. 368 с.
