www.wikidata.uk-ua.nina.az

Симетричний граф В теорії графів граф G є симетричним або дуго транзитивним якщо для будь яких пар суміжних вершин u1 v1

Симетричний граф

В теорії графів, граф G є симетричним (або дуго-транзитивним) якщо, для будь-яких пар суміжних вершин u1—v1 і u2—v2 графа G, існує автоморфізм

Граф Петерсена — (кубічний) симетричний граф. Будь-яка пара суміжних вершин може бути відображена на іншу через автоморфізм, бо будь-яке 5-вершинне кільце може бути відображене в будь-яке інше

такий, що

Інакше кажучи, граф симетричний, якщо група його автоморфізмів діє транзитивно над впорядкованими парами суміжних вершин (тобто, над орієнтованими ребрами). Такий граф іноді називають 1-дуго-транзитивний або прапорцево-транзитивний.

За визначенням (ігноруючи u1 і u2), симетричний граф без ізольованих вершин має також бути вершинно-транзитивним. Завдяки визначенню через відображення одного ребра на інше, симетричний граф має також бути реберно-транзитивним. Однак, реберно-транзитивний граф не має бути симетричним, бо a—b можуть відбиватись в c—d, але не в d—c. Наприклад, напівсиметричний граф є реберно-транзитивним і регулярним, але не вершинно-транзитивним.

Таким чином, кожний зв'язний симетричний граф має бути і вершинно-транзитивним, і реберно-транзитивним, зворотне твердження теж правильне для графів непарних степенів. Однак, для парних степенів, існують зв'язні вершинно-транзитивні і реберно-транзитивні, але не симетричні графи. Такі графи називаються напівтранзитивними[en]. Найменший зв'язний напівтранзитивний граф це граф Хольта[en], зі степенем 4 і 27 вершинами. Деякі автори використовують термін «симетричний граф» для позначення графів, що вершинно-транзитивні і реберно-транзитивні, радше ніж дуго-транзитивні. Таке визначення охоплює напівтранзитивні графи, які виключені визначенням поданим вище.

У відстанево-транзитивного графа замість розглядання пар суміжних вершин (тобто вершин на відстані 1), визначення розглядає дві пари вершин, кожна з однаковою відстанню між вершинами. Такий граф автоматично симетричний за визначенням.

Визначимо t-дугу як послідовність з t+1 вершин таких, що будь-які дві послідовні вершини суміжні, з допустимою відстанню між вершинами, що повторюються, більшою за два кроки. T-транзитивний граф це такий граф, що група автоморфізмів діє транзитивно на t-дугах, але не на (t+1)-дугах. Через те, що 1-дуги це просто ребра, кожний симетричний граф степені 3 або більше має бути t-транзитивний для деякого t, і значення t можна використати для подальшої класифікації симетричних графів. Куб є 2-транзитивним, наприклад.

Приклади Редагувати

Поєднання умови симетричності з накладанням обмеження кубічності на граф (тобто всі вершини мають степінь 3) породжує дуже сильну умову, і такі графи становляться досить рідкісними, щоб бути занесеними в список. Перепис Фостера (англ. Foster census) і його розширення подають такі списки. Перепис Фостера був початий в 1930 році Рональдом Фостером коли він працював у Bell Labs, і в 1988 (коли Фостеру було 92) складений на той момент його перелік (список всіх кубічних симетричних графів до 512 вершин) був опублікованим у формі книги. Перші тринадцять елементів цього списку це кубічні симетричні графи до 30 вершин (десять з них також відстанево-транзитивні; винятки позначені):

