Минимальные реберные расширения направленных и ориен-тированных звезд | ПДМ. 2011. № 2(12).

Минимальные реберные расширения направленных и ориен-тированных звезд

Рассматриваются минимальные реберные k-расширения графов, которые получаются из звездного графа произвольной ориентацией ребер. Ранее было получено полное решение, описывающее минимальные вершинные и реберные k-расширения неориентированных звезд, а также минимальные вершинные k-расширения ориентированных звезд. В этой работе дается полное описание всех минимальных реберных k-расширений для ориентированных и направленных звезд.

Minimal edge extensions of oriented and directed stars.pdf ВведениеОриентированным графом (далее орграфом) называется пара G = (V, а), гдеV - конечное непустое множество, называемое множеством вершин, а а - отноше-ние на множестве вершин V, называемое отношением смежности. Орграф с анти-симметричным отношением смежности называется направленным графом, или дигра-фом. Граф с симметричным и антирефлексивным отношением смежности называетсянеориентированным графом, или неографом. Основные определения даются по рабо-те [1].Граф с пустым отношением смежности называется вполне несвязным и обозна-чается On, где n - число вершин. Полный диграф без петель называется турниром.Циклической тройкой называется 3-вершинный турнир, у которого в каждой вершинеесть одна исходящая и одна входящая дуга.Симметризацией орграфа (G = (V, а) называется неограф G = (V, (а U а- i)\А),то есть симметризация орграфа получается заменой дуг ребрами и удалением петель.Вложением графа G i = (У^а i) в граф G2 = (V2^2) называется такое взаимнооднозначное отображение ^ : V ^ V2, что для любых вершин u,v . V выполняетсяследующее условие: (u,v) . а i ^ (^(u),^(v)) . а2.Два графа G = (V , а ) и G2 = (V2, а2) называются изоморфными, если можноустановить взаимно однозначное соответствие ^ : Vi ^ V2, сохраняющее отношениесмежности: (u,v) . а i ^ (^(u),^(v)) . а2 для любых u,v . V. Изоморфизм графана себя называется автоморфизмом. Две вершины u и v называются подобными, еслисуществует автоморфизм ^ : 0 (то есть одна вершина смежна с nнесмежными вершинами). Ориентированной звездой будем называть орграф, симмет-ризация которого является звездой. Ориентированную звезду будем обозначать Zm,ra)P,где m и n - число вершин с единственной соответственно исходящей и входящей ду-гой, а p - число вершин с одной входящей и одной исходящей дугой. Направленнойзвездой будем называть ориентированную звезду, являющуюся диграфом, и обозна-чать (у направленной звезды p = 0). Вершину, являющуюся концом или началомкаждой дуги звезды, будем называть центральной. Вершину, соединенную со всемиостальными вершинами орграфа,будем называть полной. Полная вершина может бытьсоединена с другими вершинами исходящей дугой, входящей или парой встречных дуг.Центральная вершина является единственной полной вершиной звезды. Легко опре-делить количество дуг звезды Zm,ra)P: m + n + 2p.В работе [8] удалось найти общее решение для описания минимальных вершин-ных k-расширений предполных графов, то есть графов, которые имеют хотя бы однувершину, смежную со всеми остальными. Звездный граф является частным случаемпредполного графа, и в работе [9] дается полное описание минимальных вершинных иреберных k-расширений для неориентированных звезд. Дадим вспомогательное опре-деление и приведем соответствующую теорему относительно минимальных реберныхk-расширений.Под соединением двух графов G1 = (V1,a1) и G2 = (V2,a2), не имеющих общихвершин, понимается граф G1 + G2 = (V1 U V2, а1 U а2 U V1 x V2 U V2 x V1)Теорема 1 [9]. При k ^ n/2 граф K1+2k + On-2k является единственным мини-мальным реберным k-расширением графа K1 + On. При k > n/2 граф K1 + On не имеетминимальных реберных k-расширений.1. Минимальные реберные 1-расширенияОбозначим через ZKm;ra;P семейство графов, получающихся из звезды добав-лением p - 1 «центральной» вершины, соединением их между собой и центральнойвершиной звезды парами встречных дуг. Каждая из добавленных центральныхвершин соединяется m входящими и n исходящими дугами с произвольными источни-ками и стоками звезды Zm,n. По описанной схеме для заданной звезды в общем случаеможет быть построено много графов (рис. 1).Рис. 1. Звезда Z2,2 и графы вида ZK2,2,2Теорема 2. Относительно минимальных реберных 1-расширений направленныхзвезд справедливо следующее:1) при m = n =1 звезда Z1;1 имеет единственное с точностью до изоморфизмаминимальное реберное 1-расширение, которым является циклическая тройка;2) при mn > 1 звезда имеет минимальные реберные 1-расширения: K1>m+ra играфы, построенные по схемам ZKm-1;ra,2 и ZKm,ra-1)2;3) при m > 0, n = 0 звезда Zm0 имеет минимальные реберные 1-расширения видаZ K m - 1 , 0 , 2 ;4) при m = 0, n > 0 звезда Z0 n имеет минимальные реберные 1-расширения видаZK0,ra-1,2;5) при m = 2, n =1 звезда Z2>1 имеет еще одно минимальное реберное 1-рас-ширение - турнир, получающийся из циклической тройки добавлением однойвершины и дуг от нее во все остальные вершины;6) при m = 2, n =1 звезда Z2 1 имеет еще одно минимальное реберное 1-рас-ширение - турнир, получающийся из циклической тройки добавлением однойвершины и дуг в нее из всех остальных вершин.Доказательство. Убедимся, что орграфы K1 m + n , ZKm - 1 r a 2 и ZKm r a - 1 2 дей-ствительно являются реберными 1-расширениями звезды Zm,n.Для неориентированной звезды K1>m+ra проверка вполне тривиальна. Пусть в звез-де есть и источники, и стоки, то есть m > 0 и n > 0. Рассмотрим удаление в графеK1 m + n любой дуги вида (v, u), где v - центральная вершина, а u - любая другая. Вло-жение звезды строится следующим образом: центральная вершина звездысоответствует вершине v. Вершины u и m - 1 из оставшихся вершин графа K1>m+ra бу-дут соответствовать источникам, а остальные n вершин - стокам. Аналогично - дляслучая удаления дуги вида (u,v). Заметим, что количество дуг в графе K1>m+ra в двараза больше, чем в звезде Zm,n, то есть 2(m + n).Пусть m > 0; рассмотрим орграф ZKm - 1 r a 2 . В этом графе две вершины имеютполустепени исхода и захода n + 1 и m соответственно, а у остальных вершин суммыполустепеней исхода и захода равны 2. Общее количество дуг равно 2(m + n). Обозна-чим две полные вершины через v1 и v2.Все дуги рассматриваемого орграфа можно разделить на три группы подобныхдуг:1) дуги от вершин v и v2 в остальные вершины (если n = 0, то дуг этого типаможет не быть);2) дуги в вершины v i и v2 из остальных вершин (если m = 1, то дуг этого типаможет не быть);3) дуги между вершинами v i и v2.Рассмотрим удаление из орграфа Z K m - 1;П;2 дуги каждого вида и укажем, какимобразом в получившийся орграф может быть вложена звезда Zm,n. Обозначим:1) G 1 -граф, получающийся из орграфа Z K m - 1;П;2 удалением дуги первого типа;пусть для определенности это будет дуга (v 1,u), где u - произвольная вершина,которая в звезде Z m n была стоком;2) G2 - граф, получающийся из орграфа Z K m - 1n 2 удалением дуги второго типа;пусть для определенности это будет дуга (w, v 1), где w - произвольная вершина,которая в звезде Zm,n была истоком;3) G3 - граф, получающийся из орграфа ZKm-1)n,2 удалением дуги третьего типа;пусть для определенности это будет дуга (v2,v1).Во всех трех случаях m - 1 вершин орграфов G1, G2, G3, из которых идет дугав вершину v2, и вершина v1 будут соответствовать источникам звезды Zm n, верши-на v2 -центральной вершине, а оставшиеся n вершин орграфов G1, G2, G3 - стокамзвезды Zm>n.Аналогично рассмотрим орграф ZKm,n - 1 ) 2 при n > 0. В этом графе две вершиныимеют полустепени исхода и захода n и m + 1 соответственно, а у остальных вер-шин суммы полустепеней исхода и захода равны 2. Общее количество дуг снова равно2(m + n). Как и раньше, обозначим две полные вершины через v1 и v2. Все дуги рас-сматриваемого орграфа делятся на три группы подобных дуг:1) дуги от вершин vi и v2 в остальные вершины (если n = 1 , то дуг этого типаможет не быть);2) дуги в вершины v1 и v2 из остальных вершин (если m = 0, то дуг этого типаможет не быть);3) дуги между вершинами v1 и v2.Рассмотрим удаление из орграфа Z K m n - 1 2 дуги каждого вида и укажем, какимобразом в получившийся орграф может быть вложена звезда Zmn. Пусть1) граф G1 получается из орграфа Z K m n - 1 2 удалением дуги первого типа; пустьдля определенности это будет дуга (v1, u), где u - произвольная вершина, кото-рая в звезде Zm,n была стоком;2) граф G2 получается из орграфа ZKm,n - 1 ) 2 удалением дуги второго типа; пустьдля определенности это будет дуга (w,v1), где w - произвольная вершина, ко-торая в звезде Zmn была истоком;3) граф G3 получается из орграфа Z K m n - 1 2 удалением дуги третьего типа; пустьдля определенности это будет дуга (v1,v2).Во всех трех случаях m - 1 вершин орграфов G1, G2, G3, из которых идет дугав вершину v2, и вершина v1 будут соответствовать источникам звезды Zm,n, верши-на v2 -центральной вершине, а оставшиеся n вершин орграфов G1, G2, G3 - стокамзвезды Zm,n.Исследуем, какие у звезды Z m n могут быть минимальные реберные 1-расширения.Пусть G* -некоторое минимальное реберное 1-расширение звезды Zm,n. Так как звез-да Zm,n вкладывается в орграф G*, то в G* есть как минимум одна полная вершина.Рассмотрим случаи, когда такая вершина одна, две, три и более.I с л у ч а й . Предположим, что полная вершина одна, и обозначим ее через v.В этом случае вершина v должна быть соединена со всеми остальными вершина-ми парой встречных дуг. Если бы это было не так и вершина v была бы соединенас некоторой вершиной u только одной дугой, например (v, u), то вложение звездыв граф G* - (v, u) было бы невозможно, так как ни одна вершина не будет соответство-вать центральной вершине звезды Zm,n. Граф K1>m+ra имеет минимальное число дугсреди всех рассматриваемых графов, то есть графов с одной вершиной, соединеннойпарой встречных дуг со всеми остальными вершинами.II с л у ч а й . Пусть есть две полные вершины. Обозначим их через v1 и v2. Какиедуги должны быть между этими вершинами? Если между ними будет только однадуга, например (v1,v2), то граф, получающийся из G* после удаления дуги (v1,v2), небудет содержать ни одной вершины, которая могла бы соответствовать центральнойвершине звезды Zmn. Следовательно, вершины v1 и v2 соединены парой встречныхдуг.Каковы могут быть полустепени исхода и захода вершин v1 и v2? Очевидно, что онине могут быть меньше, чем у центральной вершины звезды Zm,n, то есть n и m соответ-ственно. Общее количество дуг, входящих и исходящих из этих вершин, равно m+n +1(две дуги между вершинами v1 и v2 и по одной дуге в или из оставшихся m + n - 1вершин). Таким образом, вершины v1 и v2 могут иметь либо полустепень исхода m, аполустепень захода n + 1, либо наоборот. Можно заметить, что вершины v1 и v2 долж-ны иметь одинаковые полустепени исхода и захода. В самом деле, если бы это было нетак и вершины v1 и v2 имели бы разные полустепени, например вершина v1 - (m, n +1),а вершина v2 - (m + 1, n), то удаление дуги (v1, v2) привело бы к орграфу, в которомвершины v1 и v2 имеют полустепени исхода и захода (m - 1 , n + 1) и (m + 1 , n - 1)соответственно. Ясно, что вложение в получившийся граф звезды невозможно.Итак, среди всех графов, имеющих две вершины с одинаковыми полустепенями исходаи захода, соединенные между собой парой встречных дуг, а с остальными вершина-ми хотя бы одной дугой, подходящими являются только графы семейств ZKm - 1 r a 2 иIII с л у ч а й. Рассмотрим случай, когда есть три вершины, соединенные совсеми остальными m + n - 2 вершинами хотя бы одной дугой. Обозначим эти полныевершины через v1, v2 и v3. Подобное соединение возможно при m + n ^ 2. Между этимивершинами, очевидно, должна быть по крайней мере одна дуга. Общее количество дугв таком графе будет не меньше чем 3 + 3(m + n - 2) = 3(m + n - 1).Если m + n = 2, то число дуг будет меньше, чем в рассмотренных ранее случа-ях I и II, где количество дуг равно 2(m + n). Непосредственной проверкой убедимся,что звезда Z1;1, которая является ориентированной цепью, имеет подходящее реберное1-расширение, которое в данном случае будет циклической тройкой (рис. 2).Звезды Z2 0 и Z0 2 не имеют реберных 1-расширений, построенных по рассматри-ваемой схеме. Если же добавить еще одну дугу, то мы получим графы, изоморфныеграфам семейств ZK1)0)2 и ZK0)1)2. При m + n = 3 имеем 3(m + n - 1) = 2(m + n). Тоесть число дуг будет таким же, как и в рассмотренных ранее случаях. Подходящимизвездами будут Z3 0 , Z2 1 , Z1 2 и Z0 3 . Непосредственной проверкой убеждаемся, чтозвезды Z3,0 и Z0,3 не имеют реберных 1-расширений, построенных по рассматривае-мой схеме, а звезды Z2>1 и Z1>2 имеют. Все их реберные 1-расширения изображены нарис. 3, причем первыми указаны расширения, укладывающиеся в рассматриваемуюсхему. Вершины v1, v2 и v3 образуют в них контур. Последующие три расширенияпринадлежат семействам ZK2 0 2 и ZK1 1 2 для звезды Z2 1 ; ZK0 2 2 и ZK1 1 2 для звез-ды Z1>2. Последние расширения - это звезды K1>3. Видно, что звезды Z2>1 и Z1>2 имеюттри изоморфных минимальных реберных 1-расширения и по два различных.Рис. 3. Звезды Z2;1 и Z1>2 и все их МР-1РIV с л у ч а й . Рассмотрим случай, когда есть p > 3 вершин, соединенных совсеми остальными m + n - p + 1 вершинами хотя бы одной дугой. Подобное соединениевозможно при m + n ^ p - 1. Между этими вершинами, очевидно, должна быть покрайней мере одна дуга, то есть индуцированный ими подграф является турниром.Общее количество дуг в таком графе будет не менее чемp(m + n - p + 1) + p(p - 1)/2 = p(m + n) - p(p - 1)/2.Исследуем, в каких случаях эта величина может быть меньше, чем 2(m + n) -коли-чество дополнительных ребер в случаях I и II. Получаемp(m + n) - p(p - 1)/2 ^ 2(m + n),(m + n)(p - 2) - p(p - 1)/2 ^ 0.Так как m + n ^ p - 1, то (p - 1)(p - 2) - p(p - 1)/2 ^ 0, откуда (p - 1)(p - 2 - p/2) ^ 0,а так как p > 3, то остается p/2 - 2 ^ 0, то есть p ^ 4.Случаи, когда p = 1, 2 и 3, были рассмотрены ранее, и, таким образом, еще толькопри p = 4 возможно реберное 1-расширение, которое будет иметь не больше дуг, чемрасширения из случаев I и II. Итак, при p = 4 количество дуг есть 4(m + n) - 6, а урасширений в случаях I и II - 2(m + n), причем m + n ^ 3. Сравнивая, получаем, чтолишь при m + n = 3 достигается равенство, а при остальных значениях количестводуг в расширении с p = 4 будет больше, чем в случаях I и II. При m + n = 3 имеемчетыре звезды, которые мы уже рассматривали ранее: Z3,0, Z2>1, Z1>2 и Z0,3. Можнозаметить, что эта ситуация идентична рассмотренной ранее и не дает новых реберных1-расширений. Следствие 1. Исходящая звезда, то есть направленная звезда вида Zm0,m > 1, имеет два неизоморфных минимальных реберных 1-расширения - граф K 1 m иорграф ZKm-1,0,2.Следствие 2. Входящая звезда, то есть направленная звезда вида Z0 n , n > 1,имеет два неизоморфных минимальных реберных 1-расширения - граф K 1 m и орграфZ K 0 , n - 1 , 2 .Теорему 2 легко обобщить для ориентированных звезд. Обозначим через ZKmnp, tграф, получающийся из звезды Zmn добавлением t - 1 «центральной» вершины, со-единением их между собой и центральной вершиной звезды Zm,n парами встречныхдуг. Каждая из добавленных центральных вершин соединяется m входящими, n исхо-дящими дугами и p ребрами с произвольными источниками и стоками звезды Zm,n.Теорема 3. Ориентированные звезды Zm,n,p при m> 0, n> 0 и p> 0 имеют един-ственное с точностью до изоморфизма минимальное реберное 1-расширение - звездуK1,m+n+p.Доказательство. Пусть G* -некоторое минимальное реберное 1-расширениезвезды Zm,n,p. Так как звезда Zm,n,p вкладывается в орграф G*, то в G* есть как мини-мум одна полная вершина. Рассмотрим случаи, когда полная вершина одна и более.I с л у ч а й. Предположим, что полная вершина одна, и обозначим ее через v.Повторяя рассуждения из доказательства теоремы 2, получим, что вершина v должнабыть соединена со всеми остальными вершинами парой встречных дуг. Если бы этобыло не так и вершина v была бы соединена с некоторой вершиной u только однойдугой, например (v, u), то вложение звезды Z m n p в граф G* - (v, u) было бы невозмож-но, так как ни одна вершина не будет соответствовать центральной вершине звездыZm,n,p. Граф K1 m + n + p имеет минимальное число дуг среди всех подходящих под этотслучай графов, то есть графов с одной вершиной, соединенной парой встречных дугсо всеми остальными вершинами. Легко видеть, что звезда K1,m+n+p является ребер-ным 1-расширением орзвезды Zm,n,p. Рассмотрим удаление в графе K1,m+n+p любойдуги вида (v,u), где v - центральная вершина, а u - любая другая. Вложение звездыZm n p строится следующим образом: центральная вершина звезды Zm n p соответствуетвершине v. Вершина u и m - 1 из оставшихся вершин графа K1,m+n будут соответство-вать источникам, а остальные n + p вершин - стокам и вершинам, которые соединеныс центральной вершиной парой встречных дуг. Заметим, что количество дуг в графеKi,m+n+p есть 2(m + n + p).II с л у ч а й. Предположим, что вершин, соединенных дугой с остальными вер-шинами, всего t штук и t > 1. Повторяя рассуждения из теоремы 2, получим, что цен-тральные вершины должны быть соединены между собой, что дает не менее t(t - 1)/2дуг, каждая из них - с p вершинами парой встречных дуг и с остальными m + n - t + 1вершинами по крайней мере одной дугой. Всего получаем дугt(t - 1)/2 + 2pt + t(m + n - t + 1) = t(m + n + 2p - (t - 1)/2).Эта величина принимает минимальное (по t > 1) значение при t = 2, и это будет2(m + n + p ) + p - 1. Однако при t = 2, как мы установили при исследовании случая IIв доказательстве теоремы 2, центральные вершины должны быть соединены паройвстречных дуг. Поэтому минимально возможное количество дуг по данной схеме можетбыть 2(m + n + p) + p, и при p > 0 это больше числа дуг в графе K1>m+ra+p. 2. Минимальные реберные k-расширенияОбобщим результаты двух предыдущих теорем.Теорема 4. Относительно минимальных реберных k-расширений направленныхзвезд справедливо следующее:1) при m = n = k звезда имеет минимальным реберным k-расширениемлюбой регулярный (2k + 1)-вершинный турнир, и только их;2) при m = n + 1 = k звезда Zm+1,m имеет минимальным реберным k-расширениемлюбой (2k + 2)-вершинный турнир, который получается из регулярного (2k + 1)-вершинного турнира добавлением дополнительной вершины-источника;3) при m + 1 = n = k звезда Zm,m+1 имеет минимальным реберным k-расширениемлюбой (2k + 2)-вершинный турнир, который получается из регулярного (2k + 1)-вершинного турнира добавлением дополнительной вершины-стока;4) кроме случая m = n = k, звезда при k ^ m + n имеет минимальнымреберным k-расширением графы вида ZKmi,rai)k+1, где m1 + n1 = m + n - k,max{0, m - k} ^ m1 ^ m, max{0, n - k} ^ n1 ^ m. При k > m + n звездане имеет минимальных реберных k-расширений.Доказательство. Пусть k > 1 и G* - некоторое минимальное реберное k-рас-ширение звезды Zm,n. Так как звезда вкладывается в орграф G*, то в G* естькак минимум одна вершина, соединенная дугой со всеми остальными. Обозначим че-рез p количество полных вершин; положим N = m + n. Очевидно, что p ^ m + n + 1.Удаление k любых дуг из графа G* должно оставить по крайней мере одну полнуювершину.I с л у ч а й. Если все полные вершины в графе G* соединены между собой однойдугой, то удаление такой дуги исключает две полные вершины. Поэтому количествополных вершин должно быть не менее 2 k + 1. Тогда количество дуг в таком орграфебудет не менее чем (2k + 1)k + (2k + 1)(N - 2k) = (2k + 1)N - 2k2 - k, причем 2k ^ N.II с л у ч а й. Если все полные вершины в графе G* соединены между собой паройвстречных дуг, то удаление такой пары дуг исключает две полные вершины. Поэтому,если k четно, то количество полных вершин должно быть не менее k + 1. При нечетномk = 2k1 + 1 с удалением k1 пар встречных дуг будут исключены k - 1 полных вершин.Предположим, что останется еще лишь одна полная вершина. Если она будет соедине-на с некоторой вершиной только одной дугой, то, удалив ее, мы исключим последнююполную вершину. Следовательно, эта вершина должна быть соединена с остальнымивершинами также парой встречных дуг. Более того, удалив одну такую дугу, мы по-лучим, что из единственной полной вершины либо исходит, либо входит в некоторуювершину единственная дуга. Следовательно, в звезде должен быть хотя бы одинисточник и сток. В силу произвольности выбора исключаемых вершин можно сделатьвывод, что при нечетном k, при n> 0, m> 0 и k - 1 ^ N, орграф G* может иметь kполных вершин, соединенных между собой и со всеми остальными вершинами паройвстречных дуг. Определим количество дуг в этом случае:k(k - 1) + 2(N - k + 1)k = 2Nk - k2 + k,причем k - 1 ^ N.III с л у ч а й . Если количество полных вершин в орграфе G* есть k + 1, то междусобой они должны быть соединены парой встречных дуг, но с остальными вершинамиони могут быть соединены одной дугой. Мы уже встречались с такими орграфами,например это семейства ZKmi,rai ,к+1. Минимальное количество дуг в этом случае равно(k + 1)k + (k + 1)(N - k) = N1(k + 1), причем k ^ N.Видно, что при больших значениях N количество дуг в последнем случае будетменьше, чем в случаях I и II. Определим более точные соотношения по количествудуг между этими случаями. Случаи II и III:2Nk - k2 + k ^ N(k + 1),N(k - 1) - k(k - 1) ^ 0,(N - k)(k - 1) ^ 0.При k =1 имеем равенство количества дуг. Случай II при k = 1 -это звезда K1;nиз теоремы 2. При k > 1 интерес представляет случай N ^ k. Но так как в случае IIk ^ N, то остается единственная возможность k = N. Легко видеть, что при k = Nграфы в случаях II и III изоморфны и представляют собой полный граф Kn. Такимобразом, при k > 1 случай II не представляет интереса.Случаи I и III:(2k + 1)N - 2k2 - k ^ N(k + 1),Nk - 2k2 - k ^ 0.Так как в случае I имеем ограничение 2k ^ N, то интерес представляют всего двазначения N. При N = 2k получаем, что граф, построенный по схеме I, будет иметьменьше дуг, чем граф из случая III, а при N = 2k + 1 количество дуг в случаях I и IIIбудет одинаково. Видно, что при этих значениях графы из случая I будут турнирами.Исследуем эти возможности подробнее.N = 2k. В этом случае имеем (2k + 1)-вершинный турнир. Удаляя k произвольныхдуг, соединяющих различные вершины турнира, получим граф с единственной полнойвершиной, которая соединена с каждой из остальных вершин одной дугой. Значит,чтобы звезда Zm,ra вкладывалась в получившийся граф, в эту вершину должны входитьm дуг и выходить n. В силу произвольности выбора это должно быть справедливо длявсех вершин турнира, то есть все вершины должны иметь одинаковые степени исходаи захода. Это возможно лишь при m = n = k. Таким образом, только звезда вида Zm,mможет иметь регулярный турнир минимальным реберным k-расширением при k = m.При k =1 имеем звезду Z1;1, и ее минимальным реберным 1-расширением являетсяциклическая тройка. На рис. 4 показана звезда Z2 2 и ее единственное минимальноереберное 2-расширение, построенное по описанной схеме.N = 2k + 1. В этом случае имеем (2k + 2)-вершинный турнир. Удаляя k произволь-ных дуг, соединяющих различные вершины турнира, получим граф с двумя полнымивершинами,которые соединены с каждой из остальных вершин одной дугой. Значит,чтобы звезда n вкладывалась в получившийся граф, в одну из этих вершин должнывходить m дуг и выходить n. Так как число вершин в турнире четно, то он не можетбыть регулярным и все вершины не могут иметь одинаковые полустепени исхода изахода. Следовательно, хотя бы одна вершина будет иметь полустепени исхода и захо-да, отличные от m и n. Однако такая вершина может быть только одна, потому чтоРис. 4. Звезда Z2,2 и ее единственное МР-2Рв противном случае, подбирая соответствующим образом k удаляемых дуг, мы моглибы получить орграф с двумя полными вершинами, ни одна из которых бы не имелаm входящих и n исходящих дуг. Итак, в (2k + 2)-вершинном турнире 2k + 1 вершиндолжны иметь одинаковые полустепени исхода и захода - m и n соответственно. Та-ким образом, имеем (2k + 1)m исходящих дуг, (2k + 1)n входящих и одну неучтеннуювершину, обозначим ее w. Так как число входящих и исходящих дуг должно бытьравно, а m = n, то можно сделать вывод, что либо m = n +1 и w является стоком,либо n = m + 1 и w является источником. Таким образом, только звезды вида Z m + i , mи Zm,m+1 могут иметь минимальным реберным k-расширением при k = m турнир,получающийся из регулярного (2m + 1)-вершинного турнира добавлением вершиныи дуг из нее во все вершины турнира для звезды Zm+1,m и из всех вершин турнирав добавленную для звезды Zm,m+1. При k =1 имеем звезды Z2 1 и Z1 2 и их мини-мальные реберные 1-расширения, упомянутые в п. 5 и 6 теоремы 2. Этим завершаетсяисследование случая I. Рассмотрим далее наиболее общий случай III.Кроме случая N = 2k, графы, построенные по схеме случая III, являются кандида-тами на минимальные реберные k-расширения. Убедимся, что эти графы действитель-но будут являться реберными k-расширениями. Пусть G* - произвольный граф видаZKmi,n i ,k+1, где m1 + n1 + k = m + n. Рассмотрим удаление дуг между различными пол-ными вершинами и остальными вершинами орграфа G*. Удаление одной такой дугиисключает одну полную вершину. Удаление k дуг оставит единственную полную вер-шину. Эта полная вершина будет соединена с k вершинами парой встречных дуг, с m1вершинами исходящей дугой, а с n1 вершинами входящей дугой. По предположениюзвезда Z m n должна вкладываться в получившийся орграф. Если m1 > m или n1 > n,то такое вложение будет невозможно. Аналогично, если m1 < m - k или n1 < n - k.Если же все указанные неравенства выполняются, то недостающими вершинами длясоответствия источникам и стокам звезды будут являться бывшие полные вершиныорграфа G*. Похожим образом можно рассмотреть удаления дуг между полными вер-шинами и убедиться, что графы вида ZKmi,ni,fc+1 действительно являются ребернымиk-расширениями звезды Z m n при выполнении указанных ранее ограничений. На рис. 5 показаны все минимальные реберные 2-расширения звезд Z2,3 и Z3,2.Теорема 5. Относительно минимальных реберных k-расширений ориентирован-ных звезд Z m n p справедливо следующее:1) при четном k звезда Zm,n,p имеет минимальные реберные k-расширения видаZKmi,ni,p,fc+i, и только их;2) при нечетном k, m > 0, n > 0 и (m + n - k)(k - 1) - 2p ^ 0 звезда Z m n p имеетминимальное реберное k-расширение вида + Om+n+p-k+1;3) при k ^ m + n и (m + n - k)(k - 1) - 2p ^ 0 звезда Zm,n,p имеет минимальныереберные k-расширения вида ZKmi,ni,p,k+1;Рис. 5. Звезды Z2,3 и ^3,2 и их МР-2Р: единственное в форме турнира и по одномупредставителю семейств ZK 1,2,3 и ZK2134) при k > m + n звезда не имеет минимальных реберных k-расширений.Доказательство. Пусть k > 1 и G* - некоторое минимальное реберное k-рас-ширение звезды Zm,ra)P. Так как звезда Zm,ra)P вкладывается в орграф G*, то в G* естькак минимум одна полная вершина. Обозначим через t количество полных вершин;положим N = m + n. Очевидно, что t ^ m + n +1. Удаление k любых дуг из графа G*должно оставить по крайней мере одну полную вершину.I с л у ч а й . Если все полные вершины в графе G* соединены между собой однойдугой, то удаление одной такой дуги исключает две полные вершины. Поэтому коли-чество полных вершин должно быть не менее 2k + 1. Каждая полная вершина должнабыть соединена с p вершинами парой встречных дуг, а с остальными по крайней мереодной дугой. Тогда количество дуг в таком орграфе будет не менее чем(2k + 1)k + (2k + 1)(N - 2k) + 2(2k + 1)p = (2k + 1)N - 2k2 - k + 2(2k + 1)p,причем 2 k ^ N.II с л у ч а й . Если все полные вершины в графе G* соединены между собой паройвстречных дуг, то удаление такой пары дуг исключает две полные вершины. Поэтомуесли k четно, то количество полных вершин должно быть не менее k + 1. При нечетномk = 2k1 + 1 удаление k1 пары встречных дуг исключает k - 1 полных вершин. Пред-положим, что останется еще лишь одна полная вершина. Если она будет соединенас некоторой вершиной только одной дугой, то, удалив ее, мы исключим последнююполную вершину. Следовательно, эта вершина должна быть соединена с остальнымивершинами также парой встречных дуг. Более того, удалив одну такую дугу, мы по-лучим, что из единственной полной вершины либо исходит, либо входит в некоторуювершину единственная дуга. Следовательно, в звезде должен быть хотя бы одинисточник и сток. В силу произвольности выбора исключаемых вершин можно сделатьвывод, что при нечетном k, при n> 0, m> 0 и k - 1 ^ N орграф G* может иметь kполных вершин, соединенных между собой и со всеми остальными вершинами паройвстречных дуг. Такой граф можно представить как Kk + Om+ra+P-fc+1. Определим ко-личество дуг в этом случае: k(k - 1) + 2(N - k +1 + p)k = 2Nk - k2 + k + 2pk, причемIII с л у ч а й . Если количество полных вершин в орграфе G* есть k + 1 , томежду собой они должны быть соединены парой встречных дуг, c p вершинами такжеk - 1 ^ N.парой встречных дуг, а с остальными вершинами они могут быть соединены однойдугой. Мы уже встречались с такими орграфами, например это семейства ZKmi,ni p,fc+1.Определим минимальное количество дуг в этом случае:(k + 1)k + (k + 1)(N - k) + 2(k + 1)p = N(k + 1) + 2(k + 1)p, причем k ^ N.Видно, что при больших значениях N количество дуг в последнем случае будетминимальным. Определим более точные соотношения по количеству дуг между этимислучаями. Случаи II и III:2Nk - k2 + k + 2pk ^ N(k + 1) + 2(k + 1)p,N(k - 1) - k(k - 1) - 2p ^ 0,(N - k)(k - 1) - 2p ^ 0.При k = 1 в теореме 3 мы получили, что графы из случая II всегда имеют меньшеечисло дуг, чем графы из случая III. При k > 1 ситуация представляется более сложной:при значениях N, много больших, чем k и p, меньше дуг будет в схеме III, а принечетных значениях k, близких к N или больших, чем p, меньше дуг будет в схеме II.Случаи I и III:(2k + 1)N - 2k2 - k + 2(2k + 1)p ^ N(k + 1) + 2(k + 1)p,Nk - 2k2 - k + 2kp ^ 0.Так как в случае I имеем ограничение 2k ^ N, то при p > 0 у графов из случая Iбудет всегда больше дуг, чем у графов из случая III. Рассмотрим для примера поиск минимальных реберных 3-расширений звездыZ2 2 1 . Посчитаем величину (m + n - k)(k - 1) - 2p и получим(2 + 2 - 3)(3 - 1) - 2 * 1 = 0.Таким образом, по теореме 5 получаем, что звезда Z2 21 будет иметь минимальныереберные 3-расширения двух видов: граф K3 + O3 и графы вида ZK1,0,1,4 и ZK0,1,1,4.Все эти графы содержат по 24 дуги. На рис. 6 показаны все минимальные реберные3-расширения звезды Z2,2,1. Для облегчения визуализации расширений пара встречныхдуг заменена неориентированным ребром.Рис. 6. Звезда Z2,2,1 и все ее МР-3РЗаключениеВ данной работе дано аналитическое решение задачи описания минимальных ре-берных k-расширений для направленных и ориентированных звезд. Ранее удалось най-ти полное решение задачи описания минимальных вершинных k-расширений для на-правленных звезд, а также минимальных вершинных и реберных k-расширений длянеориентированных звезд. Полученные результаты расширяют класс графов, для ко-торых удалось найти полное решение рассматриваемой задачи.

