Известия Саратовского университета. Новая серия.

Серия Математика. Механика. Информатика

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)


Для цитирования:

Комаров Д. Д. Минимальные реберные расширения пальм // Известия Саратовского университета. Новая серия. Серия : Математика. Механика. Информатика. 2013. Т. 13, вып. 3. С. 99-104. DOI: 10.18500/1816-9791-2013-13-3-99-104

Статья опубликована на условиях лицензии Creative Commons Attribution 4.0 International (CC-BY 4.0).
Опубликована онлайн: 
27.08.2013
Полный текст:
(downloads: 221)
Язык публикации: 
русский
Рубрика: 
УДК: 
519.17

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

Авторы: 
Комаров Дмитрий Дмитриевич, Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского
Аннотация: 

 Минимальные реберные расширения графов можно рассматривать как модель оптимальной реберной отказоустойчивой реализацией некоторой системы. Задача нахождения минимальных реберных расширений произвольного графа является 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 с.
Поступила в редакцию: 
19.02.2013
Принята к публикации: 
18.07.2013
Опубликована: 
30.08.2013
Краткое содержание:
(downloads: 93)