Об алгоритме вычисления точного значения параметра произвольного дерева

Н.Н. Давтян1, Р.Р. Камалян2

1Иджеванский филиал Ереванского государственного университета 2Институт информатики и проблем автоматизации НАН РА

Предложен алгоритм, позволяющий по любому дереву G вычислять точное значение параметра ^,12(G) за линейное время.

Ключевые слова: дерево, реберная раскраска, интервальный спектр.

Обозначения, определения, вспомогательные результаты, цель работы

В работе рассматриваются неориентированные графы без кратных ребер и петель [1], содержащие хотя бы одно ребро. Множество вершин графа G обозначается через V(G), множество ребер через E(G). Степень вершины

x є V(G) в графе G обозначается через dG(x), наибольшая из степеней вершин графа G через A(G) . Для графа G и Vi, где 1 < i < A(G), положим: V(l)(G) = {x є V(G)/dG(x) = i} . Для графа G положим: y(G) = |V(1)(G)|, r(G) |v(A(g))(G)| . Для графа G и произвольных двух его вершин x и у через pG(x,y) обозначаем расстояние [1] между x и у в графе G. Для произвольного дерева G и двух любых его вершин x и у через PG (x, у) обозначаем простую цепь [1], соединяющую вершины x и у, через VPG(x, у) множество вершин этой цепи, и обозначаем

int VPg (x, у) VPg (x, у) ({x} u {у}).

Если D непустое конечное подмножество множества N натуральных чисел, то через l(D) и L(D) обозначаем, соответственно, его наименьший и наибольший элемент. Непустое конечное подмножество D множества N назовем интервалом, если из t є N, l(D) < t < L(D) вытекает t є D .

Правильной реберной 1 — раскраской (1 є N) графа О назовем функцию ф : Е(О) ^ {1,2,…, 1}, удовлетворяющую условиям:

для VI, 1 < і < 1, существует хотя бы одно ребро е(і) є Е(О) с ф(е(1) ) = і;

для любых двух смежных ребер е’ є Е(О), е» є Е(О) ф(е ‘)^ф(е").

Наименьшее значение 1, при котором существует правильная реберная 1 раскраска графа О, обозначается через х'(О).

Множество всех правильных реберных 1 — раскрасок графа О, где х’ (О) < 1 < |Е(О)|, обозначим через а(О,1), и пусть

|Е(О)|

а(О) = ^ а(О,1;).

1=х’ (О)

Для графа О и раскраски ф є а(0,1), где х’ (О) < 1 < |Е(О)|, через ф* обозначим правильную реберную 1 — раскраску графа О , удовлетворяющую условию: для Ve є Е(О) ф* (е) = 1 +1 — ф(е).

Если ф є а (О) и х є У(О), то множество { ф(е) / е є Е(О) , е смежно с х } назовем спектром вершины х графа О при раскраске ф и обозначим через БО (х, ф) ; через ГО (ф) обозначим число |{ ъ є У (О) / БО (ъ, ф) является интервалом}!.

Замечание 1. Для любого графа О и Vф є а(О) ГО (ф) = ГО (ф*) .

Изучению поведения функции ГО(ф) для графов некоторых классов при ф є а(0,1) и 1, удовлетворяющем неравенству х’ (О) < 1 < |Е(О)| , посвящены работы [2-5]. В работе [2] для произвольного связного неориентированного конечного графа без кратных ребер и петель были введены параметры , д12,

Д21, д22, имеющие, в частности, теоретико-игровой смысл (о параметре д12 см. работу [3]).

Предположим, что ребра графа раскрашиваются в игре двух лиц с антагонистическими интересами и асимметричным распределением ролей. Первому игроку дано право выбора количества цветов в раскраске, а второму право раскрасить граф с использованием количества цветов, указанного первым игроком. Первый игрок заинтересован в том, чтобы в итоговой раскраске графа оказалось как можно меньше вершин с интервальным спектром, а второй в том, чтобы таких вершин оказалось как можно больше. При такой интерпретации д21

является наименьшим, гарантированным для первого игрока числом вершин с интервальным спектром по окончании игры.

Аналогичный смысл может быть придан и параметрам д11 и д22, с той разницей, что интересы обоих игроков будут совпадающими: в случае с оба заинтересованы в том, чтобы число вершин с интервальным спектром в итоговой раскраске графа оказалось как можно меньше, а в случае с д22 как можно больше.

В [2] найдены точные значения параметров Д11, д12, д21 и д22 для «лестниц Мебиуса».

В [4] найдены точные значения параметров д11, д12, д21 и д22 в случаях,

когда граф О изоморфен либо простой цепи, либо простому циклу, либо простому циклу с одной хордой.

В [5] найдены точные значения параметров д11 и д22 для деревьев.

В [3] найдено точное значение параметра д12 для деревьев. Именно, доказана

Теорема. Для произвольного дерева Б с |У(Б)| > 2

MD) = Y (D) + r(D) + R(D),

