Кіріспе
Граф теориясындағы түсінік
Граф теориясында, қатты реттелген граф (SRG) – v төбесі және k дәрежесі бар 1=G = (V, E) реттелген граф, сондықтан белгілі бір бүтін сандар үшін кез келген екі іргелес төбеде λ ортақ көршілес төбелер болады, ал кез келген екі іргелес емес төбеде μ ортақ көршілес төбелер болады. Мұндай қатты реттелген граф srg(v, k, λ, μ) деп белгіленеді; оның "параметрлері" (v, k, λ, μ) сандары болып табылады. Оның толықтырушысы да қатты реттелген: ол srg(v, v − k − 1, v − 2 − 2k + μ, v − 2k + λ) болып табылады. μ нөлден өзгеше болған жағдайда, қатты реттелген граф диаметрі 2 болатын қашықтық реттелген граф болып табылады. 1=λ = 1 болған жағдайда, ол жергілікті сызықтық граф болып табылады.
every two adjacent vertices have λ common neighbours, and
every two non adjacent vertices have μ common neighbours. Such a strongly regular graph is denoted by srg(v, k, λ, μ); its "parameters" are the numbers in (v, k, λ, μ). Its complement is also strongly regular: it is an srg(v, v − k − 1, v − 2 − 2k + μ, v − 2k + λ). A strongly regular graph is a distance regular graph with diameter 2 whenever μ is non zero. It is a locally linear graph whenever 1=λ = 1.
Этимология
Қатты тұрақты график әдебиетте srg(v, k, λ, μ) деп белгіленеді. Дәстүр бойынша, анықтаманы тривиальды түрде қанағаттандыратын графиктер егжей-тегжейлі зерттеулерден және қатты тұрақты графиктер тізімінен шығарылады. Мұндай графиктердің ішінде бір немесе бірнеше бірдей өлшемдегі толық графиктердің біріктірілген жиынтығы және олардың толықтырғыштары, сондай-ақ бірдей өлшемдегі тәуелсіз жиындары бар толық көпбұрышты графиктер бар. Андри Браувер мен Хендрик ван Малдегем (#References қараңыз) спектрлік граф теориясына негізделген қатты тұрақты графиктің басқаша, бірақ толыққанды эквивалентті анықтамасын қолданады: қатты тұрақты граф – шекті тұрақты граф, ол дәл үш өзіндік мәнге ие, олардың тек біреуі ғана k дәрежесіне тең және көбейістігі 1-ге тең. Бұл толық байланысты графиктерді (тек екі ерекше өзіндік мәні бар, үш емес) және байланыссыз графиктерді (онда k дәрежесінің көбейістігі әртүрлі байланысқан компоненттердің санына тең, демек, бірден көп) автоматты түрде алып тастайды. Браувердің ішіндегі көптеген әдебиеттер үлкен өзіндік мәнді r (көптігі f) деп, ал кішірек өзіндік мәнді s (көптігі g) деп атайды.
Тарих
Р. С. Боз 1963 жылы жоғары реттелген графтарды енгізді. Олар 1950 жылдары спектральдық граф теориясының жаңа саласындағы бұрынғы жұмыстарға негізделген.
Мысалдар
Ұзындығы 5 цикл srg(5, 2, 0, 1) болып табылады. Питерсен графигі srg(10, 3, 0, 1) болып табылады. Клебш графигі srg(16, 5, 0, 2) болып табылады. Шриханде графигі srg(16, 6, 2, 2) болып табылады, ол арақашықтық транзитивті график емес. n × n шаршы ладья графигі, яғни теңгерімді толық екі бөліктік графтың сызықтық графигі Kn,n, srg(n2, 2n – 2, n – 2, 2) болып табылады. Оның параметрлері Шриханде графигімен сәйкес келеді, бірақ екі график изоморфты емес. Толық графтың сызықтық графигі Kn – бұл. Чанг графтары srg(28, 12, 6, 4) болып табылады, бұл K8 сызықтық графигімен бірдей, бірақ бұл төрт график изоморфты емес. Кез келген (s, t) ретті жалпыланған төртбұрыш өзінің сызықтық графигі ретінде srg((s + 1)(st + 1), s(t + 1), s – 1, t + 1) береді. Мысалы, GQ(2, 4) өзінің сызықтық графигі ретінде srg(27, 10, 1, 5) береді. Шлефли графигі srg(27, 16, 10, 8) болып табылады. Хоффман–Синглтон графигі srg(50, 7, 0, 1) болып табылады. Симс Гевиртц графигі (56, 10, 0, 2) болып табылады. M22 графигі, сондай-ақ Меснер графигі srg(77, 16, 0, 4) болып табылады. Браувер–Хеймерс графигі srg(81, 20, 1, 6) болып табылады. Хигман–Симс графигі srg(100, 22, 0, 6) болып табылады. Жергілікті Маклафлин графигі srg(162, 56, 10, 24) болып табылады. Камерон графигі srg(231, 30, 9, 3) болып табылады. Берлекамп–ван Линт–Сейдель графигі srg(243, 22, 1, 2) болып табылады. Маклафлин графигі srg(275, 112, 30, 56) болып табылады. q реттік Палей графигі srg(q, (q – 1)/2, (q – 5)/4, (q – 1)/4) болып табылады. Ең кіші Палей графигі, , 5 циклды (жоғарыда) құрайды. Өзін-өзі толықтыратын доғалық транзитивті графиктер күшті түрде тұрақты болады. График және оның толықтырылысы байланысқан болса, күшті түрде тұрақты график примитивті деп аталады. Жоғарыдағы барлық графиктер примитивті, әйтпесе Конвейдің 99 график мәселесі srg(99, 14, 1, 2) құрылысын сұрайды. Мұндай параметрлері бар график бар-жоғы белгісіз, және Джон Хортон Конвей осы мәселені шешуге 1000 доллар сыйлық ұсынды.
Conway's 99 graph problem asks for the construction of an srg(99, 14, 1, 2). It is unknown whether a graph with these parameters exists, and John Horton Conway offered a $1000 prize for the solution to this problem.
Үшбұрыштысыз графиктер
λ = 0-ге тең күшті тұрақты графиктер үшбұрышсыз болады. 3 төбесінен аз толық графиктер мен барлық толық екі бөлікті графиктерден басқа, бұрын тізілген жеті график (бесбұрыш, Петерсен, Клебш, Хоффман-Синглтон, Гевиртц, Меснер М22 және Хигман-Симс) ғана белгілі.
Геодезиялық графиктер
Кез келген күшті тұрақты граф – геодезиялық граф болып табылады, яғни кез келген екі төбесінің арасында бірегей салмақсыз ең қысқа жол бар. -ға тең күшті тұрақты графтардың тек қана 0 саны белгілі, сондықтан олар үшбұрышсыз да болады. Бұлар Мур графтары деп аталады және төменде егжей-тегжейлі қарастырылады. (400, 21, 2, 1) сияқты параметрлердің басқа комбинациялары әлі жоққа шығарылмады. -ға ие күшті тұрақты графтардың қасиеттерін зерттеуге қарамастан, олардың тағы бар екені немесе олардың саны шекті ме екені әлі белгісіз.