Ключевые слова

fault tolerance, minimal edge extension, star graph, звездные графы, отказоустойчивость, оптимальная отказоустойчивая реализация, минимальное расширение

Авторы

ФИООрганизацияДополнительноE-mail
Абросимов Михаил БорисовичСаратовский государственный университет им. Н. Г. Чернышевскогодоцент, кандидат физико-математическихнаук, доцентmic@rambler.ru
Всего: 1

Ссылки

Абросимов М. Б. Минимальные расширения транзитивных турниров // Вестник Томского госуниверситета. Приложение. 2006. № 17. С. 187-190.
Абросимов М. Б. Минимальные расширения неориентированных звезд // Теоретические проблемы информатики и ее приложений. Саратов: СГУ, 2006. Вып. 7. С. 3-5.
Абросимов М. Б. Минимальные k-расширения предполных графов // Изв. вузов. Математика. 2003. №6(493). С. 3-11.
Абросимов М. Б. О сложности некоторых задач, связанных с расширениями графов // Матем. заметки. 2010. №5(88). С. 643-650.
Sung T. Y., Lin C. Y., Chuang Y. C., and Hsu L. H. Fault tolerant token ring em-bedding in double loop networks // Inform. Process. Lett. 1998. V. 66. P. 201-207.
Киреева А. В. Отказоустойчивость в функциональных графах // Упорядоченные множества и решетки. Саратов, 1995. Вып. 11. С. 32-38.
Harary F. and Hayes J. P. Node fault tolerance in graphs // Networks. 1996. V. 27. P. 19-23.
Harary F. and Hayes J. P. Edge fault tolerance in graphs // Networks. 1993. V. 23. P. 135-142.
Hayes J. P. A graph model for fault-tolerant computing system // IEEE Trans. Comput. 1976. V.C25. No. 9. P. 875-884.
Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. М.: Наука, 1997.
 Минимальные реберные расширения направленных и ориен-тированных звезд | ПДМ. 2011. № 2(12).

Минимальные реберные расширения направленных и ориен-тированных звезд | ПДМ. 2011. № 2(12).

Полнотекстовая версия