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