Транзитивна редукција

У математици, транзитивна редукција усмереног графа је граф са неколико грана колико је могуће тако да имају исти однос досега као дати граф. Подједнако, дати граф и његова транзитивна редукција требало би да имају иста транзитивна затворења, и њихове транзитивне редукције би требало да имају неколико грана колико је то могуће међу свим графовима ових особина. Транзитивне редукције је увео Ахо, Гареy & Уллман 1972, који је увео танке границе при њиховом сложеном рачунарском конструисању.

Ако је дати граф коначан усмерен ацикличан гараф, његова транзитивна редукција је јединствена, и подграф је датог графа. Међутим јединственост није гаранција за цикличне графове, и за бесконачне графове постојање уопште није ни гарантовано.Блиско повезани концепти минималног еквивалентног графа је подграф датог графа који има исту релацију досега и што је могуће мање коначне усмерене ацикличне графове, минимални еквивалентни граф је исти као и транзитивна редукција. Међутим, за цикличне графове, минимални еквивалентан граф се НП-тешко конструише, док се транзитивна редукција и даље може конструисати у полиномијалном времену.Транзитивна редукција се такође може дефинисати за абстрактније бинарне релације скупова, претстављањем парова релација као грана графа.

Код директних ацикличних графова

Транзитивна редукција коначног усмереног графа Г је граф са сто је могуће мање грана који има исту релацију досега као оригиналан граф. То јест ако постоји пут од чвора x до чвора y у графу Г, мора постојати и пут од x ка y и у транзитивној редукцији Г-а, и обрнуто. Слика која следи нам приказује граф који одговара не-транзитивној бинарној релацији (лево) и својој транзитивној редукцији (десно).

Транзитивна редукција коначног усмереног ацикличног графа Г је је јединствена, и састоји се од грана графа Г које формирају једини пут измедју својих крајњих тачака.Конкретно, то је увек подграф датог графа.Због овога, транзитивна редукција одговара минималном еквивалентном графу у овом случају.

У математичкој теорији бинарних релација, свака релација Р на скупу X може бити протумачена као усмерени граф који има скуп X као своје чворове и има грану xy за сваки уређени пар елемената који су повезани у Р.Конкретно, ова метода дозвољава да парцијално уређене скупове посматрамо као усмерене ацикличне графове, где постоји грана xy у графу кад год постоји релација поретка 'x < y између датих парова елемената парцијалног уређења.Када се употреби операција транзитивне редукције на усмереном ациклином графу који је конструисан на овај начин, добија се covering релација парцијалног уређења, која се често даје као визуелни израз путем Хассе диаграма.

Код цикличних графова

Код коначног графа који мозда има циклус,транзитивна редукција није јединствено дефинисана:мозда постоји више од једног графа са истим скупом чворова као и минималим бројем грана и има исту релацију досега као дати граф.Поред тога,постоји и случај када нити један од ових минималних графова није подграф датог графа.Ипак,исправно је да минималне графове са истим релацијам досега обележавамо као дати граф Г.Ако је Г произвољан усмерен граф, и ако је Х граф са минималним могућим бројем грана који има исту релацију досега као Г, онда се Х састоји од:

• Усмереног циклуса за сваку чврсто повезану компоненту из Г, која спаја цворове у ову компоненту
• Гране xy за сваку грану XY транзитивне редукције кондензације од Г,где су X и Y две чврсто повезане компоненте од Г које су спојене гранама у кондензацији,x је било који чвор компоненте X, а y је било који чвор компоненте Y.Кондензација од Г је усмрен ацикличан граф који има чвор за сваку чврсто повезану компоненту из Г.Посебно, зато што је ацикличан, његова транзитивна редукција се дефинише као у претходном делу.

Укупан број грана у овом типу транзитивне редукције је једнак броју чворова у транзитивној редукцији кондензације, плус број чворова у нетривијалном чврсто повезаним компонентама (компоненте које се састоје од више од једног чвора).

