Кіріспе
Субграфтар жиектері қысқартылған
In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges, vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only if its minors include neither the complete graph K5 nor the complete bipartite graph K3,3. The Robertson–Seymour theorem implies that an analogous forbidden minor characterization exists for every property of graphs that is preserved by deletions and edge contractions. For every fixed graph H, it is possible to test whether H is a minor of an input graph G in polynomial time;
A function f is referred to as "minor monotone" if, whenever H is a minor of G, one has f(H) ≤ f(G).
Графтар теориясында, бағытталмаған граф H, егер H граф G-ден қабырғаларды, төбелерді жою және қабырғаларды қысқарту арқылы құрастырылса, G графигінің миноры деп аталады. Графтар миноры теориясы Вагнер теоремасымен басталды: граф жазық болады, егер және ғана егер оның миноры толық граф K5 немесе толық екі бөлікті граф K3,3-ті қамтымаса. Робертсон-Сеймур теоремасы, жою және қабырғаларды қысқарту арқылы сақталатын графтардың кез келген қасиеті үшін, ұқсас тыйым салынған минор сипаттамасы бар екенін көрсетеді. Кез келген белгілі граф H үшін, H кіріс граф G-нің миноры болып табысады ма, жоқ па, соны полиномиалдық уақытта тексеруге болады; f функциясы "минор монотонды" деп аталады, егер H, G-нің миноры болса, онда f(H) ≤ f(G) теңдігі орындалады.
In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges, vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only if its minors include neither the complete graph K5 nor the complete bipartite graph K3,3. The Robertson–Seymour theorem implies that an analogous forbidden minor characterization exists for every property of graphs that is preserved by deletions and edge contractions. For every fixed graph H, it is possible to test whether H is a minor of an input graph G in polynomial time;
A function f is referred to as "minor monotone" if, whenever H is a minor of G, one has f(H) ≤ f(G).
Негізгі нәтижелер мен болжамдар
Графтың кіші қатынасы шекті бағытталмаған графтардың изоморфизм кластарында ішінара реттілікті қалыптастыратынын тексеру оңай: ол транзитивті (G-нің кіші бөлігі G-нің кіші бөлігі), және G және H бір-біріне кіші болуы мүмкін, егер олар изоморфты болса, өйткені кез келген тривиалды емес кіші операция жиектерді немесе төбелерін жояды. Нил Робертсон мен Пол Сеймурдың терең нәтижесі бойынша бұл ішінара тәртіп шын мәнінде жақсы квази тәртіпке жатады: егер шекті графтардың шексіз тізімі берілсе, онда әрқашан i < j сияқты екі индекс бар, бұл кіші реттікке кішіретілген. Бұл нәтиже бұрын Клаус Вагнердің атынан Вагнердің болжамы деп аталатын болжамды дәлелдеді; Вагнер оны бұдан бұрын көп болжамдаған, бірақ оны 1970 жылы ғана жариялаған. Сеймур мен Робертсон өздерінің дәлелдеуі барысында граф құрылымы теоремасын да дәлелдеді, онда олар кез келген H тұрақты граф үшін H-нің кішігірім граф ретінде болмауы кез келген графтың дөрекі құрылымын анықтайды. Теореманың мәлімдемесі өзі ұзақ және күрделі, бірақ қысқаша айтқанда, мұндай графиктің кіші графтардың кликалық қосындысының құрылымы болуы керек екенін анықтайды. Осылайша, олардың теориясы графтардың кіші бөлшектері мен топологиялық кіріктірілімдері арасындағы негізгі байланыстарды орнатады. Кез келген H графигі үшін қарапайым H кіші еркін графиктер шашыраңқы болуы керек, яғни жиектер саны төбелер санының тұрақты еселігінен аз. Нақтырақ айтқанда, егер H-де h төбесі болса, онда қарапайым n төбесі бар қарапайым H-дің кіші еркін графигінің ең көп дегенде жиектері болуы мүмкін, ал кейбір кіші еркін графиктердің кем дегенде осы көп жиектері болады. Сонымен, егер H-де h төбелері болса, онда H-ке кіші еркін графиктерде орташа дәреже және одан әрі дегенерация бар. Сонымен қатар, H-ке кіші еркін графиктерде жазықтық графиктер үшін жазықтық бөлуші теоремасына ұқсас бөлгіш теоремасы бар: кез келген тұрақты H үшін және кез келген n төбесі бар H-ке кіші еркін G графигі үшін G-ді екіге (мүмкін байланысты емес) субграфиктерге бөліп тастайтын төбелердің қосалқы жиынтығын табуға болады, әрбір субграфикте төбеден аспайтын. Тіпті одан да күшті, кез келген H, H шағын еркін графиктерде ағаштың ені бар. Граф теориясындағы Хадвигер болжамы егер G графигінде k төбесі бар толық графикке кіші изоморфты болмаса, онда G k – 1 түстермен дұрыс бояу болады. 1=k = 5 жағдайы төрт түстер теоремасының қайталауы болып табылады. Хадвигер болжамы k ≤ 6 үшін дәлелденді, бірақ жалпы жағдайда белгісіз, оны "граф теориясындағы ең терең шешілмеген проблемалардың бірі" деп атайды. Төрт түстің теоремасын графтың кіші түстеріне байланысты тағы бір нәтиже - Робертсон, Сандерс, Сеймур және Томас жариялаған snark теоремасы, бұл W. T. Tutte болжаған төрт түстің теоремасын күшейтіп, шетіне түс беруде төрт түс қажет болатын кез келген 3-тұрақты графтың Петерсен графты кіші түске ие болуы керек деп мәлімдейді.
The Hadwiger conjecture in graph theory proposes that if a graph G does not contain a minor isomorphic to the complete graph on k vertices, then G has a proper coloring with k – 1 colors. The case 1=k = 5 is a restatement of the four color theorem. The Hadwiger conjecture has been proven for k ≤ 6, but is unknown in the general case. call it "one of the deepest unsolved problems in graph theory." Another result relating the four color theorem to graph minors is the snark theorem announced by Robertson, Sanders, Seymour, and Thomas, a strengthening of the four color theorem conjectured by W. T. Tutte and stating that any bridgeless 3 regular graph that requires four colors in an edge coloring must have the Petersen graph as a minor.
Кіші жабық графтар отбасылары
Көптеген графтар отбасыларында F-тегі графтың кез келген кіші графигі де F-те болады; мұндай сынып кіші жабық деп аталады. Мысалы, кез келген жазық графта немесе графты белгілі бір топологиялық бетке орналастыруда, қабырғаларды жою немесе қабырғаларды қысқарту орналастырудың туындысын арттыра алмайды; сондықтан жазық графтар және кез келген белгілі бетке орналастырылатын графтар кіші жабық отбасыларды құрайды. Егер F кіші жабық отбасы болса, онда (кіші графиктің жақсы квази-реттелу қасиетіне байланысты) F-қа жатпайтын графтардың арасында кішігірім минималды графтардың шекті жиынтығы X болады. Бұл графтар F үшін тыйым салынған кіші графиктір: граф F-қа жатады, егер және тек қана егер ол X жиынтығындағы кез келген графты кіші графигі ретінде қамтымаса. Яғни, әрбір кіші жабық F отбасы X кіші графигі жоқ графтар отбасы ретінде белгілі бір шекті жиынтық X тыйым салынған кіші графиктері арқылы сипатталуы мүмкін. F шектелген ағаш тереңдігіне ие болса, оның тыйым салынған кіші графиктері жол графтарының ажыратылған қосындысын қамтыса ғана, F шектелген ағаш еніне ие болса, оның тыйым салынған кіші графиктері жазық графты қамтыса ғана, ал F шектелген жергілікті ағаш еніне ие болса (диаметр мен ағаш ені арасындағы функционалдық байланыс) оның тыйым салынған кіші графиктері шыңырақты графты (бір төбесін жою арқылы жазық болатын графты) қамтыса ғана. Егер H жазықтықта тек бір қиылысумен салына алса (яғни, оның қиылысу саны бірге тең болса), онда H кіші графигі жоқ графтар үшін оңайлатылған құрылым теоремасы бар, онда олар жазық графтар мен шектелген ағаш ені бар графтардың кликалық қосындылары ретінде құрылады. Мысалы, K5 және K3,3 екеуінің де қиылысу саны бірге тең, және Вагнер көрсеткендей, K5 кіші графигі жоқ графтар жазық графтар мен сегіз төбесі бар Вагнер графигінің 3 кликалық қосындысымен, ал K3,3 кіші графигі жоқ графтар жазық графтар мен K5-тің 2 кликалық қосындысымен сәйкес келеді.
Топологиялық кәмелетке толмағандар
H графигі G графигінің топологиялық кіші графигі деп аталады, егер H графигінің бөлінісі G графигінің кіші графигіне изоморфты болса. Кез келген топологиялық кіші графигі – кіші графигі де болып табылады. Бірақ керісіншесі жалпы жағдайда дұрыс емес (мысалы, Петерсен графигіндегі K5 толық графигі кіші графигі болып табылады, бірақ топологиялық емес), бірақ ең жоғары дәрежесі үштен аспайтын графиктер үшін бұл дұрыс. Топологиялық кіші графигі қатынасы шекті графиктер жиынында жақсы квази-реттеме емес, сондықтан Робертсон мен Сеймурдың нәтижесі топологиялық кіші графигіне қолданылмайды. Дегенмен, шекті тыйым салынған кіші графигі сипаттамаларынан шекті тыйым салынған топологиялық кіші графигі сипаттамаларын құру оңай, о үшін k шығу жиегі бар әрбір тармақ жиынтығын k жапырақты және кем дегенде екі төменгі дәрежесі бар кез келген ағашпен алмастыру керек.
Жасөспірімдер
H графигі G графигінің индукцияланған кіші графигі деп аталады, егер оны G графигінің индукцияланған ішкі графигінен қабырғаларды қысқарту арқылы алуға болады. Әйтпесе, G графигі H индукцияланған кіші графигін қамтамайтын болады.
Батырылу кіші
Лифтинг деп аталатын граф операциясы суға батыру деп аталатын ұғымның орталық бөлігі болып табылады. Лифтинг – жапсарлас жиектердегі операция. Егер V, U және W үш төбесі берілген болса, мұнда (V, U) және (U, W) графтың жиектері болса, VUW лифтингі немесе (V, U), (U, W) эквиваленті – бұл екі жиекті (V, U) және (U, W) жойып, (V, W) жиегін қосу операциясы. Егер (V, W) жиегі бұрыннан болған болса, V және W енді бірнеше жиекпен байланысады, сондықтан бұл операция көп граф операциясы болып табылады. Егер H графы G графынан лифтинг операцияларының (G бойынша) тізбегі арқылы және содан кейін изоморфты кішіграфты тауып алу арқылы алынса, онда H – G-нің батыру миноры деп айтамыз. Батыру минорын анықтаудың тағы бір тәсілі бар, ол лифтинг операциясына тең. Егер H-нің төбелерінен G-нің төбелеріне инъективті бейнелеу болса, онда H-нің жапсарлас элементтерінің бейнелері G-де жиектері бөлек жолдармен байланысқан болса, H – G-нің батыру миноры болып табылады. Батыру миноры қатынасы – шекті графтар жиынында жақсы квазиреттеу, сондықтан Робертсон мен Сеймурдың нәтижесі батыру минорына қолданылады. Бұл сондай-ақ, әрбір батыру минорына жабық отбасының тыйым салынған батыру минорының шекті отбасымен сипатталатынын білдіреді. Граф салу кезінде батыру миноры жазық емес графтардың жазықтығы ретінде пайда болады: жазықтықтағы графтың суретінен, қиылыстармен, әрбір қиылысу нүктесін жаңа төбемен ауыстыру арқылы батыру минорын құруға болады, және осы процесте әр қиылысқан жиекті жолға бөлуге болады. Бұл жазық графтарға арналған салу әдістерін жазық емес графтарға кеңейтуге мүмкіндік береді.
There is yet another way of defining immersion minors, which is equivalent to the lifting operation. We say that H is an immersion minor of G if there exists an injective mapping from vertices in H to vertices in G where the images of adjacent elements of H are connected in G by edge disjoint paths. The immersion minor relation is a well quasi ordering on the set of finite graphs and hence the result of Robertson and Seymour applies to immersion minors. This furthermore means that every immersion minor closed family is characterized by a finite family of forbidden immersion minors. In graph drawing, immersion minors arise as the planarizations of non planar graphs: from a drawing of a graph in the plane, with crossings, one can form an immersion minor by replacing each crossing point by a new vertex, and in the process also subdividing each crossed edge into a path. This allows drawing methods for planar graphs to be extended to non planar graphs.
Жасы жетпегендер
G графигінің беткей майнасы – G графигінің жиектері жиынтығын қысқарту арқылы құрылған майнасы, мұнда қысқартылған жиектер диаметрі төмен бөлек субграфтар жиынтығын құрайды. Беткей майнастар график майналары мен субграфтар теориялары арасында аралық құрайды, себебі жоғары тереңдігі бар беткей майнастар графикалық майнастардың қалыпты түрімен сәйкес келеді, ал тереңдігі нөлдік беткей майнастар – нақты субграфтар болып табылады. Олар сондай-ақ, кішігірімдерді алу кезінде жабылмаған 1-жазықтық графиктер сияқты графиктер кластарына график майналары теориясын кеңейтуге мүмкіндік береді.
Партитеттік шарттар
Графтың кішігірімдерінің баламалы және теңдестірілген анықтамасы бойынша, H графигі G графигінің кішігірімі болып табылады, егер H графигінің төбелері G графигінің төбелері қиыспайтын кіші ағаштар жиынтығы арқылы бейнеленсе, және егер H графигінде екі төбе іргелес жатса, онда G графигіндегі сәйкес екі ағашта олардың шеткі нүктелері табылуы керек. Тақ кішігірімдер бұл анықтаманы осы кіші ағаштарға жұптылық шарттарын қосу арқылы шектейді. Егер H графигі жоғарыда көрсетілгендей G графигінің кіші ағаштары жиынтығы арқылы бейнеленсе, онда H графигі G графигінің тақ кішігірімі болып табылады, егер G графигінің төбелеріне екі түс тағайындау мүмкін болса, онда G графигіндегі әрбір жиек кіші ағаш ішінде дұрыс боялған (оның шеткі нүктелері әртүрлі түстерде) және G графигіндегі екі кіші ағаш арасындағы іргелес жатқандықты білдіретін әрбір жиек монохроматикалық (оның екі шеткі нүктесі бірдей түсте) болса. Әдеттегі граф кішігірімдерінен айырмашылығы, тыйым салынған тақ кішігірімдері бар графтар міндетті түрде сиректеу болмайды. Хадвигер болжамы, k-хроматикалық графтар міндетті түрде k төбелі толық графтарды кішігірімдер ретінде қамтиды, сонымен қатар тақ кішігірімдер тұрғысынан зерттелді. Граф кішігірімдері түсінігінің тағы бір жұптылыққа негізделген кеңейтілуі – екі бөлікті кішігірімдер түсінігі, ол бастапқы граф екі бөлікті болған кезде екі бөлікті графты тудырады. H графигі басқа G графигінің екі бөлікті кішігірімі болып табылады, егер H графигі G графигінен төбелерді, жиектерді жою және графтың шеткі циклы бойынша бір-бірінен екі қашықтықта орналасқан төбелер жұптарын біріктіру арқылы алынса. Екі бөлікті кішігірімдер үшін Вагнер теоремасының бір түрі қолданылады: G екі бөлікті графы жазықтық граф болып табылады, егер және тек қана оның екі бөлікті кішігірімі ретінде K3,3 пайдалы граф болмаса.
An odd minor restricts this definition by adding parity conditions to these subtrees. If H is represented by a collection of subtrees of G as above, then H is an odd minor of G whenever it is possible to assign two colors to the vertices of G in such a way that each edge of G within a subtree is properly colored (its endpoints have different colors) and each edge of G that represents an adjacency between two subtrees is monochromatic (both its endpoints are the same color). Unlike for the usual kind of graph minors, graphs with forbidden odd minors are not necessarily sparse. The Hadwiger conjecture, that k chromatic graphs necessarily contain k vertex complete graphs as minors, has also been studied from the point of view of odd minors. A different parity based extension of the notion of graph minors is the concept of a bipartite minor, which produces a bipartite graph whenever the starting graph is bipartite. A graph H is a bipartite minor of another graph G whenever H can be obtained from G by deleting vertices, deleting edges, and collapsing pairs of vertices that are at distance two from each other along a peripheral cycle of the graph. A form of Wagner's theorem applies for bipartite minors: A bipartite graph G is a planar graph if and only if it does not have the utility graph K3,3 as a bipartite minor.
Алгоритмдер
График G-де H-дің кіші графигі бар-жоғын анықтау мәселесі жалпы жағдайда NP-толық; мысалы, егер H, G-мен бірдей түйіндер санына ие циклдық граф болса, онда H, G-дің кіші графигі болады, егер және тек қана G-де Гамильтон циклі болса. Дегенмен, G кірістің бөлігі болғанда, ал H белгілі болса, оны полиномиалдық уақытта шешуге болады. Нақтырақ айтқанда, H, G-дің кіші графигі ме, жоқ па, тексеру үшін жұмыс уақыты осы жағдайда O(n³), мұнда n – G-дегі түйіндер саны, ал үлкен O белгісі H-ге суперекспоненциалды түрде тәуелді тұрақтыны жасырады; бастапқы Graph Minors нәтижесінен бері, бұл алгоритм O(n²) уақытына дейін жақсартылды. Осылайша, берілген графикте тыйым салынған кіші графиктің бар-жоғын тексеруге арналған полиномиалдық уақыт алгоритмін қолдану арқылы, теориялық тұрғыдан кез келген кіші жабық отбасының мүшелерін полиномиалдық уақытта тануға болады. Бұл нәтиже практикада қолданылмайды, өйткені жасырылған тұрақты тым үлкен (оны көрсету үшін Кнуттың үш қабатты жоғары көрсеткіш белгісі қажет), кез келген қолданыстан бас тартуға, оны галактикалық алгоритмге айналдыруға себеп болады. Сонымен қатар, осы нәтижені конструктивті қолдану үшін графтар отбасының тыйым салынған кіші графиктерін білу қажет. Кейбір жағдайларда тыйым салынған кіші графиктің қандай екені белгілі немесе оларды есептеуге болады. Егер H белгілі жазық граф болса, онда енгізілген граф G-де H, G-дің кіші графигі ме, жоқ па, сызықтық уақытта тексеруге болады. H белгіленбеген жағдайларда, G жазық болған кезде жылдам алгоритмдер белгілі.