Графтар теориясы: 3 дәрежелі төбелері бар кубтық графтар, тривалентті графтар және Foster санағы туралы ақпарат. Математикалық анықтамалар мен мысалдар.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
3-дәрежелі барлық төбелері бар граф
Graph with all vertices of degree 3
Граф теориясының математикалық саласында кубтық граф – барлық төбелерінің дәрежесі үшке тең граф. Басқаша айтқанда, кубтық граф – 3-реттелі граф. Кубтық графтар үшмәнді графтар деп те аталады. Бикубтық граф – кубтық екібөлімді граф.
In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3 regular graph. Cubic graphs are also called trivalent graphs. A bicubic graph is a cubic bipartite graph.
Симметрия
1932 жылы Рональд М. Фостер кубикалық симметриялық графтардың үлгілерін жинауды бастады, осылайша Фостер санағының негізі қаланды. Көптеген танымал жеке графиктер кубикалық және симметриялық болып табылады, олардың ішінде пайдалы график, Петерсен графигі, Хейвуд графигі, Мёбиус-Кантор графигі, Паппус графигі, Десаргес графигі, Науру графигі, Коксетер графигі, Тутте-Коксетер графигі, Дайк графигі, Фостер графигі және Биггс-Смит графигі бар. В. Т. Тутте симметриялық кубикалық графтарды ең кіші бүтін сан s арқылы жіктеді, мұнда s ұзындығындағы кез келген екі бағытталған жол графтың тек бір симметриясы арқылы бір-біріне сәйкес келеді. Ол s-тің мәні 5-тен аспайтынын көрсетті және s-тің 1-ден 5-ке дейінгі барлық мүмкін мәндері үшін графиктердің мысалдарын келтірді. Жартылай симметриялық кубикалық графтарға Грей графигі (ең кішкентай жартылай симметриялық кубикалық граф), Любляна графигі және Тутте 12 клеткасы жатады. Фрухт графигі – симметриясы жоқ ең кішкентай бес кубикалық графтың бірі: оның тек бір граф автоморфизмі бар, ол сәйкестік автоморфизмі болып табылады.
In 1932, Ronald M. Foster began collecting examples of cubic symmetric graphs, forming the start of the Foster census. Many well known individual graphs are cubic and symmetric, including the utility graph, the Petersen graph, the Heawood graph, the Möbius–Kantor graph, the Pappus graph, the Desargues graph, the Nauru graph, the Coxeter graph, the Tutte–Coxeter graph, the Dyck graph, the Foster graph and the Biggs–Smith graph. W. T. Tutte classified the symmetric cubic graphs by the smallest integer number s such that each two oriented paths of length s can be mapped to each other by exactly one symmetry of the graph. He showed that s is at most 5, and provided examples of graphs with each possible value of s from 1 to 5. Semi symmetric cubic graphs include the Gray graph (the smallest semi symmetric cubic graph), the Ljubljana graph, and the Tutte 12 cage. The Frucht graph is one of the five smallest cubic graphs without any symmetries: it possesses only a single graph automorphism, the identity automorphism.
Түстер мен жеке жиынтықтар
Брукс теоремасы бойынша, толық K4 графигінен басқа, кез келген байланысты кубтық граф үш түстен аспайтын түспен боялуы мүмкін. Сондықтан, K4-тен басқа кез келген байланысты кубтық графтың кем дегенде n/3 төбесінен тұратын тәуелсіз жиыны болады, мұнда n – графтың төбелерінің саны: мысалы, 3 түсті бояудағы ең ірі түстік кластың кем дегенде осы көптеген төбелері бар. Визинг теоремасына сәйкес, кез келген кубтық графтың қабырғаларын бояу үшін үш немесе төрт түс қажет. 3 қабырғаны бояу – Тайт бояуы деп аталады, ол графтың қабырғаларын үш толық сәйкестікке бөледі. Кёнигтің сызықтық бояу теоремасы бойынша, кез келген бикубтық графтың Тайт бояуы болады. Тайт бояуы жоқ, көпірсіз кубтық графтар сарқырамалар (snarks) деп аталады. Оларға Петерсен графигі, Тиетце графигі, Блануша сарқырамасы, гүл сарқырамасы, қос жұлдыз сарқырамасы, Секерес сарқырамасы және Уоткинс сарқырамасы жатады. Сарқырамалардың саны шексіз.
According to Brooks' theorem every connected cubic graph other than the complete graph K4 has a vertex coloring with at most three colors. Therefore, every connected cubic graph other than K4 has an independent set of at least n/3 vertices, where n is the number of vertices in the graph: for instance, the largest color class in a 3 coloring has at least this many vertices. According to Vizing's theorem every cubic graph needs either three or four colors for an edge coloring. A 3 edge coloring is known as a Tait coloring, and forms a partition of the edges of the graph into three perfect matchings. By Kőnig's line coloring theorem every bicubic graph has a Tait coloring. The bridgeless cubic graphs that do not have a Tait coloring are known as snarks. They include the Petersen graph, Tietze's graph, the Blanuša snarks, the flower snark, the double star snark, the Szekeres snark and the Watkins snark. There is an infinite number of distinct snarks.
Топология және геометрия
Кубтық графтар топологияда бірнеше тәсілмен туындайды. Мысалы, 2g2 төбесі бар кубтық графтар g ≥ 2 туысы бар бетті шалбар жұптарына бөлудің әртүрлі жолдарын сипаттайды. Егер графикті 1 өлшемді CW кешені ретінде қарастырсақ, кубтық графтар жиі кездеседі, себебі 1 ұяшықты бекіту карталарының көпшілігі графиктің 0 қаңқасынан бөлек болады. Кубтық графтар үш өлшемдегі қарапайым полиэдрлердің графтары түрінде де құрылады, мысалы, әр төбесіне үш жақ тірелетін тұрақты додекаэдр сияқты полиэдрлер. Кез келген график ендірілісі екі өлшемді бетке кубтық график құрылымы ретінде, яғни график кодталған карта ретінде бейнелене алады. Бұл құрылымда кубтық графтың әрбір төбесі ендірілістің жалаушасын – бір-бірімен байланысты төбе, қабырға және беттен тұратын үштік жиынтығын көрсетеді. Әр жалаудың үш көршісі – одан осы байланысты үштік жиынтығының бір мүшесін өзгертіп, қалған екі мүшесін өзгертусіз алу арқылы алынған үш жалау.
Cubic graphs arise naturally in topology in several ways. For example, the cubic graphs with 2g 2 vertices describe the different ways of cutting a surface of genus g ≥ 2 into pairs of pants. If one considers a graph to be a 1 dimensional CW complex, cubic graphs are generic in that most 1 cell attaching maps are disjoint from the 0 skeleton of the graph. Cubic graphs are also formed as the graphs of simple polyhedra in three dimensions, polyhedra such as the regular dodecahedron with the property that three faces meet at every vertex. An arbitrary graph embedding on a two dimensional surface may be represented as a cubic graph structure known as a graph encoded map. In this structure, each vertex of a cubic graph represents a flag of the embedding, a mutually incident triple of a vertex, edge, and face of the surface. The three neighbors of each flag are the three flags that may be obtained from it by changing one of the members of this mutually incident triple and leaving the other two members unchanged.
Гамильтондық
Гаммильтондық кубикалық графтар туралы көптеген зерттеулер жүргізілді. 1880 жылы П. Г. Тайт әрбір текше көпжақты графтың Гамильтон айналымы бар деп болжады. Уильям Томас Тютте 1946 жылы 46 төбелі Тютте графымен Тайттың болжамына қарсы мысал келтірді. 1971 жылы Тютте барлық бикубтық графтар Гамильтондық деп болжады. Бірақ, Джозеф Хортон 96 төбелі қарсы мысал, Хортон графы келтірді. Кейін Марк Эллингэм тағы екі қарсы мысал құрды: Эллингэм-Хортон графтары. Барнеттің болжамы, Тайт және Тютте болжамдарының әлі де ашық комбинациясы, әрбір бикубтық көпжақты графтың Гамильтондық екенін айтады. Кубикалық граф Гамильтондық болғанда, LCF нотациясы оны ықшам түрде көрсетуге мүмкіндік береді. Егер n төбелі кубикалық графтардың арасынан біркелкі кездейсоқ таңдалса, онда ол Гамильтондық болуы ықтимал: n төбелі кубикалық графтардың Гамильтондық үлесі n шексіздікке жақындағанда бірге жуықтасады. Дэвид Эппштейн әрбір n төбелі кубикалық графтың ең көп дегенде 2n/3 (шамамен 1,260n) ерекше Гамильтон айналымы бар екенін болжады және осындай айналымдары бар кубикалық графтардың мысалдарын ұсынды. Гамильтон айналымдарының саны бойынша ең жақсы дәлелденген бағалау: .
There has been much research on Hamiltonicity of cubic graphs. In 1880, P. G. Tait conjectured that every cubic polyhedral graph has a Hamiltonian circuit. William Thomas Tutte provided a counter example to Tait's conjecture, the 46 vertex Tutte graph, in 1946. In 1971, Tutte conjectured that all bicubic graphs are Hamiltonian. However, Joseph Horton provided a counterexample on 96 vertices, the Horton graph. Later, Mark Ellingham constructed two more counterexamples: the Ellingham–Horton graphs. Barnette's conjecture, a still open combination of Tait's and Tutte's conjecture, states that every bicubic polyhedral graph is Hamiltonian. When a cubic graph is Hamiltonian, LCF notation allows it to be represented concisely. If a cubic graph is chosen uniformly at random among all n vertex cubic graphs, then it is very likely to be Hamiltonian: the proportion of the n vertex cubic graphs that are Hamiltonian tends to one in the limit as n goes to infinity. David Eppstein conjectured that every n vertex cubic graph has at most 2n/3 (approximately 1.260n) distinct Hamiltonian cycles, and provided examples of cubic graphs with that many cycles. The best proven estimate for the number of distinct Hamiltonian cycles is .
Басқа қасиеттері
Кез келген n төбесі бар кубикалық графтың жол ені ең көп дегенде n/6-қа тең. Кубикалық графтардың жол ені үшін белгілі ең төменгі шек 0,082n болып табылады. Бұл төменгі шек пен n/6 жоғарғы шек арасындағы айырманы қалай қысқарту әлі белгісіз. 1736 жылы Леонард Эйлер графтар теориясы бойынша жарияланған алғашқы мақаласында дәлелдеген қол алысу леммасы бойынша, кез келген кубикалық графтың төбелерінің саны жұп болады. Петерсен теоремасы бойынша, кез келген көпірсіз кубикалық графтың толық сәйкестігі болады. Ловас және Пламмер кез келген көпірсіз кубикалық графтың экспоненциалдық саны толық сәйкестіктерге ие деген болжам айтты. Бұл болжам жақында дәлелденді, нәтижесінде n төбесі бар кез келген көпірсіз кубикалық графтың кем дегенде 2n/3656 толық сәйкестігі бар екендігі көрсетілді.
The pathwidth of any n vertex cubic graph is at most n/6. The best known lower bound on the pathwidth of cubic graphs is 0.082n. It is not known how to reduce this gap between this lower bound and the n/6 upper bound. It follows from the handshaking lemma, proven by Leonhard Euler in 1736 as part of the first paper on graph theory, that every cubic graph has an even number of vertices. Petersen's theorem states that every cubic bridgeless graph has a perfect matching. Lovász and Plummer conjectured that every cubic bridgeless graph has an exponential number of perfect matchings. The conjecture was recently proved, showing that every cubic bridgeless graph with n vertices has at least 2n/3656 perfect matchings.
Алгоритмдер мен күрделілік
Бірнеше зерттеушілер тек кубтық графтармен шектелген экспоненциалды уақыт алгоритмдерінің күрделілігін зерттеді. Мысалы, графтың жол бойынша жіктелуіне динамикалық бағдарламалауды қолдану арқылы Фомин мен Хойе олардың ең үлкен тәуелсіз жиынтықтарын 2<sup>n</sup>/6 + o(n) уақытында табуға болатынын көрсетті. Бірнеше маңызды графтарды оңтайландыру мәселелері APX-қатты, яғни, олардың жуықтау алгоритмдері бар, олардың жуықтау қатынасы тұрақтымен шектеледі, бірақ олардың жуықтау қатынасы 1-ге жақындайтын полиномиалдық уақытты жуықтау схемалары жоқ, егер P=NP болмаса. Бұларға ең кішкентай төбелік қаптама, ең үлкен тәуелсіз жиынтық, ең кішкентай үстемдік жиынтығы және ең үлкен кесінді табу мәселелері кіреді. Кроссинг саны (кәз келген графты сызуда қиылысатын ең аз қабырғалар саны) кубтық графтар үшін NP-қатты, бірақ жуықтауға болады. Кубтық графтардағы Саяхатшы мәселесін 1153/1152-ден кем фактормен жуықтау NP-қатты екені дәлелденді.
Several researchers have studied the complexity of exponential time algorithms restricted to cubic graphs. For instance, by applying dynamic programming to a path decomposition of the graph, Fomin and Høie showed how to find their maximum independent sets in time 2n/6 + o(n). Several important graph optimization problems are APX hard, meaning that, although they have approximation algorithms whose approximation ratio is bounded by a constant, they do not have polynomial time approximation schemes whose approximation ratio tends to 1 unless P=NP. These include the problems of finding a minimum vertex cover, maximum independent set, minimum dominating set, and maximum cut. The crossing number (the minimum number of edges which cross in any graph drawing) of a cubic graph is also NP hard for cubic graphs but may be approximated. The Travelling Salesman Problem on cubic graphs has been proven to be NP hard to approximate to within any factor less than 1153/1152.