Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

В теорії графів узагальненими графами Петерсена називають сімейство кубічних графів утворене з єднанням вершин правильно

Узагальнений граф Петерсена

Узагальнений граф Петерсена

В теорії графів узагальненими графами Петерсена називають сімейство кубічних графів, утворене з'єднанням вершин правильного багатокутника з відповідними вершинами зірки. Сімейство містить граф Петерсена і узагальнює один зі шляхів побудови графу Петерсена. Сімейство узагальнених графів Петерсена ввів у розгляд в Коксетер і назву цим графам дав у 1969 році Марк Воткінс.

image
Граф Дюрера G(6,2).

Визначення і позначення

У позначеннях Воткінса G(n,k) — це граф з множиною вершин

{u0, u1, …, un-1, v0, v1, …, vn-1}

і множиною ребер

{ui ui+1, ui vi, vi vi+k: i = 0,…,n − 1}

де індекси беруться за модулем n і k < n/2. Позначенням Коксетера для того ж графу буде {n}+{n/k}, комбінація зі символу Шлефлі для правильного n-кутника та зірки, з яких граф утворено. Будь-який узагальнений граф Петерсена можна побудувати як [en] з графу з двома вершинами, двома петлями і ще одним ребром.

Граф Петерсена сам по собі G(5,2) або {5}+{5/2}.

Приклади

До узагальнених графів Петерсена належать n-призма G(n,1), граф Дюрера G(6,2), граф Мебіуса — Кантора G(8,3), додекаедр G(10,2), граф Дезарга G(10,3) і граф Науру G(12,5).

Чотири узагальнених графи Петерсена — трикутна призма, 5-кутна призма, граф Дюрера і G(7,2) належать до семи графів, що є кубічними, вершинно-3-зв'язковими і (що означає, що всі його найбільші незалежні множини мають однаковий розмір).

Властивості

image
Один з трьох гамільтонових циклів у G(9,2). Два інших гамільтонових цикли в тому самому графі отримують обертанням на 40°.

Це сімейство графів має низку цікавих властивостей. Наприклад:

  1. G(n,k) є вершинно-транзитивним (означає, що є симетрії, які переводять будь-яку вершину в будь-яку іншу) тоді і тільки тоді, коли n = 10 і k =2, або якщо k2 ≡ ±1 (mod n).
  2. Він є реберно-транзитивним (має симетрії, які переводять будь-яке ребро в будь-яке інше) лише в таких семи випадках: (n,k) = (4,1), (5,2), (8,3), (10,2), (10,3), (12,5), (24,5). Тільки ці сім графів є симетричними узагальненими графами Петерсена.
  3. Він є двочастковим у тому і тільки в тому випадку, коли n парне і k непарне.
  4. Він є графом Келі в тому і тільки в тому випадку, коли k2 ≡ 1 (mod n).
  5. Він є , якщо n порівнянне з 5 за модулем 6 і k дорівнює 2, n-2, (n+1)/2, або (n-1)/2 (всі чотири з цих значень k призводять до ізоморфним графів). Він не є гамільтоновим, якщо n ділиться на чотири, щонайменше при значенні 8, і k рівному n/2. У всіх інших випадках він має гамільтонів цикл. Якщо n порівнянне з 3 за модулем 6 і k дорівнює 2, G(n,k) має рівно три гамільтонових цикли, для G(n,2) число гамільтонових циклів можна обчислити за формулою, що залежить від класів n за модулем шість і залучає числа Фібоначчі.

Граф Петерсена є єдиним узагальненим графом Петерсена, який не можна розфарбувати реберно в 3 кольори. Узагальнений граф Петерсена G(9,2) є одним з небагатьох відомих графів, який не можна розфарбувати реберно в 3 кольори.

Будь-який узагальнений граф Петерсена є графом одиничних відстаней.

Див. також

