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

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

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


Образец для цитирования:

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

Опубликована онлайн: 
27.08.2013
Язык публикации: 
русский
Рубрика: 
УДК: 
519.17

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

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

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

DOI: 
10.18500/1816-9791-2013-13-3-99-104
Библиографический список: 
  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 с.
Краткое содержание:
(downloads: 8)
Полный текст в формате PDF:
(downloads: 11)