Кіріспе
Графиктер теориясында, тұрақты график – әрбір төбесінің көршілерінің саны бірдей болатын график; яғни, әрбір төбеде бірдей дәреже немесе валенттілік болады. Тұрақты бағытталған график әрбір ішкі төбесінің кіріс дәрежесі мен шығыс дәрежесі бір-біріне тең болуы керек деген қатаң талапты да орындауы тиіс. Дәрежесі k болатын төбелері бар тұрақты график k дәрежелі график немесе k-тұрақты график деп аталады.
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i. e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each internal vertex are equal to each other. A regular graph with vertices of degree k is called a graph or regular graph of degree k.
Ерекше жағдайлар
Ең көп дегенде 2 дәрежелі тұрақты графтарды жіктеу оңай: 0 дәрежелі граф ажыратылған төбелерден тұрады, 1 дәрежелі граф ажыратылған қабырғалардан тұрады, ал 2 дәрежелі граф циклдар мен шексіз тізбектердің ажыратылған біріктірілісінен тұрады. 3 дәрежелі граф кубикалық граф деп аталады. Қатаң тұрақты граф – бұл әрбір жапсарған төбе жұбының ортақ көршілерінің саны бірдей l, ал әрбір жапсарған емес төбе жұбының ортақ көршілерінің саны бірдей n болатын тұрақты граф. Тұрақты, бірақ қатаң емес ең кішкентай графтар – 6 төбелі циклдық граф және айналмалы граф. Кез келген m үшін толық граф қатаң тұрақты.
Тіршілік ету
Қажетті және жеткілікті шарттар реттелген, *n* санындағы графтың болуы үшін – *n* және *n* саны жұп болуы. Дәлел: Толық графтың әрбір екі түрлі төбесі бір-бірмен жалғыз қабырға арқылы байланысқан. Сондықтан толық графта қабырғалардың саны максимал болады және қабырғалардың саны *n*(n-1)/2-ге тең, ал дәрежесі *n*-1-ге тең. Бұл нақты граф үшін ең төменгі дәреже. Сондай-ақ, егер кез келген реттелген графтың *n* саны болса, онда қабырғалардың саны *n*k/2-ге тең, сондықтан *n* жұп болуы керек. Мұндай жағдайда, циркуляциялық графтар үшін тиісті параметрлерді қарастыра отырып, реттелген графтарды құру оңай.
Қасиеттері
Қол алысу леммасы бойынша, тақ k-ға ие k-тұрақты графтың төбелерінің саны жұп болады. Нэш Уильямстың теоремасы 2k + 1 төбесі бар кез келген графтың Гамильтон циклі болатынын айтады. A графиктің жапсарлас матрицасы болсын. Онда граф тұрақты болады, егер және тек қана A-ның өзіндік векторы болса. Оның өзіндік мәні графиктің тұрақты дәрежесіне тең болады. Басқа өзіндік мәндерге сәйкес келетін өзіндік векторлар ортогоналды , сондықтан мұндай өзіндік векторлар үшін . k дәрежелі тұрақты граф байланысты болады, егер және тек қана k өзіндік мәнінің көптігі біреу болса. "Тек қана егер" бағыты Перрон-Фробеніус теоремасының салдары болып табылады. G диаметрі D және жапсарлас матрицаның өзіндік мәндері бар k-тұрақты граф болсын. Егер G екібөлікті болмаса, онда.
A regular graph of degree k is connected if and only if the eigenvalue k has multiplicity one. The "only if" direction is a consequence of the Perron–Frobenius theorem. Let G be a k regular graph with diameter D and eigenvalues of adjacency matrix If G is not bipartite, then
Ұрпақ
Тез алгоритмдер бар, олар белгілі бір дәрежедегі және қабырғалар санындағы барлық тұрақты графтарды изоморфизмге дейін жасай алады.