Примітки

  1. H. S. M. Coxeter. Self-dual configurations and regular graphs // Bulletin of the American Mathematical Society. — 1950. — Т. 56 (16 червня). — С. 413—455. — DOI:10.1090/S0002-9904-1950-09407-5.
  2. Mark E. Watkins. A Theorem on Tait Colorings with an Application to the generalized Petersen graphs // . — 1969. — Т. 6 (16 червня). — С. 152—164. — DOI:10.1016/S0021-9800(69)80116-X.
  3. Jonathan L. Gross, Thomas W. Tucker. Пример 2.1.2. // Topological Graph Theory. — New York : Wiley, 1987. — С. 58.
  4. S. R. Campbell, M. N. Ellingham, Gordon F. Royle. A characterisation of well-covered cubic graphs // Journal of Combinatorial Mathematics and Combinatorial Computing. — 1993. — Т. 13 (16 червня). — С. 193—212.
  5. R. Frucht, J. E. Graver, M. E. Watkins. The groups of the generalized Petersen graphs // Proceedings of the . — 1971. — Т. 70. — С. 211—218. — DOI:10.1017/S0305004100049811.
  6. B. R. Alspach. The classification of Hamiltonian generalized Petersen graphs // Journal of Combinatorial Theory, Series B. — 1983. — Т. 34. — С. 293—312. — DOI:10.1016/0095-8956(83)90042-4.
  7. Andrew Thomason. Cubic graphs with three Hamiltonian cycles are not always uniquely edge colorable // Journal of Graph Theory. — 1982. — Т. 6, вип. 2. — С. 219—221. — DOI:10.1002/jgt.3190060218.
  8. Allen J. Schwenk. Enumeration of Hamiltonian cycles in certain generalized Petersen graphs // . — 1989. — Т. 47, вип. 1. — С. 53—59. — (Series B). — DOI:10.1016/0095-8956(89)90064-6.
  9. Frank Castagna, Geert Prins. Every generalized Petersen graph has a Tait Coloring // . — 1972. — Т. 40.
  10. Béla Bollobás. Extremal Graph Theory. — Dover, 2004. — С. 233. Reprint издания 1978 Academic Press
  11. Arjana Žitnik, Boris Horvat, Tomaž Pisanski. All generalized Petersen graphs are unit-distance graphs. — 2010. — Т. 1109.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

