Бағытталған графтардың артық қабырғаларын жою арқылы қысқартуы
Transitive reduction
Графтар теориясы: Бағытталған графтардың транзитивті азайтуы – қабырғалар санын азайтып, байланыс қатынасын сақтайтын өңдеу. Алгоритмдер мен күрделігі туралы ақпарат.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Бағытталған графиктің көшірмесі, артық қабырғалары алынып тасталған.
Copy of a directed graph with redundant edges removed
Графтар теориясының математикалық саласында, D бағытталған графигінің транзитивті қысқартуы – бірдей төбелері және мүмкіндігінше аз қабырғалары бар басқа бағытталған график, сондықтан v, w төбелерінің кез келген жұбы үшін D-де v-ден w-ға бағытталған жол бар, егер және ғана егер мұндай жол қысқартуда да болса. Транзитивті қысқартулар алғаш рет енгізілді, олар оларды құрудың есептеу күрделілігіне қатаң шектеулер қойды. Техникалық тұрғыдан алғанда, қысқарту – D сияқты қолжетімділік қатынасына ие бағытталған график. Д және оның транзитивті қысқартуы бір-бірімен бірдей транзитивті жабылуға ие болуы керек, ал D транзитивті қысқартуы осы қасиетке ие барлық графиктердің арасында ең аз қабырғаға ие болуы керек. Шешілген бағытталған ациклді графтың (бағытталған циклдары жоқ графтың) транзитивті қысқартуы бірегей және берілген графтың ішкі графигі болып табылады. Дегенмен, (бағытталған) циклдары бар графтар үшін бірегейлік сақталмайды, ал шексіз графтар үшін тіпті болуы да кепілденбеді. Тығыз байланысты ұғым – ең аз эквивалентті граф, ол D-нің қолжетімділік қатынасымен бірдей және мүмкіндігінше аз қабырғалары бар ішкі графигі. Айырмашылығы – транзитивті қысқарту міндетті түрде D-нің ішкі графигі болуы керек емес. Шешілген бағытталған ациклді графтар үшін ең аз эквивалентті граф транзитивті қысқартумен бірдей. Алайда, циклдары болуы мүмкін графтар үшін ең аз эквивалентті графтарды құру NP-қиын, ал транзитивті қысқартуларды полиномиалдық уақытта құрастыруға болады. Транзитивті қысқартуды жиынтағы абстрактілі екілік қатынас үшін, қатынастың жұптарын бағытталған графиктегі доғалар ретінде қарастыру арқылы анықтауға болады.
In the mathematical field of graph theory, a transitive reduction of a directed graph D is another directed graph with the same vertices and as few edges as possible, such that for all pairs of vertices v, w a (directed) path from v to w in D exists if and only if such a path exists in the reduction. Transitive reductions were introduced by , who provided tight bounds on the computational complexity of constructing them. More technically, the reduction is a directed graph that has the same reachability relation as D. Equivalently, D and its transitive reduction should have the same transitive closure as each other, and the transitive reduction of D should have as few edges as possible among all graphs with that property. The transitive reduction of a finite directed acyclic graph (a directed graph without directed cycles) is unique and is a subgraph of the given graph. However, uniqueness fails for graphs with (directed) cycles, and for infinite graphs not even existence is guaranteed. The closely related concept of a minimum equivalent graph is a subgraph of D that has the same reachability relation and as few edges as possible. The difference is that a transitive reduction does not have to be a subgraph of D. For finite directed acyclic graphs, the minimum equivalent graph is the same as the transitive reduction. However, for graphs that may contain cycles, minimum equivalent graphs are NP hard to construct, while transitive reductions can be constructed in polynomial time. Transitive reduction can be defined for an abstract binary relation on a set, by interpreting the pairs of the relation as arcs in a directed graph.
Бағытталған ациклді графиктерде
Түпкіленген бағытталған G графигінің транзитивті редукциясы – бастапқы графикпен бірдей қолжетімділік қатынасын қамтитын, мүмкіндігінше аз жиектері бар график. Яғни, егер G графигінде x төбесінен y төбесіне жол болса, онда G графигінің транзитивті редукциясында да x-тен y-ге жол болуы керек, және керісінше. Атап айтқанда, егер x-тен y-ге және y-ден z-ге жолдар болса, онда y төбесін қамтымайтын x-тен z-ге жол болуы мүмкін емес. x, y және z үшін транзитивтілік мынаны білдіреді: егер x < y және y < z болса, онда x < z. Егер y-ден z-ге кез келген жолға x-тен y-ге жол сәйкес келсе, онда x-тен z-ге жол бар; алайда, x-тен y-ге және x-тен z-ге кез келген жолға y-ден z-ге жол сәйкес келеді деп айтуға болмайды, сондықтан транзитивті редукция кезінде x және z төбелері арасындағы кез келген жиек алынып тасталады, себебі олар транзитивті емес жолдарды көрсетеді. Келесі суретте транзитивті емес екілік қатынасқа (сол жақта) және оның транзитивті редукциясына (оң жақта) сәйкес келетін графиктердің суреттері көрсетілген. Түпкіленген бағытталған ациклді график G-дің транзитивті редукциясы бірегей болып табылады және оның шеттері төбелері арасындағы жалғыз жолды құрайды. Әсіресе, ол әрқашан берілген графиктің енетін ішкі графигі болып табылады. Осы себепті, транзитивті редукция осы жағдайда ең төменгі эквиваленттік графикпен сәйкес келеді. Бинарлық қатынастардың математикалық теориясында, X жиынындағы кез келген R қатынасын X жиыны төбелер жиыны ретінде және R қатынасында байланысты элементтердің әрбір реттелген жұбы үшін xy доғасы бар бағытталған график ретінде қарастыруға болады. Атап айтқанда, бұл әдіс жартылай реттелген жиындарды бағытталған ациклді графиктер ретінде қайта қарастыруға мүмкіндік береді, онда егер жартылай реттік элементтердің берілген жұбы арасында x < y қатынасы болса, онда графикте xy доғасы болады. Осылай құрылған бағытталған ациклді графикқа транзитивті редукция операциясы қолданылған кезде, ол жартылай реттіктің жабылатын қатынасын тудырады, ол көбінесе Хассе диаграммасы арқылы визуализацияланады. Транзитивті редукция желілер арасындағы құрылымдық айырмашылықтарды анықтау үшін бағытталған ациклді графиктер түрінде ұсынылған желілерде (мысалы, сілтеме графиктері немесе сілтеме желілері) қолданылған.
The transitive reduction of a finite directed graph G is a graph with the fewest possible edges that has the same reachability relation as the original graph. That is, if there is a path from a vertex x to a vertex y in graph G, there must also be a path from x to y in the transitive reduction of G, and vice versa. Specifically, if there is some path from x to y, and another from y to z, then there may be no path from x to z which does not include y. Transitivity for x, y, and z means that if x < y and y < z, then x < z. If for any path from y to z there is a path x to y, then there is a path x to z; however, it is not true that for any paths x to y and x to z that there is a path y to z, and therefore any edge between vertices x and z are excluded under a transitive reduction, as they represent walks which are not transitive. The following image displays drawings of graphs corresponding to a non transitive binary relation (on the left) and its transitive reduction (on the right). The transitive reduction of a finite directed acyclic graph G is unique, and consists of the edges of G that form the only path between their endpoints. In particular, it is always a spanning subgraph of the given graph. For this reason, the transitive reduction coincides with the minimum equivalent graph in this case. In the mathematical theory of binary relations, any relation R on a set X may be thought of as a directed graph that has the set X as its vertex set and that has an arc xy for every ordered pair of elements that are related in R. In particular, this method lets partially ordered sets be reinterpreted as directed acyclic graphs, in which there is an arc xy in the graph whenever there is an order relation x < y between the given pair of elements of the partial order. When the transitive reduction operation is applied to a directed acyclic graph that has been constructed in this way, it generates the covering relation of the partial order, which is frequently given visual expression by means of a Hasse diagram. Transitive reduction has been used on networks which can be represented as directed acyclic graphs (e. g. citation graphs or citation networks) to reveal structural differences between networks.
Жабылуды пайдалану арқылы азайтуды есептеу
Транзитивті азайту транзитивті жабу сияқты оңай екенін дәлелдеу үшін Aho және авторлар бұрыннан белгілі болған буледік матрица көбейтумен эквиваленттілікке сүйенеді. Олар A-ны берілген бағытталған ациклді графтың жабыстық матрицасы, ал B-ны оның транзитивті жабылуының жабыстық матрицасы (кез келген стандартты транзитивті жабылу алгоритмін қолдану арқылы есептеледі) деп белгілейді. Содан кейін uv қабырғасы транзитивті азайтуға жатады, егер және тек қана A матрицасының u-шы қатарында және v-шы бағанында нөлден өзге элемент болса, ал AB матрицалық көбейтілімінің сол позициясында нөл болса. Бұл құрылымда AB матрицасының нөлден өзге элементтері екі немесе одан ұзын жолдармен байланысқан төбелер жұптарын көрсетеді.
To prove that transitive reduction is as easy as transitive closure, Aho et al. rely on the already known equivalence with Boolean matrix multiplication. They let A be the adjacency matrix of the given directed acyclic graph, and B be the adjacency matrix of its transitive closure (computed using any standard transitive closure algorithm). Then an edge uv belongs to the transitive reduction if and only if there is a nonzero entry in row u and column v of matrix A, and there is a zero entry in the same position of the matrix product AB. In this construction, the nonzero elements of the matrix AB represent pairs of vertices connected by paths of length two or more.
Ақыртылуды азайтуды пайдалану арқылы есептеу
Транзитивті азайту транзитивті жабумен бірдей қиын екенін көрсету үшін, Ахо және авторлар берілген бағытталған ациклді G графынан H графы құрастырады, онда G-нің әрбір төбесі үш төбеден тұратын жолмен алмастырылады, ал G-нің әрбір қабырғасы H-дегі осы жолдардың сәйкес ортаңғы төбелерін байланыстыратын қабырғаға сәйкес келеді. Бұдан өзге, H графында Ахо және авторлар әрбір жолдың басталуынан соңына дейін қабырға қосады. H транзитивті азайтуында, u жолының басталуынан v жолының соңына дейін қабырға бар, егер және тек қана егер uv қабырғасы G транзитивті жабылуына жатпаса. Сондықтан, егер H транзитивті азайтуын тиімді есептеуге болады, онда G транзитивті жабылуын тікелей одан анықтауға болады.
To prove that transitive reduction is as hard as transitive closure, Aho et al. construct from a given directed acyclic graph G another graph H, in which each vertex of G is replaced by a path of three vertices, and each edge of G corresponds to an edge in H connecting the corresponding middle vertices of these paths. In addition, in the graph H, Aho et al. add an edge from every path start to every path end. In the transitive reduction of H, there is an edge from the path start for u to the path end for v, if and only if edge uv does not belong to the transitive closure of G. Therefore, if the transitive reduction of H can be computed efficiently, the transitive closure of G can be read off directly from it.
Кескілікті шамалы графиктерде есептеу
Бағытталған ациклдік графтың нүктелер саны n және қабырғалар саны m бойынша өлшенгенде, транзитивті азайтулар O(nm) уақытында табылуы мүмкін, бұл сирек графтар үшін матрицалық көбейту әдістерінен жылдам болуы мүмкін. Мұны істеу үшін, берілген бағытталған ациклдік графтағы әр мүмкін бастапқы нүкте үшін сызықтық уақытта ең ұзын жол алгоритмін қолданыңыз. Есептелген ең ұзын жолдардан тек ұзындығы бірге тең (бір қабырғалы) жолдарды қалдырыңыз; яғни, u-ден v-ге басқа жол жоқ болған қабырғаларды (u, v) қалдырыңыз. Бұл O(nm) уақыт шегі тереңдікке бірінші іздеу немесе ендікке бірінші іздеуді пайдаланып, кез келген бастапқы нүктеден қол жетімді нүктелерді табу арқылы транзитивті жабылуларды құрудың күрделілігімен сәйкес келеді, сондықтан осы шарттар бойынша транзитивті жабылулар мен транзитивті азайтуларды бірдей уақытта табуға болады.
When measured both in terms of the number n of vertices and the number m of edges in a directed acyclic graph, transitive reductions can also be found in time O(nm), a bound that may be faster than the matrix multiplication methods for sparse graphs. To do so, apply a linear time longest path algorithm in the given directed acyclic graph, for each possible choice of starting vertex. From the computed longest paths, keep only those of length one (single edge); in other words, keep those edges (u,v) for which there exists no other path from u to v. This O(nm) time bound matches the complexity of constructing transitive closures by using depth first search or breadth first search to find the vertices reachable from every choice of starting vertex, so again with these assumptions transitive closures and transitive reductions can be found in the same amount of time.