Вершин Діаметр Обхват Граф Примітки
4 1 3 Повний граф K4 відстанево-транзитивний, 2-transitive
6 2 4 Повний двочастковий граф K3,3 відстанево-транзитивний, 3-транзитивний
8 3 4 Вершини і ребра куба відстанево-транзитивний, 2-транзитивний
10 2 5 Граф Петерсена відстанево-транзитивний, 3-транзитивний
14 3 6 Граф Хівуда відстанево-транзитивний, 4-транзитивний
16 4 6 Граф Мебіуса — Кантора 2-транзитивний
18 4 6 Граф Паппуса відстанево-транзитивний, 3-транзитивний
20 5 5 Вершини і ребра додекаедра відстанево-транзитивний, 2-транзитивний
20 5 6 Граф Дезарга відстанево-транзитивний, 3-транзитивний
24 4 6 Граф Науру (узагальнений граф Петерсена G(12,5)) 2-транзитивний
26 5 6 Граф F26A 1-транзитивний
28 4 7 Граф Коксетера відстанево-транзитивний, 3-транзитивний
30 4 8 Граф Тютте-Коксетера відстанево-транзитивний, 5-транзитивний

Іншими добре відомими кубічними симетричними графами є граф Діка, граф Фостера і граф Біґґса–Сміта. Десять відстанево-транзитивних графів, які перелічені вище, разом із графом Фостера і графом Біґґса—Сміта, є єдиними кубічними відстанево-транзитивними графами.

Некубічні симетричні графи включають циклічні графи (степеня 2), повні графи (степеня 4 або вище, коли вони мають 5 або більше вершин), графи гіперкуби (степеня 4 або вище, коли вони мають 16 або більше вершин), і графи утворені вершинами і ребрами октаедра, ікосаедра, кубооктаедра та ікосододекаедра. Граф Радо є прикладом симетричного графа з нескінченною кількістю вершин і нескінченним степенем.

Примітки Редагувати

  1. ↑ Biggs, Norman (1993). Algebraic Graph Theory (вид. 2nd). Cambridge: Cambridge University Press. с. 118–140. ISBN 0-521-45897-8. 
  2. ↑ Godsil, Chris; Royle, Gordon (2001). Algebraic Graph Theory. New York: Springer. с. 59. ISBN 0-387-95220-9. 
  3. ↑ Babai, L (1996). Automorphism groups, isomorphism, reconstruction. У Graham, R; Groetschel, M; Lovasz, L. . Elsevier. Архів оригіналу|archiveurl= вимагає |url= (довідка) за 11 червня 2010. Процитовано 10 березня 2011. 
  4. Bouwer, Z. «Vertex and Edge Transitive, But Not 1-Transitive Graphs.» Canad. Math. Bull. 13, 231—237, 1970.
  5. Gross, J.L. and Yellen, J. (2004). Handbook of Graph Theory. CRC Press. с. 491. ISBN 1584880902. 
  6. Holt, Derek F. (1981). A graph which is edge transitive but not arc transitive. Journal of Graph Theory 5 (2): 201–204. doi:10.1002/jgt.3190050210. .
  7. Marston Conder, Trivalent symmetric graphs on up to 768 vertices [ 15 червня 2011 у Wayback Machine.], J. Combin. Math. Combin. Comput, vol. 20, pp. 41—63
  8. Foster, R. M. «Geometrical Circuits of Electrical Networks.» Transactions of the American Institute of Electrical Engineers 51, 309—317, 1932.
  9. «The Foster Census: R.M. Foster's Census of Connected Symmetric Trivalent Graphs», by Ronald M. Foster, I.Z. Bouwer, W.W. Chernoff, B. Monson and Z. Star (1988) ISBN 0-919611-19-2
  10. Biggs, p. 148
  11. ↑ Weisstein, Eric W., «Cubic Symmetric Graph [ 5 січня 2011 у Wayback Machine.]», from Wolfram MathWorld.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
