Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Жазық графтардағы тыйым салынған минорлар
On forbidden minors in planar graphs
Графтар теориясында Вагнер теоремасы – Клаус Вагнердің есімімен аталған, жазық графтардың математикалық тыйым салынған минорлар арқылы сипаттамасы. Теоремаға сәйкес, шекті граф жазық болады, егер және тек қана оның минорларында K5 (бес төбесі бар толық граф) немесе K3,3 (үтірлі граф, алты төбесі бар толық екі бөлікті граф) болмаса. Бұл граф минорлары теориясының алғашқы нәтижелерінің бірі және Робертсон–Сеймур теоремасының алғы күші болып саналады.
In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither K5 (the complete graph on five vertices) nor K3,3 (the utility graph, a complete bipartite graph on six vertices). This was one of the earliest results in the theory of graph minors and can be seen as a forerunner of the Robertson–Seymour theorem.
Анықтамалар мен мәлімдеме
Берілген графиктің жазықтықтағы бейнелеуі – график Евклид жазықтығында, оның төбелері үшін нүктелермен және қабырғалары үшін қисықтармен бейнеленген түр, мұнда екі қабырғаның арасындағы жалғыз қиылысу олардың ортақ төбесінде болады. Берілген графиктің кіші графигі – бұл төбелерді, қабырғаларды жою және қабырғаларды біріктіру арқылы құрылған басқа график. Қабырға біріктірілгенде, оның екі төбесі бірігіп, бір төбеге айналады. Графтардың кіші графигі теориясының кейбір нұсқаларында, біріктіруден пайда болған графтар өзіне-өзі циклдарды және бірнеше жақын төбелерді жою арқылы оңайлатылады, ал басқа нұсқаларда көпқырлы графтарға рұқсат етіледі, бірақ бұл өзгеріс Вагнер теоремасына ешқандай әсер етпейді. Вагнер теоремасы бойынша, әрбір графтың жазықтықтағы бейнелеуі болады немесе екі типтің біріне кіші граф: толық граф K5 немесе толық екі бөлікті граф K3,3. (Бір графдың екі типте де кіші графы болуы мүмкін.) Егер берілген граф жазық болса, оның барлық кіші графтары да жазық болады: төбелерді және қабырғаларды жою жазықтықты сақтайды, ал қабырғаны біріктіру де жазықтықты сақтайтын тәсілмен жасалуы мүмкін, біріктірілген қабырғаның екі төбесінің біреуін өз орнында қалдырып, екінші төбесіне жанасқан барлық қабырғаларды біріктірілген қабырғаның бойымен бағыттап. Кіші минималды жазық емес граф – жазық емес, бірақ оның барлық тиісті кіші графтары (кем дегенде бір жою немесе біріктіру арқылы құрылған кіші графтар) жазық. Вагнер теоремасын айтудың тағы бір жолы – екі кіші минималды жазық емес граф бар: K5 және K3,3. Тағы бір нәтиже, кейде Вагнер теоремасы деп аталады, төрт байланысқан граф жазық болады, егер және тек қана оның K5 кіші графы болмаса. Яғни, байланыстың жоғары деңгейін болжай отырып, K3,3 графигін сипаттаудан шығарып, тек K5-ті тыйым салынған кіші граф ретінде қалдыруға болады. Кельманс-Сеймур болжамы бойынша, 5 байланысқан граф жазық болады, егер және тек қана оның K5 топологиялық кіші графы болмаса.
A planar embedding of a given graph is a drawing of the graph in the Euclidean plane, with points for its vertices and curves for its edges, in such a way that the only intersections between pairs of edges are at a common endpoint of the two edges. A minor of a given graph is another graph formed by deleting vertices, deleting edges, and contracting edges. When an edge is contracted, its two endpoints are merged to form a single vertex. In some versions of graph minor theory the graph resulting from a contraction is simplified by removing self loops and multiple adjacencies, while in other version multigraphs are allowed, but this variation makes no difference to Wagner's theorem. Wagner's theorem states that every graph has either a planar embedding, or a minor of one of two types, the complete graph K5 or the complete bipartite graph K3,3. (It is also possible for a single graph to have both types of minor.) If a given graph is planar, so are all its minors: vertex and edge deletion obviously preserve planarity, and edge contraction can also be done in a planarity preserving way, by leaving one of the two endpoints of the contracted edge in place and routing all of the edges that were incident to the other endpoint along the path of the contracted edge. A minor minimal non planar graph is a graph that is not planar, but in which all proper minors (minors formed by at least one deletion or contraction) are planar. Another way of stating Wagner's theorem is that there are only two minor minimal non planar graphs, K5 and K3,3. Another result also sometimes known as Wagner's theorem states that a four connected graph is planar if and only if it has no K5 minor. That is, by assuming a higher level of connectivity, the graph K3,3 can be made unnecessary in the characterization, leaving only a single forbidden minor, K5. Correspondingly, the Kelmans–Seymour conjecture states that a 5 connected graph is planar if and only if it does not have K5 as a topological minor.
Куратовский теоремасымен байланысты тарихы
Вагнер 1937 жылы екі теореманы жариялады, бұл 1930 жылы Куратовский теоремасы жарияланғаннан кейін болды. Куратовский теоремасына сәйкес, граф жазық болады, егер және тек қана егер ол K5 және K3,3 сияқты екі тыйым салынған графтың біреуінің бөлінісін кіші граф ретінде қамтымаса. Бір жағынан, Куратовский теоремасы Вагнер теоремасынан күштірек: бөлініс процесінде пайда болған әрбір жолдың бір қана шетін қалдырып, қалғандарын қысқарту арқылы бөліністі сол типтегі кіші графқа айналдыруға болады, бірақ кіші графты сол типтегі бөлініске айналдыру әрқашан мүмкін емес. Дегенмен, K5 және K3,3 графтары үшін, егер графтың кіші графы ретінде кем дегенде осы екі графтың біреуі болса, онда ол бөлініс ретінде де болады деп оңай дәлелдеуге болады, сондықтан екі теорема эквивалентті.
Wagner published both theorems in 1937, subsequent to the 1930 publication of Kuratowski's theorem, according to which a graph is planar if and only if it does not contain as a subgraph a subdivision of one of the same two forbidden graphs K5 and K3,3. In a sense, Kuratowski's theorem is stronger than Wagner's theorem: a subdivision can be converted into a minor of the same type by contracting all but one edge in each path formed by the subdivision process, but converting a minor into a subdivision of the same type is not always possible. However, in the case of the two graphs K5 and K3,3, it is straightforward to prove that a graph that has at least one of these two graphs as a minor also has at least one of them as a subdivision, so the two theorems are equivalent.
Салдары
Вагнер теоремасының төрт байланысқан графтар үшін күшті нұсқасының бір салдары – K5 кіші графигі жоқ графтарды сипаттау болып табылады. Теореманы мынадайша қайта формулиреуге болады: әрбір мұндай граф жазық немесе қарапайым бөліктерге жіктеледі. Осы идеяны пайдаланып, K5 кіші графигі еркін графтар жазық графтар мен сегіз төбесі бар Вагнер графигінің комбинациялары түрінде құрастырылуы мүмкін, олар кликалық қосынды операциялары арқылы біріктіріледі. Мысалы, K3,3 осылайша үш жазық графтың кликалық қосындысы ретінде құрастырылуы мүмкін, олардың әрқайсысы K4 тетраэдрлік графигінің көшірмесі болып табылады. Вагнер теоремасы графтардың кішігірімдері теориясының маңызды алғышарты болып табылады, ол екі терең және кең қамтитын нәтижелерді дәлелдеуде аяқталды: графтар құрылымы теоремасы (Вагнердің K5 кішігірімдері жоқ графтардың кликалық қосындыға жіктелуінің жалпылауы) және Робертсон–Сеймур теоремасы (жазық графтардың тыйым салынған кішігірімдерінің сипаттамасының жалпылауы, кішігірімдерді алу операциясына қатысты жабық графтар отбасының шекті саны бар тыйым салынған кішігірімдер арқылы сипаттамасы бар). Вагнер теоремасының аналогтары матроидтар теориясына да қолданылуы мүмкін: атап айтқанда, дәл сол K5 және K3,3 графтары (басқа үш тыйым салынған конфигурациямен бірге) графикалық матроидтарды тыйым салынған матроид кішігірімдері арқылы сипаттауда қолданылады.
One consequence of the stronger version of Wagner's theorem for four connected graphs is to characterize the graphs that do not have a K5 minor. The theorem can be rephrased as stating that every such graph is either planar or it can be decomposed into simpler pieces. Using this idea, the K5 minor free graphs may be characterized as the graphs that can be formed as combinations of planar graphs and the eight vertex Wagner graph, glued together by clique sum operations. For instance, K3,3 can be formed in this way as a clique sum of three planar graphs, each of which is a copy of the tetrahedral graph K4. Wagner's theorem is an important precursor to the theory of graph minors, which culminated in the proofs of two deep and far reaching results: the graph structure theorem (a generalization of Wagner's clique sum decomposition of K5 minor free graphs) and the Robertson–Seymour theorem (a generalization of the forbidden minor characterization of planar graphs, stating that every graph family closed under the operation of taking minors has a characterization by a finite number of forbidden minors). Analogues of Wagner's theorem can also be extended to the theory of matroids: in particular, the same two graphs K5 and K3,3 (along with three other forbidden configurations) appear in a characterization of the graphic matroids by forbidden matroid minors.