Апериодичан граф

У области математичке теорије графова, усмерен граф је апериодичан ако не постоји цео број к > 1 који дели дужину сваког циклуса графа. Еквивалентно томе, граф је апериодичан ако највећи заједнички делилац дужине његових циклуса износи један. Највећи заједнички делилац графа Г представља период графа Г.

Апериодични граф. Дужине циклуса у овом графу износе 5 и 6, према томе не постоји к>1 који дели све дужине циклуса

Графови који не могу бити апериодични

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

Тестирање апериодичности

Претпоставља се да је Г чврсто повезан граф и да к дели дужине свих циклуса у Г. Размотрити резултат обављања претраге у дубину графа Г, са почетком у било ком чвору и доделу сваког чвора V до одређеног Ви, где је и дужина пута претраге у дубину од корена до чвора V. Може се показати да ова подела у сетове Ви има својство да свака ивица у графу иде из скупа Ви у други сет V(и+1) мод к. Насупрот томе, ако партиција са тим постоји код повезаног графа Г, к мора делити дужине свих циклуса графа Г.

Период повезаног графа Г можемо пронаћи пратећи следеће кораке:

Претражимо у дубину граф Г
За свако е у Г које повезује чворове нивоа и стабла претраге у дубину са чворовима нивоа ј, нека је к_е = ј - и - 1.
Израчунати највећи заједнички делилац сета бројева к_е.

Граф је апериодичан ако и само ако период израчунат на овај начин износи један.

Ако Г није строго повезан граф, можемо на сличан начин извести претходна три корака тако што за сваку строго повезану компоненту графа Г игноришемо ивице које пролазе из једне чврсто повезане компоненте у другу.

Џарвис и Схиер описују веома сличан алгоритам користећи претрагу у ширину уместо претраге у дубину. Предност претраге у дубину је јака анализа графа, која може бити укључена у исту претрагу.

Апликације

У чврсто повезаном графу, ако су на чворовима дефинисани ланци Маркова у којима је вероватноћа преласка из в на w различита од нула ако и само ако постоји ивица од в до w, онда је тај ланац апериодичан ако и само ако је и граф апериодичан. Ланци Маркова који су у свим стањима рекурентни имају чврсто повезани граф транзиције стања, а ланац Маркова је апериодичан ако и само ако је овај граф апериодичан. Дакле, апериодичност графова је користан концепт у анализи ланаца Маркова.

Апериодичност је такође битна код решавања проблема бојања пута. Према решењу овог проблема (Трахтман 2009), чврсто повезан усмерен граф у којем сви чворови имају исти излазни степен, има синхрозабилну грану бојања ако и само ако је апериодичан.

Литература

Јарвис, Ј. П.; Схиер, D. Р. (1996), "Грапх-тхеоретиц аналyсис оф фините Марков цхаинс", ин Схиер, D. Р.; Wаллениус, К. Т., Апплиед Матхематицал Моделинг: А Мултидисциплинарy Аппроацх, ЦРЦ Пресс.
Трахтман, Аврахам Н. (2009), "Тхе роад цолоринг проблем", Исраел Јоурнал оф Матхематицс 172.