Графтарда қабырғаны жою және түйіндерді біріктіру. Граф минорлары теориясындағы негізгі операция – қабырғаны қысқарту, түйіндерді біріктіру және графты өзгерту.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Графтың жиегін жою және түйіндерін біріктіру
Deleting a graph edge and merging its nodes
Графтар теориясында, жиектерді қысқарту – бұл графтан жиекті алып тастап, оның бұрын байланыстырған екі түйінін бірге біріктіру операциясы. Жиектерді қысқарту графтардың кіші элементтері теориясындағы негізгі операция болып табылады. Түйіннің біріктірілуі – бұл операцияның шектеусіз азат түрі.
In graph theory, an edge contraction is an operation that removes an edge from a graph while simultaneously merging the two vertices that it previously joined. Edge contraction is a fundamental operation in the theory of graph minors. Vertex identification is a less restrictive form of this operation.
Анықтама
Бүйірдің жиырылуы нақты бір бүйірге қатысты жүзеге асырылады. Бүйір алынып тасталады және оның екі жанасқан төбесі, және , жаңа төбеге біріктіріледі, мұнда оларға жанасқан бүйірлер жаңа төбеге жанасқан бүйірлерге сәйкес келеді. Көбінесе, операция шеттер жиынтығында әрбір шетті жиырып (кез келген ретпен) орындалуы мүмкін. Соның нәтижесінде алынған граф кейде былай жазылады (бұл шетті жоюды білдіреді). Төменде көрсетілгендей, бүйірді жиыру операциясы бастапқы граф қарапайым граф болған жағдайда да көптеген шеттері бар графқа әкелуі мүмкін. Дегенмен, кейбір авторлар көптеген шеттердің пайда болуына жол бермейді, сондықтан қарапайым графтарда орындалған бүйірді жиыру әрқашан қарапайым графтарды тудырады.
The edge contraction operation occurs relative to a particular edge, The edge is removed and its two incident vertices, and , are merged into a new vertex , where the edges incident to each correspond to an edge incident to either or More generally, the operation may be performed on a set of edges by contracting each edge (in any order). The resulting graph is sometimes written as (Contrast this with , which means removing the edge .) As defined below, an edge contraction operation may result in a graph with multiple edges even if the original graph was a simple graph. However, some authors disallow the creation of multiple edges, so that edge contractions performed on simple graphs always produce simple graphs.
Ресми анықтама
Кез келген қабырғасы бар графты (немесе бағытталған графты) қарастырайық, онда . болып табылатын функцияны қарастырайық, бұл функция графтың әр төбесін өзіне, ал қалғандарын жаңа төбеге бейнелейді. графын қысқарту нәтижесінде жаңа граф пайда болады, мұнда , , және кез келген үшін , егер және тек қана сәйкес қабырғасы графында төбесіне жанасқан болса, төбесіне жанасады.
Let be a graph (or directed graph) containing an edge with Let be a function that maps every vertex in to itself, and otherwise, maps it to a new vertex The contraction of results in a new graph , where ), , and for every , is incident to an edge if and only if, the corresponding edge, is incident to in .
Бағананы анықтау
Төбелерді идентификациялау (кейде төбелерді жиыру деп аталады) жиырудың тек қана ортақ қабырғасы бар төбелерде ғана жүруі керек деген шектеуді жояды. (Осылайша, қабырғаны жиыру – төбелерді идентификациялаудың ерекше жағдайы.) Операция графтың кез келген жұп (немесе ішкі жиын) төбелерінде жүргізілуі мүмкін. Жиырылатын екі төбе арасындағы қабырғалар кейде алынып тасталады. Егер және – бөлек компоненттердің төбелері болса, онда біз жаңа графты құруға болады, мұнда және төбелері графтың ішінде жаңа төбе ретінде анықталады. Жалпы алғанда, төбелер жиынтығының бөлінісі берілген жағдайда, бөліністегі төбелерді идентификациялауға болады; нәтижедегі граф – бөлшек граф деп аталады.
Vertex identification (sometimes called vertex contraction) removes the restriction that the contraction must occur over vertices sharing an incident edge. (Thus, edge contraction is a special case of vertex identification.) The operation may occur on any pair (or subset) of vertices in the graph. Edges between two contracting vertices are sometimes removed. If and are vertices of distinct components of , then we can create a new graph by identifying and in as a new vertex in More generally, given a partition of the vertex set, one can identify vertices in the partition; the resulting graph is known as a quotient graph.
Жоғарғы жағы бөлінуі
Vertex cleaving, vertex split дегеніміз – бір төбе екіге бөлінеді, нәтижесінде пайда болған екі жаңа төбе бастапқы төбенің іргелес төбелерімен іргелеседі. Бұл төбелерді біріктіру операциясының кері процесі, бірақ әдетте төбелерді біріктіру кезінде екі біріктірілген төбенің іргелес төбелері бір жиынтықтан құралмайды.
Vertex cleaving, which is the same as vertex splitting, means one vertex is being split into two, where these two new vertices are adjacent to the vertices that the original vertex was adjacent to. This is a reverse operation of vertex identification, although in general for vertex identification, adjacent vertices of the two identified vertices are not the same set.
Жолдың жиырылуы
Жолдың қысқаруы – жолдың бастапқы және соңғы нүктелері арасында бір ғана жиек пайда болатындай етіп, жолдың жиектерінің жиынтығында жүзеге асады. Жол бойындағы төбелерге жанасқан жиектер жойылады немесе кездейсоқ (немесе жүйелі) түрде соңғы нүктелердің біріне қосылады.
Path contraction occurs upon the set of edges in a path that contract to form a single edge between the endpoints of the path. Edges incident to vertices along the path are either eliminated, or arbitrarily (or systematically) connected to one of the endpoints.
Бұрау
Екі бөлек графты қарастырайық және , мұнда вертекстерін қамтиды және вертекстерін қамтиды. Егер біз графты вертексін мен вертексіне, ал вертексін мен вертексіне біріктіру арқылы ала алатын болсақ, вертексінің жиынына қатысты графтың бұралуында, мысалы, вертексін мен вертексін біріктіреміз.
Consider two disjoint graphs and , where contains vertices and and contains vertices and Suppose we can obtain the graph by identifying the vertices of and of as the vertex of and identifying the vertices of and of as the vertex of In a twisting of with respect to the vertex set , we identify, instead, with and with .
Қолданбалар
Шекаралық және төбелерді жиыру әдістері графтың қабырғалары немесе төбелерінің саны бойынша индукция арқылы дәлелдеуде өте пайдалы, онда кіші графтардың барлығы үшін белгілі бір қасиет орындалады деп есептелінеді және осыны үлкен граф үшін дәлелдеуге қолдануға болады. Қабырғаны жиыру кездейсоқ байланысқан графтың аралас ағаштарының санына арналған рекурсивті формулаларда және қарапайым графтың түстік полиномына арналған рекурренттік формулаларда қолданылады. Жиырулар графты қарапайымдастыру қажет болғанда, бір-біріне эквивалентті ұғымдарды білдіретін төбелерді біріктіру арқылы да пайдалы. Ең көп таралған мысал – әрбір күшті байланысқан компоненттегі барлық төбелерді жиыру арқылы жалпы бағытталған графикті ациклді бағытталған графикке келтіру. Егер граф сипаттайтын қатынас транзитивті болса, оны құрастыру үшін жиырылған төбелердің белгілерінің жиынтығымен әр төбеге белгі берілгенше, ешқандай ақпарат жоғалмайды. Тағы бір мысал – жаһандық график түсін бөлуде жүзеге асырылатын біріктіру, онда төбелер келісімге келтіріледі (қауіпсіз болған жағдайда) әртүрлі айнымалылар арасындағы жылжу операцияларын болдырмау үшін. Қабырғаны жиыру 3D модельдеу пакеттерінде (қолымен немесе модельдеу бағдарламалық құралының кейбір мүмкіндіктері арқылы) төбелер санын үнемі азайту үшін қолданылады, бұл төмен полигонды модельдерді жасауға көмектеседі.
Both edge and vertex contraction techniques are valuable in proof by induction on the number of vertices or edges in a graph, where it can be assumed that a property holds for all smaller graphs and this can be used to prove the property for the larger graph. Edge contraction is used in the recursive formula for the number of spanning trees of an arbitrary connected graph, and in the recurrence formula for the chromatic polynomial of a simple graph. Contractions are also useful in structures where we wish to simplify a graph by identifying vertices that represent essentially equivalent entities. One of the most common examples is the reduction of a general directed graph to an acyclic directed graph by contracting all of the vertices in each strongly connected component. If the relation described by the graph is transitive, no information is lost as long as we label each vertex with the set of labels of the vertices that were contracted to form it. Another example is the coalescing performed in global graph coloring register allocation, where vertices are contracted (where it is safe) in order to eliminate move operations between distinct variables. Edge contraction is used in 3D modelling packages (either manually, or through some feature of the modelling software) to consistently reduce vertex count, aiding in the creation of low polygon models.