V teoriyi grafiv graf G ye simetrichnim abo dugo tranzitivnim yaksho dlya bud yakih par sumizhnih vershin u1 v1 i u2 v2 grafa G isnuye avtomorfizmGraf Petersena kubichnij simetrichnij graf Bud yaka para sumizhnih vershin mozhe buti vidobrazhena na inshu cherez avtomorfizm bo bud yake 5 vershinne kilce mozhe buti vidobrazhene v bud yake inshe f V G V G takij sho f u1 u2 and f v1 v2 1 Inakshe kazhuchi graf simetrichnij yaksho grupa jogo avtomorfizmiv diye tranzitivno nad vporyadkovanimi parami sumizhnih vershin tobto nad oriyentovanimi rebrami 2 Takij graf inodi nazivayut 1 dugo tranzitivnij 2 abo praporcevo tranzitivnij 3 Za viznachennyam ignoruyuchi u1 i u2 simetrichnij graf bez izolovanih vershin maye takozh buti vershinno tranzitivnim 1 Zavdyaki viznachennyu cherez vidobrazhennya odnogo rebra na inshe simetrichnij graf maye takozh buti reberno tranzitivnim Odnak reberno tranzitivnij graf ne maye buti simetrichnim bo a b mozhut vidbivatis v c d ale ne v d c Napriklad napivsimetrichnij graf ye reberno tranzitivnim i regulyarnim ale ne vershinno tranzitivnim Vidi grafiv za yihnimi avtomorfizmamividstanevo tranzitivnij displaystyle leftarrow silno regulyarnij displaystyle downarrow simetrichnij dugo tranzitivnij displaystyle leftarrow t tranzitivnij t 2 displaystyle downarrow yaksho zv yaznij vershinno ta reberno tranzitivnij en displaystyle rightarrow reberno tranzitivnij i regulyarnij displaystyle rightarrow reberno tranzitivnij displaystyle downarrow displaystyle downarrow vershinno tranzitivnij displaystyle rightarrow regulyarnij displaystyle uparrow graf Kelikososimetrichnij en asimetrichnijTakim chinom kozhnij zv yaznij simetrichnij graf maye buti i vershinno tranzitivnim i reberno tranzitivnim zvorotne tverdzhennya tezh pravilne dlya grafiv neparnih stepeniv 3 Odnak dlya parnih stepeniv isnuyut zv yazni vershinno tranzitivni i reberno tranzitivni ale ne simetrichni grafi 4 Taki grafi nazivayutsya napivtranzitivnimi en 5 Najmenshij zv yaznij napivtranzitivnij graf ce graf Holta en zi stepenem 4 i 27 vershinami 1 6 Deyaki avtori vikoristovuyut termin simetrichnij graf dlya poznachennya grafiv sho vershinno tranzitivni i reberno tranzitivni radshe nizh dugo tranzitivni Take viznachennya ohoplyuye napivtranzitivni grafi yaki viklyucheni viznachennyam podanim vishe U vidstanevo tranzitivnogo grafa zamist rozglyadannya par sumizhnih vershin tobto vershin na vidstani 1 viznachennya rozglyadaye dvi pari vershin kozhna z odnakovoyu vidstannyu mizh vershinami Takij graf avtomatichno simetrichnij za viznachennyam 1 Viznachimo t dugu yak poslidovnist z t 1 vershin takih sho bud yaki dvi poslidovni vershini sumizhni z dopustimoyu vidstannyu mizh vershinami sho povtoryuyutsya bilshoyu za dva kroki T tranzitivnij graf ce takij graf sho grupa avtomorfizmiv diye tranzitivno na t dugah ale ne na t 1 dugah Cherez te sho 1 dugi ce prosto rebra kozhnij simetrichnij graf stepeni 3 abo bilshe maye buti t tranzitivnij dlya deyakogo t i znachennya t mozhna vikoristati dlya podalshoyi klasifikaciyi simetrichnih grafiv Kub ye 2 tranzitivnim napriklad 1 Prikladi RedaguvatiPoyednannya umovi simetrichnosti z nakladannyam obmezhennya kubichnosti na graf tobto vsi vershini mayut stepin 3 porodzhuye duzhe silnu umovu i taki grafi stanovlyatsya dosit ridkisnimi shob buti zanesenimi v spisok Perepis Fostera angl Foster census i jogo rozshirennya podayut taki spiski 7 Perepis Fostera buv pochatij v 1930 roci Ronaldom Fosterom koli vin pracyuvav u Bell Labs 8 i v 1988 koli Fosteru bulo 92 1 skladenij na toj moment jogo perelik spisok vsih kubichnih simetrichnih grafiv do 512 vershin buv opublikovanim u formi knigi 9 Pershi trinadcyat elementiv cogo spisku ce kubichni simetrichni grafi do 30 vershin 10 11 desyat z nih takozh vidstanevo tranzitivni vinyatki poznacheni Vershin Diametr Obhvat Graf Primitki4 1 3 Povnij graf K4 vidstanevo tranzitivnij 2 transitive6 2 4 Povnij dvochastkovij graf K3 3 vidstanevo tranzitivnij 3 tranzitivnij8 3 4 Vershini i rebra kuba vidstanevo tranzitivnij 2 tranzitivnij10 2 5 Graf Petersena vidstanevo tranzitivnij 3 tranzitivnij14 3 6 Graf Hivuda vidstanevo tranzitivnij 4 tranzitivnij16 4 6 Graf Mebiusa Kantora 2 tranzitivnij18 4 6 Graf Pappusa vidstanevo tranzitivnij 3 tranzitivnij20 5 5 Vershini i rebra dodekaedra vidstanevo tranzitivnij 2 tranzitivnij20 5 6 Graf Dezarga vidstanevo tranzitivnij 3 tranzitivnij24 4 6 Graf Nauru uzagalnenij graf Petersena G 12 5 2 tranzitivnij26 5 6 Graf F26A 11 1 tranzitivnij28 4 7 Graf Koksetera vidstanevo tranzitivnij 3 tranzitivnij30 4 8 Graf Tyutte Koksetera vidstanevo tranzitivnij 5 tranzitivnijInshimi dobre vidomimi kubichnimi simetrichnimi grafami ye graf Dika graf Fostera i graf Biggsa Smita Desyat vidstanevo tranzitivnih grafiv yaki perelicheni vishe razom iz grafom Fostera i grafom Biggsa Smita ye yedinimi kubichnimi vidstanevo tranzitivnimi grafami Nekubichni simetrichni grafi vklyuchayut ciklichni grafi stepenya 2 povni grafi stepenya 4 abo vishe koli voni mayut 5 abo bilshe vershin grafi giperkubi stepenya 4 abo vishe koli voni mayut 16 abo bilshe vershin i grafi utvoreni vershinami i rebrami oktaedra ikosaedra kubooktaedra ta ikosododekaedra Graf Rado ye prikladom simetrichnogo grafa z neskinchennoyu kilkistyu vershin i neskinchennim stepenem Primitki Redaguvati a b v g d e Biggs Norman 1993 Algebraic Graph Theory vid 2nd Cambridge Cambridge University Press s 118 140 ISBN 0 521 45897 8 a b Godsil Chris Royle Gordon 2001 Algebraic Graph Theory New York Springer s 59 ISBN 0 387 95220 9 a b Babai L 1996 Automorphism groups isomorphism reconstruction U Graham R Groetschel M Lovasz L Handbook of Combinatorics Elsevier Arhiv originalu archiveurl vimagaye url dovidka za 11 chervnya 2010 Procitovano 10 bereznya 2011 Bouwer Z Vertex and Edge Transitive But Not 1 Transitive Graphs Canad Math Bull 13 231 237 1970 Gross J L and Yellen J 2004 Handbook of Graph Theory CRC Press s 491 ISBN 1584880902 Holt Derek F 1981 A graph which is edge transitive but not arc transitive Journal of Graph Theory 5 2 201 204 doi 10 1002 jgt 3190050210 Marston Conder Trivalent symmetric graphs on up to 768 vertices Arhivovano 15 chervnya 2011 u Wayback Machine J Combin Math Combin Comput vol 20 pp 41 63 Foster R M Geometrical Circuits of Electrical Networks Transactions of the American Institute of Electrical Engineers 51 309 317 1932 The Foster Census R M Foster s Census of Connected Symmetric Trivalent Graphs by Ronald M Foster I Z Bouwer W W Chernoff B Monson and Z Star 1988 ISBN 0 919611 19 2 Biggs p 148 a b Weisstein Eric W Cubic Symmetric Graph Arhivovano 5 sichnya 2011 u Wayback Machine from Wolfram MathWorld Otrimano z https uk wikipedia org w index php title Simetrichnij graf amp oldid 36667864