В теорії графів циркулянтним графом називається неорієнтований граф, який має циклічну групу симетрій, яка включає симетрію, при якій граф переводить вершину в будь-яку іншу вершину.
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOHdMekExTDFCaGJHVjVNVE11YzNabkx6STBNSEI0TFZCaGJHVjVNVE11YzNabkxuQnVadz09LnBuZw==.png)
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpODJMelkzTDBOeWIzZHVYMmR5WVhCb2N5NXpkbWN2TkRBd2NIZ3RRM0p2ZDI1ZlozSmhjR2h6TG5OMlp5NXdibWM9LnBuZw==.png)
Еквівалентні визначення
Циркулянтні графи можуть бути визначені кількома еквівалентними способами:
- Автоморфізм групи графа містить циклічну підгрупу, яка діє транзитивно на вершини графа.
- Граф має матрицю суміжності, що є циркулянтною матрицею.
вершин графа можна пронумерувати числами від 0 до n− 1 таким чином, що якщо дві вершини з номерами
та
суміжні, то будь-які дві вершини з номерами
і (z−x+y) modn теж суміжні.
- Граф можна намалювати (з можливими перетинами ребер) так, що його вершини лежать в кутах правильного багатокутника та будь-який поворот багатокутника в себе є симетрією малюнка (отримуємо той же малюнок).
Приклади
Будь-який цикл є циркулянтним графом, як і будь-яка корона.
Графи Пелі порядку (де
— просте число, порівнянне з 1 по модулю 4) — це графи, в яких вершини є числами від 0 до n− 1 і дві вершини суміжні, якщо різниця відповідних чисел є квадратичним відрахуванням по модулю
. Внаслідок того, що присутність або відсутність ребра залежить лише від різниці номерів вершин по модулю
, будь-який граф Пелі є циркулянтним графом.
Будь-які драбини Мебіуса є циркулянтним графом, як і будь-який повний граф. Повний двочастковий граф є циркулянтним, якщо обидві його частини мають однакову кількість вершин.
Якщо два числа та
взаємно прості, то m×n туровий граф (граф, що має вершину в кожній клітині шахової дошки m×n та ребра між будь-якими двома клітинами, якщо тура може перейти з однієї клітини на іншу за один хід) є циркулянтним графом. Це є наслідком того, що його симетрії містять як підгрупу циклічну групу . Як узагальнення цього випадку, декартів добуток графів між будь-якими циркулянтними графами з
та
вершинами дає внаслідок циркулянтний граф.
Багато з відомих нижніх меж чисел Ремзі з'являються з прикладів циркулянтних графів, що мають маленькі максимальні кліки та маленькі максимальні незалежні множини.
Конкретний приклад
Циркулянтний граф з межами
визначається як граф з
вузлами, пронумерованими числами
та кожний вузел
суміжний з 2k вузлами
по модулю
.
- Граф
пов'язаний тоді і лише тоді, коли НСД
.
- Якщо
фіксовані цілі, то число остовних дерев
, де
задовольняє рекурентне співвідношення порядку
.
- Зокрема,
, де
— n-е число Фібоначчі.
Самодоповняльні циркулянти
Самодоповняльний граф — це граф, в якому видалення наявних ребер та додавання відсутніх дає граф, ізоморфний вихідному. Наприклад, циклічний граф з п'ятьма вершинами самодоповняльний і є також циркулянтним. У більш загальному вигляді, будь-який граф Пелі є самодоповняльним циркулянтним графом. [en] показав, що якщо число має властивість, що будь-який простий дільник
порівнюваний з 1 по модулю 4, то існує самодоповняльний циркулянтний граф з
вершинами. Він висловив гіпотезу, що ця умова необхідна, тобто при інших значеннях
самодоповняльні циркулянтні графи не існують. Гіпотезу через 40 років довів Вілфред (Vilfred).
Гіпотеза Адамса
Визначимо циркулянтну нумерацію циркулянтних графів як маркування вершин графа числами від 0 до n− 1 таким чином, що якщо дві вершини та
суміжні, то будь-які дві вершини з номерами
і (z−x+y) modn теж суміжні. Еквівалентно, циркулянтна нумерація — це нумерація вершин, при якій матриця суміжності графа є циркулянтною матрицею.
Нехай — ціле, взаємно просте з
, і нехай
— будь-яке ціле число. Тоді лінійна функція ax+b перетворить циркулянтну нумерацію в іншу циркулянтну нумерацію. Андраш Адам (András Ádám) висловив гіпотезу, що лінійне відображення — єдиний спосіб перенумерації вершин графа, що зберігає властивість циркулянтності. Тобто, якщо
та
— два ізоморфних циркулянтних графи з різною нумерацією, то існує лінійне перетворення, що переводить нумерацію для
в нумерацію для
. Однак, як з'ясувалося, гіпотеза Адама не вірна. Контрприкладом служать графи
та
з 16-тьма вершинами в кожному; вершина
в
з'єднана з шістьма сусідами x± 1, x± 2, і x± 7 (по модулю 16), в той час як в
шість сусідів — це x± 2, x± 3, і x ± 5 (по модулю 16). Ці два графи ізоморфні, але їх ізоморфізм не можна отримати за допомогою лінійного перетворення.
Примітки
- V. Vilfred. [1]..
- Small Ramsey Numbers [ 18 січня 2012 у Wayback Machine.], Stanisław P. Radziszowski, Electronic J. Combinatorics, dynamic survey updated 2009.
- Horst Sachs. . — Т. 9..
Посилання
- Weisstein, Eric W. Circulant Graph(англ.) на сайті Wolfram MathWorld.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
V teoriyi grafiv cirkulyantnim grafom nazivayetsya neoriyentovanij graf yakij maye ciklichnu grupu simetrij yaka vklyuchaye simetriyu pri yakij graf perevodit vershinu v bud yaku inshu vershinu Graf Peli 13 o poryadku yak priklad cirkulyantnogo grafa Korona z shistma vismoma i desyatma vershinami Ekvivalentni viznachennyaCirkulyantni grafi mozhut buti viznacheni kilkoma ekvivalentnimi sposobami Avtomorfizm grupi grafa mistit ciklichnu pidgrupu yaka diye tranzitivno na vershini grafa Graf maye matricyu sumizhnosti sho ye cirkulyantnoyu matriceyu n displaystyle n vershin grafa mozhna pronumeruvati chislami vid 0 do n 1 takim chinom sho yaksho dvi vershini z nomerami x displaystyle x ta y displaystyle y sumizhni to bud yaki dvi vershini z nomerami z displaystyle z i z x y modn tezh sumizhni Graf mozhna namalyuvati z mozhlivimi peretinami reber tak sho jogo vershini lezhat v kutah pravilnogo bagatokutnika ta bud yakij povorot bagatokutnika v sebe ye simetriyeyu malyunka otrimuyemo toj zhe malyunok PrikladiBud yakij cikl ye cirkulyantnim grafom yak i bud yaka korona Grafi Peli poryadku n displaystyle n de n displaystyle n proste chislo porivnyanne z 1 po modulyu 4 ce grafi v yakih vershini ye chislami vid 0 do n 1 i dvi vershini sumizhni yaksho riznicya vidpovidnih chisel ye kvadratichnim vidrahuvannyam po modulyu n displaystyle n Vnaslidok togo sho prisutnist abo vidsutnist rebra zalezhit lishe vid riznici nomeriv vershin po modulyu n displaystyle n bud yakij graf Peli ye cirkulyantnim grafom Bud yaki drabini Mebiusa ye cirkulyantnim grafom yak i bud yakij povnij graf Povnij dvochastkovij graf ye cirkulyantnim yaksho obidvi jogo chastini mayut odnakovu kilkist vershin Yaksho dva chisla m displaystyle m ta n displaystyle n vzayemno prosti to m n turovij graf graf sho maye vershinu v kozhnij klitini shahovoyi doshki m n ta rebra mizh bud yakimi dvoma klitinami yaksho tura mozhe perejti z odniyeyi klitini na inshu za odin hid ye cirkulyantnim grafom Ce ye naslidkom togo sho jogo simetriyi mistyat yak pidgrupu ciklichnu grupu Yak uzagalnennya cogo vipadku dekartiv dobutok grafiv mizh bud yakimi cirkulyantnimi grafami z m displaystyle m ta n displaystyle n vershinami daye vnaslidok cirkulyantnij graf Bagato z vidomih nizhnih mezh chisel Remzi z yavlyayutsya z prikladiv cirkulyantnih grafiv sho mayut malenki maksimalni kliki ta malenki maksimalni nezalezhni mnozhini Konkretnij prikladCirkulyantnij graf C n s 1 s k displaystyle C n s 1 ldots s k z mezhami s 1 s k displaystyle s 1 ldots s k viznachayetsya yak graf z n displaystyle n vuzlami pronumerovanimi chislami 0 1 n 1 displaystyle 0 1 ldots n 1 ta kozhnij vuzel i displaystyle i sumizhnij z 2k vuzlami i s 1 i s k displaystyle i pm s 1 ldots i pm s k po modulyu n displaystyle n Graf C n s 1 s k displaystyle C n s 1 ldots s k pov yazanij todi i lishe todi koli NSD n s 1 s k 1 displaystyle n s 1 ldots s k 1 Yaksho 1 s 1 lt lt s k displaystyle 1 leq s 1 lt cdots lt s k fiksovani cili to chislo ostovnih derev t C n s 1 s k n a n 2 displaystyle t C n s 1 ldots s k na n 2 de a n displaystyle a n zadovolnyaye rekurentne spivvidnoshennya poryadku 2 s k 1 displaystyle 2 s k 1 Zokrema t C n 1 2 n F n 2 displaystyle t C n 1 2 nF n 2 de F n displaystyle F n n e chislo Fibonachchi Samodopovnyalni cirkulyantiDiv takozh Samodopovnyalnij graf Samodopovnyalnij graf ce graf v yakomu vidalennya nayavnih reber ta dodavannya vidsutnih daye graf izomorfnij vihidnomu Napriklad ciklichnij graf z p yatma vershinami samodopovnyalnij i ye takozh cirkulyantnim U bilsh zagalnomu viglyadi bud yakij graf Peli ye samodopovnyalnim cirkulyantnim grafom en pokazav sho yaksho chislo n displaystyle n maye vlastivist sho bud yakij prostij dilnik n displaystyle n porivnyuvanij z 1 po modulyu 4 to isnuye samodopovnyalnij cirkulyantnij graf z n displaystyle n vershinami Vin visloviv gipotezu sho cya umova neobhidna tobto pri inshih znachennyah n displaystyle n samodopovnyalni cirkulyantni grafi ne isnuyut Gipotezu cherez 40 rokiv doviv Vilfred Vilfred Gipoteza AdamsaViznachimo cirkulyantnu numeraciyu cirkulyantnih grafiv yak markuvannya vershin grafa chislami vid 0 do n 1 takim chinom sho yaksho dvi vershini x displaystyle x ta y displaystyle y sumizhni to bud yaki dvi vershini z nomerami z displaystyle z i z x y modn tezh sumizhni Ekvivalentno cirkulyantna numeraciya ce numeraciya vershin pri yakij matricya sumizhnosti grafa ye cirkulyantnoyu matriceyu Nehaj a displaystyle a cile vzayemno proste z n displaystyle n i nehaj b displaystyle b bud yake cile chislo Todi linijna funkciya ax b peretvorit cirkulyantnu numeraciyu v inshu cirkulyantnu numeraciyu Andrash Adam Andras Adam visloviv gipotezu sho linijne vidobrazhennya yedinij sposib perenumeraciyi vershin grafa sho zberigaye vlastivist cirkulyantnosti Tobto yaksho G displaystyle G ta H displaystyle H dva izomorfnih cirkulyantnih grafi z riznoyu numeraciyeyu to isnuye linijne peretvorennya sho perevodit numeraciyu dlya G displaystyle G v numeraciyu dlya H displaystyle H Odnak yak z yasuvalosya gipoteza Adama ne virna Kontrprikladom sluzhat grafi G displaystyle G ta H displaystyle H z 16 tma vershinami v kozhnomu vershina x displaystyle x v G displaystyle G z yednana z shistma susidami x 1 x 2 i x 7 po modulyu 16 v toj chas yak v H displaystyle H shist susidiv ce x 2 x 3 i x 5 po modulyu 16 Ci dva grafi izomorfni ale yih izomorfizm ne mozhna otrimati za dopomogoyu linijnogo peretvorennya PrimitkiV Vilfred 1 Small Ramsey Numbers 18 sichnya 2012 u Wayback Machine Stanislaw P Radziszowski Electronic J Combinatorics dynamic survey updated 2009 Horst Sachs T 9 PosilannyaWeisstein Eric W Circulant Graph angl na sajti Wolfram MathWorld