Апериодичан граф
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a2/Aperiodic-graph.svg/220px-Aperiodic-graph.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/20/Period-3-graph.svg/220px-Period-3-graph.svg.png)
У области математичке теорије графова, усмерен граф је апериодичан ако не постоји цео број к > 1 који дели дужину сваког циклуса графа. Еквивалентно томе, граф је апериодичан ако највећи заједнички делилац дужине његових циклуса износи један. Највећи заједнички делилац графа Г представља период графа Г.
Графови који не могу бити апериодични[уреди | уреди извор]
У сваком бипартитивном усмереном графу, циклуси имају дужину дељиву са два, дакле ниједан такав граф не може бити апериодичан. У сваком усмереном ацикличном графу, познато је да свако к дели све циклусе (јер не постоји усмерених циклуса за дељење), па ниједан ациклични граф није апериодични. У усмереном графу који има само један циклус, к ће бити дужина тог циклуса. Из тога следи да ни такав граф не може бити апериодичан.
Тестирање апериодичности[уреди | уреди извор]
Претпоставља се да је Г чврсто повезан граф и да к дели дужине свих циклуса у Г. Размотрити резултат обављања претраге у дубину графа Г, са почетком у било ком чвору и доделу сваког чвора V до одређеног Ви, где је и дужина пута претраге у дубину од корена до чвора V. Може се показати да ова подела у сетове Ви има својство да свака ивица у графу иде из скупа Ви у други сет V(и+1) мод к. Насупрот томе, ако партиција са тим постоји код повезаног графа Г, к мора делити дужине свих циклуса графа Г.
Период повезаног графа Г можемо пронаћи пратећи следеће кораке:
- Претражимо у дубину граф Г
- За свако е у Г које повезује чворове нивоа и стабла претраге у дубину са чворовима нивоа ј, нека је ке = ј - и - 1.
- Израчунати највећи заједнички делилац сета бројева ке.
Граф је апериодичан ако и само ако период израчунат на овај начин износи један.
Ако Г није строго повезан граф, можемо на сличан начин извести претходна три корака тако што за сваку строго повезану компоненту графа Г игноришемо ивице које пролазе из једне чврсто повезане компоненте у другу.
Џарвис и Схиер описују веома сличан алгоритам користећи претрагу у ширину уместо претраге у дубину. Предност претраге у дубину је јака анализа графа, која може бити укључена у исту претрагу.
Апликације[уреди | уреди извор]
У чврсто повезаном графу, ако су на чворовима дефинисани ланци Маркова у којима је вероватноћа преласка из в на w различита од нула ако и само ако постоји ивица од в до w, онда је тај ланац апериодичан ако и само ако је и граф апериодичан. Ланци Маркова који су у свим стањима рекурентни имају чврсто повезани граф транзиције стања, а ланац Маркова је апериодичан ако и само ако је овај граф апериодичан. Дакле, апериодичност графова је користан концепт у анализи ланаца Маркова.
Апериодичност је такође битна код решавања проблема бојања пута. Према решењу овог проблема (Трахтман 2009), чврсто повезан усмерен граф у којем сви чворови имају исти излазни степен, има синхрозабилну грану бојања ако и само ако је апериодичан.
Литература[уреди | уреди извор]
- Јарвис, Ј. П.; Схиер, D. Р. (1996), "Грапх-тхеоретиц аналyсис оф фините Марков цхаинс", ин Схиер, D. Р.; Wаллениус, К. Т., Апплиед Матхематицал Моделинг: А Мултидисциплинарy Аппроацх, ЦРЦ Пресс.
- Трахтман, Аврахам Н. (2009), "Тхе роад цолоринг проблем", Исраел Јоурнал оф Матхематицс 172.