где

-2, если A(D) = 1

если A(D) = 2 или A(D) > 4

R(D) <

min {|{х е V(dV dD(x) = 2 Sd (Х Ф) является интервалом}]/если A(D) =’

если A(D) = 3.

Целью работы является описание алгоритма, позволяющего для произвольного дерева Б с А (Б) = 3 вычислять точное значение параметра д12(В) за линейное время.

Для Уп е N , п > 2 через Рп обозначаем граф, изоморфный простой цепи [1] с п вершинами; предполагаем, что выбрано некоторое направление для движения вдоль цепи Рп от одной из ее висячих вершин до другой, и все ребра

из множества Е(Рп ) в соответствии с упомянутым движением последовательно пронумерованы: е1,…,еп _1.

2. Результат

Для У Б е N положим:

если s = 1

если s 2 и I1/1 1 s-1, F0(ei+i) = Fo(ei)}0

g( o) = 1|{^1 < i < s 1, |Fo(ei+i) Fo(ei) = ^

если s 2 и {i/1 < i < s-1, Fo(ei+1) = Fo(ei)} = 0.

Для Vs e N и любых i, j, где i e {1,2,3}, j e {1,2,3}, положим:

подпись: c ■ ■ = <
s.i.j
o, если s = 1 и i = j да, если s = 1 и i Ф j min {g(F)/F e M(sX F(e1) =i, F(es) = j}, если s 2.

Легко видеть, что для У б е N и любых 1, ], где 1 е {1,2,3} , ] е {1,2,3}, верно равенство С51 ^ = С5 ^ 1. Заметим также, что для У б е N ек11 = ек33 и

Cs,1,2 Cs,2,3 •

Нетрудно убедиться, что для Уб е N имеют место следующие равенства:

Г0, если б = 2г +1, где г е Ъ, г > 0 сб 11 = ^да, если б = 2

