Кіріспе

Бағытталмаған граф, симметрияның транзитивті циклдік тобымен әрекет ететін
квадраттық матрицалар

Граф теориясында циркуляциялық граф – кез келген төбеден кез келген төбеге симметрияның циклдік тобы арқылы әрекет ететін бағытталмаған граф. Ол кейде циклді граф деп те аталады. Графтың автоморфизм тобы графтың төбелерінде транзитивті әрекет ететін циклдік кіші топты қамтиды. Яғни, графтың граф автоморфизмі бар, ол төбелердің циклдік орналасуы болып табылады. Графтың жапсарлас матрицасы циркуляциялық матрица болып табылады. Графтың n төбесін 0-ден n-1 дейін нөмірлеуге болады, егер x және (x + d) mod n нөмірленген екі төбе жапсарлас болса, онда z және (z + d) mod n нөмірленген кез келген екі төбе жапсарлас болады. Графты (қиылыстармен мүмкін) оның төбелері дұрыс көпбұрыштың бұрыштарында жатқандай етіп салуға болады, және көпбұрыштың кез келген айналу симметриясы да суреттің симметриясы болып табылады. Граф – циклдік топтың Кейли графы.

Мысалдар

Кез келген циклдік график – циркуляциялық график, сондай-ақ 2 модуль 4-ке конгруэнтті ұштары бар кез келген тәждік график. n реттік Палей графиктері (мұнда n – 1 модуль 4-ке конгруэнтті жай сан) – бұл 0-ден n-1-ге дейінгі сандардан тұратын және екі төбесі арасындағы айырма n модульдік квадраттық қалдық болса, олар қосымша болатын график. Қабырғаның болуы немесе болмауы екі төбе сандарының n модульдік айырмасына ғана байланысты болғандықтан, кез келген Палей графигі циркуляциялық график болып табылады. Кез келген Мёбиус баспалдағы – циркуляциялық график, әрбір толық график сияқты. Толық екі бөлікті график, егер оның екі бөлігіндегі төбелер саны тең болса, циркуляциялық график болып табылады. Егер m және n сандары өзара жай болса, онда m × n атқыш графигі (m × n шахмат тақтасының әрбір шаршысы үшін төбесі және шахмат атқышы бір жүрісте қозғала алатын әр екі шаршы арасындағы қабырғасы бар график) циркуляциялық график болып табылады. Себебі оның симметрияларына кіші топ ретінде Cmn циклдік тобы кіреді (Cm × Cn). Жалпы алғанда, осы жағдайда кез келген m және n төбелі циркулянттар арасындағы графиктердің тензорлық көбейтіндісі өзі циркулянт болып табылады.

Нақты мысал

Циркулянттық граф секірулермен – бұл n түйіні бар граф, онда әрбір i түйіні 2k түйінге іргелес. Граф байланысты егер және ғана егер . Егер k және n белгілі бүтін сандар болса, онда созылатын ағаштардың саны n ретті рекурренттік қатынасты қанағаттандырады. Атап айтқанда, , мұнда – n-ші Фибоначчи саны.

Өзін-өзі толықтыратын циркуляторлар

Өзін-өзі толықтыратын график – әрбір қабырғасын қабырға емес элементке ауыстыру және керісінше, изоморфты график тудыратын график. Мысалы, бес төбелі циклдік график өзін-өзі толықтырады, сонымен қатар айналымдық график болып табылады. Көбінесе, жай реттік әрбір Пейли графигі өзін-өзі толықтыратын айналымдық график болып табылады. Хорст Сакс көрсеткендей, егер n санының әрбір жай көбейткіші 4 модулі бойынша 1-ге сәйкес келсе, онда n төбесі бар өзін-өзі толықтыратын айналымдық график бар. Ол бұл шарттың да қажетті екенін болжады: n-нің басқа ешқандай мәні өзін-өзі толықтыратын айналымдық графиктің болуына мүмкіндік бермейді.

Алгоритмдік сұрақтар

Айналмалы графиктерді тануға полиномиалдық уақыт алгоритмі бар, және айналмалы графиктер үшін изоморфизм мәселесі полиномиалдық уақытта шешіледі.