Циклдік график - Cycle graph - Wikipedia

Циклдік график
Бағытталмаған 6 цикл.svg
Ұзындығы 6 циклдік график
Тікn
Шеттерn
Гиртn
Автоморфизмдер2n (Д.n)
Хроматикалық сан3 егер n тақ
2 әйтпесе
Хроматикалық индекс3 егер n тақ
2 әйтпесе
Спектр{2 cos (2кπ/n); к = 1, ..., n[1]
Қасиеттері2-тұрақты
Шың-өтпелі
Жиек-өтпелі
Бірлік арақашықтық
Гамильтониан
Эйлериан
Ескерту
Графиктер мен параметрлер кестесі

Жылы графтар теориясы, а цикл графигі немесе дөңгелек граф Бұл график жалғыздан тұрады цикл, немесе басқаша айтқанда, шыңдардың кейбір саны (егер график болса, кем дегенде 3) қарапайым ) тұйық тізбекте қосылған. Цикл графигі n шыңдар деп аталады Cn. Ішіндегі төбелердің саны Cn санына тең шеттері, және әр шыңда бар дәрежесі 2; яғни, әр шыңның өзіне сәйкес екі шеті болады.

Терминология

Мұнда көптеген бар синонимдер «циклдік график» үшін. Оларға жатады қарапайым циклдік график және циклдік график, соңғы термин аз қолданылады, дегенмен, ол тек графиктерге сілтеме жасай алады ациклді. Граф теоретиктерінің арасында цикл, көпбұрыш, немесе n-болды жиі қолданылады. Термин n-цикл кейде басқа параметрлерде қолданылады.[2]

Төбелерінің жұп саны бар циклды ан деп атайды тіпті цикл; төбелерінің тақ саны бар циклды ан деп атайды тақ цикл.

Қасиеттері

Циклдік график дегеніміз:

Одан басқа:

Сияқты Платондық графиктер, циклдік графиктер. қаңқаларын құрайды диедра. Олардың дуалдары - бұл дипольдік графиктер қаңқаларын құрайтын hosohedra.

Бағытталған цикл графигі

Ұзындығы 8 бағытталған циклдік график

A бағытталған цикл графигі - бұл барлық шеттері бір бағытқа бағытталған циклдік графиктің бағытталған нұсқасы.

Ішінде бағытталған граф, кем дегенде бір жиекті қамтитын жиектер жиынтығы (немесе доға) әрбір бағытталған циклдан а деп аталады кері байланыс доғасы. Сол сияқты, әр бағытталған циклдан кем дегенде бір шыңы бар шыңдар жиынтығы а деп аталады кері байланыс шыңы.

Бағытталған циклдік графиканың 1-дәрежелі және 1-ден тыс дәрежелі біркелкі болады.

Бағдарланған циклдік графиктер Кейли графиктері үшін циклдік топтар (мысалы, Тревиссанды қараңыз).

Сондай-ақ қараңыз

Әдебиеттер тізімі

  1. ^ Кейбір қарапайым графикалық спектрлер. win.tue.nl
  2. ^ «11707 есеп». Amer. Математика. Ай сайын. 120 (5): 469-476. Мамыр 2013. дои:10.4169 / amer.math.monly.120.05.469. JSTOR  10.4169 / amer.math.monly.120.05.469.

Сыртқы сілтемелер