Аннотация:
Изучается влияние операций склейки и клонирования подграфов на диаметр графа. Рассматриваются вершинно-диаметральные графы, все вершины которых принадлежат диаметральным цепям, и возможности их использования при масштабировании графов с ограничением диаметра. Приводятся примеры масштабирования деревьев, толстых деревьев и вершинно-диаметральных графов с помощью операций клонирования и склейки. Оценивается диаметр и сложность синтеза таких графов.
Ключевые слова:
деревья, толстые деревья, вершинно-диаметральные графы, диаметр, доминирующее множество с окрестностью, операции склейки и клонирования.
Полный текст:
PDF файл (494 kB)