Гране транзитивне редукције која одговара кондензацији грана се увек може одабрати да буде подграф датог графа Г.Међутим,циклис унутар сваке чврсто повезане компоненте се може изабрати да буде подграф графа Г једино ако та компонента има Хамилтонов циклус, нешто сто није увек тачно, и тешко се проверава. Због ове потескоће, НП је тешко наћи најмањи подграф датоф графа Г са истим досегом (минимални еквивалентни граф).

Сложеност израчунавања

Како је Ахи ет ал. показао, када се временска сложеност графовских алгоритама мери функцијом по броју н, броју чворова графа, а не по броју грана, транзитивно затворење и транзитивна редукција имају исту сложеност. Већ је показано да транзитивно затворење и множење Логичких матрица величине н × н имају исту сложеност, па према томе и транзитивна редукција припада истој класи.Најбрзи познати алгоритам за множење матрица има сложеност О(н^2.3727) и транзитивниа редукција има исту ову сложеност.

Да би доказали да је транзитивна редукција лака као транзитивно затворење , Ахо ет ал. је од датог усмереног ацикличног графа Г конструисао други граф Х, у којем је сваки чвор из Г замењен путем од три чвора, и свака грана графа Г одговара грани графа Х која спаја одговарајуће средње чворове ових путева.Поред тога, у графу Х, Ахо ет ал. додаје грану из сваког почетка пута у сваки крај пута. У транзитивној редукцији графа Х, постоји грана од од почетка пута у до краја пута в ако и само ако грана ув не припада транзитивном затворењу графа Г.Дакле, ако се транзитивна редукција графа Х мозе ефикасно израчунати, транзитивно затворење графа Г се мозе прочитати директно одатле.

Да би доказао да је транзитивна редукција исте лакоће као и транзитивно затворење, Ахо ет ал. се ослања на већ познату еквиваленцију множења Логичких матрица.Нека А буде матрица суседства датог графа, а Б матрица суседства транзитивног затварања(која се израцунава помоћу било ког стандардног алгоритма транзитивног завршетка).Затим, грана ув припада транзитивној редукцији ако и само ако постоји не-нула улаз у реду у и колони в матрице А, и не постоји не-нула улаз на истим позицијама матрице производа АБ.У овој конструкцији, не-нула елементи матрице АБ представљају парове чворова повезаних путевима дужине веће или једнаке двојци.

Када их меримо у на основу броја чворова н и броја грана м код усмерених ацикличних графова, транзитивна редукција се израчунава у временској сложености О (нм), сто је гарантовано брже од метода множења матрица код ретких графова. Да би смо то урадили, прикупљамо гране (у,в) тако да је растојање најдужег пута од у до в један, израчунавајуци та растојања, трагамо у линеарном времену за могућим почетним чвром ,у. Ова временска граница од О (нм) се поклапа са комплексношћу конструисања транзитивног затворења коришцењем претраживања у дубину или претраживања у ширину за проналажење чворова досежних из било ког почетног чвора, тако да опет помоћу ових претпоставки транзитивна редукција се може наћи за исти временски период.

Референце

• Ахо, А. V.; Гареy, M. Р.; Уллман, Ј. D. (1972), „Тхе транситиве редуцтион оф а дирецтед грапх”, СИАМ Јоурнал он Цомпутинг, 1 (2): 131—137, МР 0306032, дои:10.1137/0201008 .
• Моyлес, Деннис M.; Тхомпсон, Гералд L. (1969), „Ан Алгоритхм фор Финдинг а Минимум Еqуивалент Грапх оф а Диграпх”, Јоурнал оф тхе АЦМ, 16 (3): 455—460, дои:10.1145/321526.321534 .
• Wиллиамс, Виргиниа Вассилевска (2012), „Мултиплyинг матрицес фастер тхан Цопперсмитх–Wиноград”, Проц. 44тх АЦМ Сyмпосиум он Тхеорy оф Цомпутинг (СТОЦ '12), стр. 887—898, дои:10.1145/2213977.2214056 .

Спољашње везе

• Wеисстеин, Ериц W. „Транситиве Редуцтион”. МатхWорлд.