On T-irreducible extensions of starlike trees.pdf Все понятия и определения взяты из работы [1]. Определение 1. Расширением n-вершинного графа G называется граф H с (n + 1) вершинами, такой, что граф G вкладывается в каждый максимальный подграф графа H. Простейшим примером расширения графа является его тривиальное расширение — соединение с одноэлементным графом (т. е. к графу G добавляется новая вершина, которая соединяется ребром с каждой вершиной графа G). Возникает вопрос о получении такого расширения графа G, которое не содержит «лишних» ребер. Один из способов — конструкция минимального расширения графа [2], другой — его Т-неприводимого расширения [3]. Определение 2. Минимальным расширением графа G называется его расширение с минимальным количеством ребер. В общем случае при построении минимального расширения возникает необходимость добавлять ребра в исходный граф, т. е. менять всю систему, моделируемую графом. Но иногда технически важно найти решение следующей задачи: построить оптимальное расширение данного графа, сохраняя его первоначальную конструкцию (т. е. не меняя связей внутри него). Существует следующая процедура: — построить тривиальное расширение исходного графа; — удалять из полученного графа рёбра до тех пор, пока выполняется свойство расширения. Полученные графы назовем Т-неприводимыми расширениями. Для произвольного графа количество неизоморфных ТНР неизвестно. Покажем примеры ТНР для некоторых классов графов. Для n-вершинной цепи единственным ТНР является (n + 1)-вершинный цикл. Для n-вершинного цикла единственным ТНР является тривиальное расширение исходного цикла. На рис. 1 представлен граф, имеющий два неизоморфных ТНР. a в б Рис. 1. Граф G (а) и два его неизоморфных ТНР (б и в) Существует следующая нерешенная задача: для произвольного дерева построить все неизоморфные ТНР. Данная задача не решена и для произвольного сверхстройного дерева. Все неизоморфные ТНР для произвольной пальмы найдены в работе С. Г. Курносовой [4]. В настоящей работе найдены все неизоморфные ТНР для ещё одного подкласса сверхстройных деревьев — равнолучевых звезд. Определение 3. Граф называется равнолучевой звездой с m лучами, каждый из которых состоит из n вершин, если V = {г0, г»1,..., гП,... , v^,... , Vm}, а = {vjvj+1 : i = 1,... , n — 1; j = 1,..., m} U {v0vj : j = 1,... , m}, где г0 — центр равнолучевой звезды. Теорема 1. Пусть граф Sm — равнолучевая звезда с m лучами, каждый из которых состоит из n вершин (n ^ 2). Тогда единственным ТНР для Sm является граф, полученный из тривиального расширения графа Sm удалением ребер и>г»П-1, j = 1,..., m, где w — вершина, добавленная при построении тривиального расширения графа Sm.

Скачать электронную версию публикации