ациклични графика
За насочено графика G може да се конструира насочено графика G, чиито върхове са множество лист G. Две групи от лист L и L2 са свързани ориентирани ръб (L (, L2) в G ЕПСО са ориентирани ръбове от L до L% в G, Тази графика се нарича лист състав графика G. G е ациклична графика. тъй като всеки цикъл ориентирани би дало насочено цикъл в G, минаваща през множество листове. [46]
Под формата на (8.52) (8.53) представлява известен проблем на най-късата обхващаща дървото в ненасочена и насочено графика. Сложността на тези алгоритми е по-малко от O (n3) - броят на върховете. Проблемът е формулиран, както следва: даден претеглена ациклични графика. Нейната нарязани, на първо място в V, генерирани от подмножество на подмножество на дъги, които произхождат от V, но не са включени в V. е необходимо да се намери максимален набор от несвързани дъги от съкращения. [47]
Обикновено, рамки са организирани в йерархия атенюиран (или heterarchies), в която рамки са разположени на мрежата долу, могат да наследи стойности от слотове на различни рамки, поставени по-горе. Heterarchy - заплетена йерархия, т.е. ациклични графика. в която възли могат да имат повече от един прекурсор. [48]
Ако, например, пътека P съдържа пет ребра, с общо тегло от 24 и път P - три ребра, с общо тегло от 36, пътя Р се счита за по-кратък. Графика или диграфа е свързан ако всяка двойка възлови точки може да бъде свързан с най-малко един път. Цикъл - път, който започва и завършва в същото връх. В ациклени графиката или диграфът цикли на разположение. А свързан граф се нарича ацикличен (rootlessness) дърво. Неизкоренени дървовидна структура е същата като тази на дървото, само че не е избрана корен. Въпреки това, всеки връх неизкоренени дърво може да служи като своя корен. [49]
За насочено графика G може да се конструира насочено графика G, чиито върхове са множество листа лист G. два комплекта LI и Z-2 са свързани ориентирани ръб (L4, L2) на G, ако има ребра, ориентирани от Lt на L, в тази графика G. наречен лист състав графика G. G е ациклична графика. тъй като всеки ориентирана цикъл би дало насочено цикъл в G, преминавайки през няколко листа. [50]
И в двата случая, модел на изображението е представен като графика, така че върховете представляват сегментите или елементи на сегмента и ръбовете представляват връзки между тях. Връзката може да бъде от тип предшественик - потомък (в дървото), или може да експресира свързаност еквивалентни обекти. И в двата случая, връзката не е рефлексивен. Образът на фиг. 3.3, и може да бъде представена като дърво, както е показано на фиг. 3.3 6 има структура, която е по-често ациклични графика. [51]
Страници: 1 2 3 4
Сподели този линк:
Свързани статии