[2, если б = 2г, где г е N г > 2,

С = (да, если б = 1

кД,2 = (1, если б е N, б > 2,

Г да, если б = 1 С513 = < 2, если б = 2г +1, где г е N

0, если б = 2г, где г е N

o,         если s = 1

Cs,2,2 = ГО если s = 2

если s e N, s 3.

Ясно, что если О дерево с А(О) = 3 и {х е У(О)/ёс(х) = 2} = 0, то Я(О) = 0 и Д12 (О) = у(О) + Г(О), поэтому в остальной части работы рассматриваются деревья О с А(О) = 3 , удовлетворяющие условию {х е У(О)/М х) = 2} Ф 0 . Договоримся считать, что при исследовании любого такого дерева О автоматически фиксируется некоторая (произвольная) его вершина х0 с ёс(х0) = 2 и вводятся в рассмотрение следующие, однозначно

определяемые выбором вершины х0 , числа и множества.

(х0) 3 |>п< УРс(х0,2)п У(3,)(с)| ;

В(х0,О) У(|,(О) и У(3|(О) и {х0};

Bg(x„,0) . V<1>(G).

•’GV^-CI

К1)

для Vx е B(x0,G)V( >(G) определено подмножество Post(x0,x,G) вершин дерева G следующим образом:

PoSt(x x G) = К2 е B(x0, G Vx е int VPG (x0 , z)} , если x * xC

post(xo,x,G) = |b(xc,G){xo}, если x = x0;

для j = 1,2,…,1 + v G(xo) определено подмножество BG(x0,j) множества V(3)(G) следующим образом:

BG(x0,j) =1x е B(x0,G)l_JBG(x0,iV P0St(xC,x,G) ^ l_JBG(x0,i)| .

[           i=0       /           i=0       J

(При этом ясно, что для Vjo, где 1 < jo < 1 + vg(x0), и для Vx е V(3)(G) ‘и{x0}, из соотношения x е BG(xo,jo) вытекает существование двух вершин x^, x^2 в дереве G , удовлетворяющих условиям:

{x ^1,x ■! 2 } ^ PoSt(xo,X,G),

int VPg (x, x^i) n V(3) (G) = 0, где i = 1,2 .)

Алгоритм А вычисления для произвольного дерева G с |V(G)| > 2 числа A(G), равного точному значению параметра R(G) .

Шаг 0. Присвоение чисел a1(x), a2(x) всем вершинам x из множества

Bg(xc,0).

Для Vx е Bg(x0,0) и Vi, 1 <i < 2, положить ai(x) = 0 .

Шаг j. (1 < j < vG(xo)) . Присвоение чисел a1(x) , a2(x) всем вершинам x из множества BG(x0 , j) . (Осуществление Шага j начинается тогда и только тогда, когда полностью завершены Шаги 0, 1, …, j-1.)

Последовательно для всех вершин x из BG(x0,j) положить:

a1(x) = min {irdll (CpG(x,x;i),2,k + ak(x j} + fmii2 (CPG(x,x,2),1,k + ak(x ^ , fmki2 (CPG(x,x.1),1,k + ak(x^1)}+ rrki2 (CPG(x,x.2),2,k + ak(x^2)}} ,

a2(x) = mj2 (CPG(x,x.1),1,k + ak(x^1)}+ Jmi2 |CPG(x,x.2),1,k + ak(x^ .

Замечание 2. Ясно, что в результате выполнения Шага vG (xo) будут вычислены числа a1(xo, ), a2(xoh ), a1(xo, ), a2(xo. ).

Шаг 1 + Уа(х0) . Вычисление числа А(О) . Положить:

А(О) = тш {тип {ср„(х0,х0и хи + ак (хо,1)} + тт {Ср„(х0Л11 т + ак (хо„)} +1,

ШкЗ {С№о.Хоа ) 2 к + ак <х0,1 )} + ЩЗ {с„0(хо.хо11 ),1,к + МХ0„ )} ■+ 1,

Ш2 {СР»(хо,хо„ )Ак + ак (х0.1 )} + ЩЗ {СР„(хо,хо„ ли + (х0„ )}} ■

Шаг ! + Уа(х0) . Завершение алгоритма. Стоп.

Замечание 3. Корректность алгоритма А вытекает из определения чисел С51 ^ (б е N , 1 е {1,2,3} , ] е {1,2,3}), их свойств, из описания шагов алгоритма

А, из замечания 1 и из принципа динамического программирования [6].

Замечание 4. Нетрудно убедиться, что указанные до описания Алгоритма А вычисления чисел и множеств, связанных с выбором вершины х0 с

(х0) = 2 дерева О, могут быть выполнены за время О (| У(О) |) .

ЛИТЕРАТУРА

Harary F. Graph Theory. Addison-Wesley, Reading, MA. 1969.

Давтян Н.Н., Камалян Р. Р. О границах экстремумов числа вершин с интервальным спектром во множестве правильных реберных t-цветных раскрасок «лестниц Мебиуса» при варьировании t // Сборник научных статей Годичной научной конференции (5-10 декабря 2008г.) Российско-Армянского (Славянского) университета. Ер., Изд-во РАУ, 2009. СС. 81-84.

Давтян Н.Н., Камалян Р.Р. О параметре ц12 дерева // Сборник научных статей Годичной научной конференции (30 ноября 4 декабря 2009г.) Российско-Армянского (Славянского) университета. Ер., Изд-во РАУ, 2010. СС. 149-151.

Давтян Н.Н., Камалян Р.Р. О свойствах числа вершин с интервальным спектром в правильных реберных раскрасках некоторых графов // Вестник Российско-Армянского (Славянского) университета. Серия физико-математические и естественные науки, № 2, 2009. СС. 33-42.

Давтян Н.Н. О наименьшем и наибольшем возможных числах вершин с интервальным спектром на множестве правильных реберных раскрасок дерева // Математические вопросы кибернетики и вычислительной техники. Т. 32. Ер., 2009. СС. 107-111.

Беллман Р. Динамическое программирование. М.: Иностранная литература, 1960.

ON AN ALGORITHM OF EVALUATION OF THE EXACT VALUE OF THE PARAMETER ^12 OF AN ARBITRARY TREE

N.N. Davtyan, R.R. Kamalian

A linear algorithm is proposed for evaluation of the exact value of the parameter ^12 for an arbitrary tree.

Материал взят из журнала Вестник выпуск Физико-математические и естественные науки