Кіріспе

Теңгерімді толық көпбөліктік график

Тұран графигі, деп белгіленеді, толық көпбөліктік график болып табылады; ол нүктелер жиынын мүмкіндігінше тең өлшемді кіші жиынға бөлу арқылы құрастырылады, содан кейін екі нүкте әр түрлі кіші жиынға жатса, олар жиекпен жалғастырылады. Егер және - нүкте санын бөлуден алынған бөлінді және қалдық болса (яғни, ), онда график мынадай формада болады, ал жиектер саны болады.
-ға, бұл жиектер саны былайша қысқаша айтылуы мүмкін: График өлшемдері және өлшемдері бар кіші жиындарға ие; әрбір нүктенің дәрежесі немесе болады. Егер (яғни, егер) бөлінсе, онда ол тұрақты график болады.

Туран теоремасы

Тұран графтары – экстремалды графтар теориясындағы маңызды нәтиже, Тұран теоремасын дәлелдеу үшін қолданған Пал Тұранның есімімен аталады. Көгершін ұясы принципі бойынша, Тұран графигіндегі r + 1 төбесінің кез келген жиыны бір бөлініс кіші жиынындағы екі төбені қамтиды; демек, Тұран графигінде r + 1 өлшемді клика жоқ. Тұран теоремасына сәйкес, Тұран графы n төбесі бар барлық (r + 1) кликасыз графтардың арасында ең көп қабырға санына ие. Киеваш пен Судаков (2003) егер α саны 1-ге жеткілікті жақын болса, Тұран графы αn төбесінің кез келген кіші жиыны кем дегенде бір қабырғаны қамтитын n реттік жалғыз (r + 1) кликасыз граф екенін көрсетті. Эрдос-Стон теоремасы Тұран теоремасын кеңейтеді, графтың субграфигі ретінде белгілі бір Тұран графигі болмайтын графтардағы қабырғалар санын шектеу арқылы. Осы теорема арқылы экстремалды графтар теориясындағы ұқсас шектеулерді кез келген алынған субграф үшін, субграфтың хроматикалық санына байланысты дәлелдеуге болады.

Ерекше жағдайлар

Тұран графындағы r параметрінің бірнеше таңдауы тәуелсіз зерттелген маңызды графтарға әкеледі. Тұранның T(2n,n) графигін толық K2n графигінен толық сәйкестікті алып тастау арқылы құруға болады. Көрсетілгендей, бұл график дәл n боксикаттылыққа ие; ол кейде Робертс графигі деп аталады. Бұл график сонымен қатар n өлшемді қиылыс политопының 1 қаңқасы болып табылады; мысалы, T(6,3) = K2,2,2 графигі - октаэдрлік график, тура октаэдрдің графигі. Егер n жұп адам кешқойға барса және әр адам өз серігінен басқа барлығымен қол алысса, онда бұл график орын алатын қол алысулар жиынтығын сипаттайды; осы себепті оны коктейльдік кеш графигі деп те атайды. Тұранның T(n,2) графигі толық екі бөлікті график болып табылады және n жұп болғанда, Мур графигі. r саны n-нің бөлгіші болғанда, Тұран графигі симметриялық және күшті тұрақты, бірақ кейбір авторлар Тұран графтарын күшті тұрақтылықтың тривиальды жағдайы деп санайды, сондықтан оларды күшті тұрақты графтардың анықтамасынан шығарады. Тұран графтарының класы экспоненциалды түрде көптеген максималды кликаларға ие болуы мүмкін, яғни бұл класта кликалар аз емес. Мысалы, Тұран графигінде 3a²b максималды кликалар бар, мұнда 3a + 2b = n және b ≤ 2; әрбір максималды клика әр бөлімшеден бір төбе таңдау арқылы құралады. Бұл графтардағы қабырғалар санына қарамастан, барлық n төбелі графтар арасында мүмкін болатын ең көп максималды кликалар саны (Moon and Moser 1965); бұл графтар кейде Moon–Moser графтары деп аталады.

Басқа қасиеттері

Әрбір Туран графы – кограф; яғни, ол жеке төбелерден басталып, ажыратылған біріктіру және толықтыру операцияларының тізбегі арқылы құрастырылуы мүмкін. Нақтырақ айтқанда, мұндай тізбек Туран графының тәуелсіз жиындарының әрқайсысын оқшауланған төбелердің ажыратылған біріктіруі ретінде құрудан басталуы мүмкін. Содан кейін, бүкіл граф – осы тәуелсіз жиындардың толықтыруларының ажыратылған біріктіруінің толықтығын құрайды. Чао және Новаки (1982) Туран графтарының түс жағынан бірегей екенін көрсетеді: басқа графтардың осыған ұқсас түстік полиномдары жоқ. Никифоров (2005) графтың k-шы өзіндік мәндері мен оның толықтығының қосындысы үшін төменгі шекті анықтау үшін Туран графынан пайдаланады. Фолс, Пауэлл және Сноинк геномдық деректердегі гендердің гомологтық топтарының кластерлерін табуға арналған тиімді алгоритмді әзірлейді, деректерді граф ретінде бейнелеу және ірі Туран подграфтарын іздеу арқылы. Туран графтары геометриялық графтар теориясымен байланысты қызықты қасиеттерге ие. Pór және Wood (2005) кез келген үш өлшемді тордың көлемі үшін Ω(((rn)3/4) төменгі шекті көрсетеді. Витсенхаузен (1974) тұрақты симплекстің төбелеріне Туран графының орналасуы арқылы құрылған конфигурация үшін Rd бірлік диаметрі бар n нүкте арасындағы квадраттық қашықтықтардың максималды қосындысына қол жеткізілетінін болжайды. n төбесі бар G графигі, егер және тек егер G r түспен тең түстеуге ие болса, T(n,r) Туран графының подграфы болып табылады. Туран графының тәуелсіз жиындарға бөлінуі G-нің түс кластарына бөлінуімен сәйкес келеді. Атап айтқанда, Туран графы – r түспен тең түстеуге ие ең үлкен n төбелі граф.