Рассматриваются минимальные реберные k-расширения предполных графов - графов, в которых есть вершина, смежная со всеми остальными. Доказывается лемма, позволяющая оценить предельные значения k, при которых предполный граф может иметь минимальные реберные k-расширения, а также указать их общий вид. Дается полное описание всех минимальных реберных k-расширений для предполных графов, являющихся соединением полного графа с вполне несвязным графом, цепью и циклом.
Скачать электронную версию публикации
Загружен, раз: 63
- Title МИНИМАЛЬНЫЕ РЕБЕРНЫЕ РАСШИРЕНИЯ НЕКОТОРЫХ ПРЕДПОЛНЫХ ГРАФОВ
- Headline МИНИМАЛЬНЫЕ РЕБЕРНЫЕ РАСШИРЕНИЯ НЕКОТОРЫХ ПРЕДПОЛНЫХ ГРАФОВ
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 1(7)
- Date:
- DOI
Ключевые слова
предполный граф, минимальное реберное расширение, отказоустойчивая реализация, precomplete graph, minimal edge extension, fault toleranceАвторы
Ссылки
Harary F., Hayes J. P. Edge fault tolerance in graphs // Networks. 1993. V. 23. P. 135-142.
Harary F., Hayes J. P. Node fault tolerance in graphs // Networks. 1996. V. 27. P. 19-23.
Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. М.: Наука, 1997.
Hayes J. P. A graph model for fault-tolerant computing system // IEEE Trans. Comput. 1976. V.C25. No. 9. P. 875-884.
Абросимов М. Б. О вычислительной сложности расширений графов // Прикладная дискретная математика. Приложение. 2009. №1. С. 94-95.
Абросимов М.Б. Минимальные k-расширения предполных графов // Изв. вузов. Математика. 2003. №6(493). С. 3-11.
МИНИМАЛЬНЫЕ РЕБЕРНЫЕ РАСШИРЕНИЯ НЕКОТОРЫХ ПРЕДПОЛНЫХ ГРАФОВ | Прикладная дискретная математика. 2010. № 1(7).
Скачать полнотекстовую версию
Полнотекстовая версияЗагружен, раз: 179