V teoriyi grafiv uzagalnenimi grafami Petersena nazivayut simejstvo kubichnih grafiv utvorene z yednannyam vershin pravilnogo bagatokutnika z vidpovidnimi vershinami zirki Simejstvo mistit graf Petersena i uzagalnyuye odin zi shlyahiv pobudovi grafu Petersena Simejstvo uzagalnenih grafiv Petersena vviv u rozglyad v Kokseter i nazvu cim grafam dav u 1969 roci Mark Votkins Graf Dyurera G 6 2 Viznachennya i poznachennyaU poznachennyah Votkinsa G n k ce graf z mnozhinoyu vershin u0 u1 un 1 v0 v1 vn 1 i mnozhinoyu reber ui ui 1 ui vi vi vi k i 0 n 1 de indeksi berutsya za modulem n i k lt n 2 Poznachennyam Koksetera dlya togo zh grafu bude n n k kombinaciya zi simvolu Shlefli dlya pravilnogo n kutnika ta zirki z yakih graf utvoreno Bud yakij uzagalnenij graf Petersena mozhna pobuduvati yak en z grafu z dvoma vershinami dvoma petlyami i she odnim rebrom Graf Petersena sam po sobi G 5 2 abo 5 5 2 PrikladiDo uzagalnenih grafiv Petersena nalezhat n prizma G n 1 graf Dyurera G 6 2 graf Mebiusa Kantora G 8 3 dodekaedr G 10 2 graf Dezarga G 10 3 i graf Nauru G 12 5 Chotiri uzagalnenih grafi Petersena trikutna prizma 5 kutna prizma graf Dyurera i G 7 2 nalezhat do semi grafiv sho ye kubichnimi vershinno 3 zv yazkovimi i sho oznachaye sho vsi jogo najbilshi nezalezhni mnozhini mayut odnakovij rozmir VlastivostiOdin z troh gamiltonovih cikliv u G 9 2 Dva inshih gamiltonovih cikli v tomu samomu grafi otrimuyut obertannyam na 40 Ce simejstvo grafiv maye nizku cikavih vlastivostej Napriklad G n k ye vershinno tranzitivnim oznachaye sho ye simetriyi yaki perevodyat bud yaku vershinu v bud yaku inshu todi i tilki todi koli n 10 i k 2 abo yaksho k2 1 mod n Vin ye reberno tranzitivnim maye simetriyi yaki perevodyat bud yake rebro v bud yake inshe lishe v takih semi vipadkah n k 4 1 5 2 8 3 10 2 10 3 12 5 24 5 Tilki ci sim grafiv ye simetrichnimi uzagalnenimi grafami Petersena Vin ye dvochastkovim u tomu i tilki v tomu vipadku koli n parne i k neparne Vin ye grafom Keli v tomu i tilki v tomu vipadku koli k2 1 mod n Vin ye yaksho n porivnyanne z 5 za modulem 6 i k dorivnyuye 2 n 2 n 1 2 abo n 1 2 vsi chotiri z cih znachen k prizvodyat do izomorfnim grafiv Vin ne ye gamiltonovim yaksho n dilitsya na chotiri shonajmenshe pri znachenni 8 i k rivnomu n 2 U vsih inshih vipadkah vin maye gamiltoniv cikl Yaksho n porivnyanne z 3 za modulem 6 i k dorivnyuye 2 G n k maye rivno tri gamiltonovih cikli dlya G n 2 chislo gamiltonovih cikliv mozhna obchisliti za formuloyu sho zalezhit vid klasiv n za modulem shist i zaluchaye chisla Fibonachchi Graf Petersena ye yedinim uzagalnenim grafom Petersena yakij ne mozhna rozfarbuvati reberno v 3 kolori Uzagalnenij graf Petersena G 9 2 ye odnim z nebagatoh vidomih grafiv yakij ne mozhna rozfarbuvati reberno v 3 kolori Bud yakij uzagalnenij graf Petersena ye grafom odinichnih vidstanej Div takozhGraf Petersena Kubichnij grafPrimitkiH S M Coxeter Self dual configurations and regular graphs Bulletin of the American Mathematical Society 1950 T 56 16 chervnya S 413 455 DOI 10 1090 S0002 9904 1950 09407 5 Mark E Watkins A Theorem on Tait Colorings with an Application to the generalized Petersen graphs 1969 T 6 16 chervnya S 152 164 DOI 10 1016 S0021 9800 69 80116 X Jonathan L Gross Thomas W Tucker Primer 2 1 2 Topological Graph Theory New York Wiley 1987 S 58 S R Campbell M N Ellingham Gordon F Royle A characterisation of well covered cubic graphs Journal of Combinatorial Mathematics and Combinatorial Computing 1993 T 13 16 chervnya S 193 212 R Frucht J E Graver M E Watkins The groups of the generalized Petersen graphs Proceedings of the 1971 T 70 S 211 218 DOI 10 1017 S0305004100049811 B R Alspach The classification of Hamiltonian generalized Petersen graphs Journal of Combinatorial Theory Series B 1983 T 34 S 293 312 DOI 10 1016 0095 8956 83 90042 4 Andrew Thomason Cubic graphs with three Hamiltonian cycles are not always uniquely edge colorable Journal of Graph Theory 1982 T 6 vip 2 S 219 221 DOI 10 1002 jgt 3190060218 Allen J Schwenk Enumeration of Hamiltonian cycles in certain generalized Petersen graphs 1989 T 47 vip 1 S 53 59 Series B DOI 10 1016 0095 8956 89 90064 6 Frank Castagna Geert Prins Every generalized Petersen graph has a Tait Coloring 1972 T 40 Bela Bollobas Extremal Graph Theory Dover 2004 S 233 Reprint izdaniya 1978 Academic Press Arjana Zitnik Boris Horvat Tomaz Pisanski All generalized Petersen graphs are unit distance graphs 2010 T 1109

Дата публікації:
Топ