Tsikl grafigi (algebra) - Cycle graph (algebra)

Yilda guruh nazariyasi, ning pastki maydoni mavhum algebra, guruh tsikl grafigi turli xilligini tasvirlaydi tsikllar a guruh va ayniqsa kichikning tuzilishini ingl cheklangan guruhlar.

Tsikl - bu o'rnatilgan ma'lum bir guruh elementining kuchlari a, qayerda aⁿ, n- elementning kuchi a ning mahsuloti sifatida aniqlanadi a o'zi tomonidan ko'paytiriladi n marta. Element a deyiladi yaratish tsikl. Sonli guruhda, ning nolga teng bo'lmagan kuchi a bo'lishi kerak guruh identifikatori, e; eng past kuch bunday buyurtma tsikl, undagi aniq elementlar soni. Tsikl grafigida tsikl ko'pburchak shaklida, tepaliklar guruh elementlarini ifodalaydi va bog'lovchi chiziqlar ushbu ko'pburchakdagi barcha elementlar bir xil tsiklning a'zolari ekanligini ko'rsatadi.

Velosipedlar

Velosipedlar bir-birining ustiga chiqib ketishi mumkin, yoki ularda o'ziga xoslikdan boshqa umumiy elementlar bo'lmasligi mumkin. Tsikl grafigi har bir qiziqarli tsiklni ko'pburchak shaklida namoyish etadi.

Agar a 6-tartibli tsiklni hosil qiladi (yoki qisqasi, bor buyurtma 6), keyin a⁶ = e. Keyin vakolatlar to'plami a², {a², a⁴, e} bu tsikl, ammo bu haqiqatan ham yangi ma'lumot emas. Xuddi shunday, a⁵ bilan bir xil tsiklni hosil qiladi a o'zi.

Shunday qilib, faqat ibtidoiy tsikllarni hisobga olish kerak, ya'ni bunday emas pastki to'plamlar boshqa tsikl. Ularning har biri ba'zilar tomonidan yaratilgan ibtidoiy element, a. Bittasini oling nuqta asl guruhning har bir elementi uchun. Har bir ibtidoiy element uchun ulang e ga a, a ga a², ..., aⁿ⁻¹ ga aⁿva hokazo e ga erishildi. Natijada tsikl grafigi hosil bo'ladi.

Qachon a² = e, a buyurtmasi 2 (an involyutsiya ) ga ulanadi e ikki qirradan. Maqsad tsiklning ikki qirrasini ta'kidlashdan tashqari, odatda chizilgan^[1] ikki element orasidagi bitta chiziq sifatida.

Xususiyatlari

Dih₄ kaleydoskop qizil oyna va 4 barobar aylanadigan generatorlar bilan	Uchun tsikl grafigi dihedral guruh Dih₄.

Guruh tsikli grafigiga misol sifatida dihedral guruh Dih₄. Ushbu guruhni ko'paytirish jadvali chapda, tsikl grafigi esa o'ng tomonda ko'rsatilgan e hisobga olish elementini belgilash.

^o	e	b	a	a²	a³	ab	a²b	a³b
e	e	b	a	a²	a³	ab	a²b	a³b
b	b	e	a³b	a²b	ab	a³	a²	a
a	a	ab	a²	a³	e	a²b	a³b	b
a²	a²	a²b	a³	e	a	a³b	b	ab
a³	a³	a³b	e	a	a²	b	ab	a²b
ab	ab	a	b	a³b	a²b	e	a³	a²
a²b	a²b	a²	ab	b	a³b	a	e	a³
a³b	a³b	a³	a²b	ab	b	a²	a	e

Tsiklga e'tibor bering {e, a, a², a³} ko'paytirish jadvalida, bilan a⁴ = e. Teskari a⁻¹ = a³ shuningdek, ushbu tsiklning generatoridir: (a³)² = a², (a³)³ = ava (a³)⁴ = e. Xuddi shunday, har qanday guruhdagi har qanday tsikl kamida ikkita generatorga ega va har ikki yo'nalishda ham o'tishi mumkin. Umuman olganda, soni generatorlar bilan tsikl n elementlari Eyler φ funktsiyasi ning n, va ushbu generatorlarning har qanday biri tsikldagi birinchi tugun sifatida yozilishi mumkin (identifikator yonida e); yoki odatda tugunlar belgilanmasdan qoldiriladi. Jeneratorda ikkita alohida tsikl kesishishi mumkin emas.

Quaternion guruhining tsikli grafigi Q₈.

Oddiy bo'lmagan sonli elementlarni o'z ichiga olgan tsikllarda grafikada ko'rsatilmagan tsiklik kichik guruhlar mavjud. Dih guruhi uchun₄ yuqorida, biz o'rtasida bir chiziq chizish mumkin a² va e beri (a²)² = e, lekin beri a² katta tsiklning bir qismidir, bu tsikl grafikasining chekkasi emas.

Ikkala tsikl identifikatsiya qilinmaydigan elementni bo'lishganda noaniqlik bo'lishi mumkin. Masalan, 8 element quaternion guruhi o'ng tomonda ko'rsatilgan tsikl grafigi mavjud. O'rta qatordagi elementlarning har biri o'zi ko'paytirilganda -1 ni beradi (bu erda 1 identifikatsiya elementi). Bunday holda biz tsikllarni kuzatib borish uchun turli xil ranglardan foydalanishimiz mumkin, ammo simmetriya masalalari ham ishlaydi.

Yuqorida ta'kidlab o'tilganidek, 2 elementli tsiklning ikkita qirrasi odatda bitta chiziq sifatida ifodalanadi.

Elementning teskari tomoni - bu o'z tsiklida o'ziga xoslikni aniqlaydigan aks ettirishga nisbatan nosimmetrik tugun.

Tarix

Tsikl grafikalari raqamlar nazariyotchisi tomonidan o'rganilgan Daniel Shanks 1950 yillarning boshlarida o'rganish vositasi sifatida qoldiq sinflarining multiplikatsion guruhlari.^[2] Ushbu fikrni birinchi marta Shanks kitobining 1962 yildagi birinchi nashrida e'lon qildi Raqamlar nazariyasida echilgan va echilmagan masalalar.^[3] Kitobda Shanks qaysi guruhlarning izomorf tsikli grafikalariga ega ekanligini va tsikl grafigi qachon bo'lganligini tekshiradi planar.^[4] 1978 yil ikkinchi nashrida Shanks o'zining tadqiqotlari haqida fikr yuritadi sinf guruhlari va rivojlanishi go'dak qadami ulkan qadam usul:^[5]

Cheklangan abeliya guruhlari bilan ishlashda tsikl grafikalari foydali ekanligini isbotladi; va men ularni murakkab tuzilishga yo'l topishda tez-tez ishlatib kelganman [77, s. 852], qidirilayotgan multiplikativ munosabatni olishda [78, p. 426] yoki ba'zi bir qidirilayotgan kichik guruhni ajratishda [79].

Tsikl grafikalari Natan Karterning 2009 yilgi kirish darsligida pedagogik vosita sifatida ishlatiladi Vizual guruh nazariyasi.^[6]

Muayyan guruh oilalarining grafik xususiyatlari

Ba'zi bir guruh turlari odatdagi grafikalarni beradi:

Tsiklik guruhlar Z_n, buyurtma n, bu oddiygina sifatida tasvirlangan bitta tsikl n- uchlari elementlari bo'lgan qirrali ko'pburchak:

Z₁	Z₂ = Dih₁	Z₃	Z₄	Z₅	Z₆ = Z₃× Z₂	Z₇	Z₈


Z₉	Z₁₀ = Z₅× Z₂	Z₁₁	Z₁₂ = Z₄× Z₃	Z₁₃	Z₁₄ = Z₇× Z₂	Z₁₅ = Z₅× Z₃	Z₁₆

Z₁₇	Z₁₈ = Z₉× Z₂	Z₁₉	Z₂₀ = Z₅× Z₄	Z₂₁ = Z₇× Z₃	Z₂₂ = Z₁₁× Z₂	Z₂₃	Z₂₄ = Z₈× Z₃

Z₂	Z₂² = Dih₂	Z₂³ = Dih₂× Dih₁	Z₂⁴ = Dih₂²

Qachon n a asosiy raqam, shakl guruhlari (Z_n)^m bo'ladi (n^m − 1)/(n − 1) n- identifikator elementini bo'lishadigan elementlarning tsikllari:

Z₂² = Dih₂	Z₂³ = Dih₂× Dih₁	Z₂⁴ = Dih₂²	Z₃²

Dihedral guruhlar Dih_n, buyurtma 2n dan iborat n-element tsikli va n 2 elementli tsikllar:

Dih₁ = Z₂	Dih₂ = Z₂²	Dih₃	Dih₄	Dih₅	Dih₆ = Dih₃× Z₂	Dih₇	Dih₈	Dih₉	Dih₁₀ = Dih₅× Z₂

Dissiklik guruhlar, Dik_n = Q_4n, buyurtma 4n:

Dic₂ = Q₈	Dic₃ = Q₁₂	Dic₄ = Q₁₆	Dic₅ = Q₂₀	Dic₆ = Q₂₄

Boshqalar to'g'ridan-to'g'ri mahsulotlar:

Z₄× Z₂	Z₄× Z₂²	Z₆× Z₂	Z₈× Z₂	Z₄²

Nosimmetrik guruhlar - nosimmetrik guruh S_n har qanday buyurtma guruhi uchun o'z ichiga oladi n, ushbu guruh uchun izomorfik kichik guruh. Shunday qilib har bir buyurtma guruhining tsikli grafigi n ning sikl grafasida topiladi_n.
Misolga qarang: S ning kichik guruhlari₄

Misol: To'liq oktahedral guruhning kichik guruhlari

S₄ × Z₂

A₄ × Z₂

Dih₄ × Z₂

S₃ × Z₂

The to'liq oktahedral guruh nosimmetrik S guruhining o'zaro bog'liqligi₄ va tsiklik guruh Z₂.
Uning tartibi 48 tani tashkil qiladi va unda 48 ni ajratadigan har bir buyurtmaning kichik guruhlari mavjud.

Quyidagi misollarda bir-biriga bog'liq bo'lgan tugunlar yonma-yon joylashtirilgan,
shuning uchun bu ushbu guruhlar uchun mumkin bo'lgan eng oddiy tsikl grafikalari emas (masalan, o'ngdagi kabi).

S₄ × Z₂ (buyurtma 48)	A₄ × Z₂ (buyurtma 24)	Dih₄ × Z₂ (buyurtma 16)	S₃ × Z₂ = Dih₆ (buyurtma 12)


S₄ (buyurtma 24)	A₄ (buyurtma 12)	Dih₄ (buyurtma 8)	S₃ = Dih₃ (buyurtma 6)

Barcha grafikalar singari tsikl grafigi ham turli xil xususiyatlarni ta'kidlash uchun turli xil usullarda namoyish etilishi mumkin. S ning tsikl grafigining ikkita tasviri₄ bunga misoldir.

S ning tsikl grafigi₄ yuqorida ko'rsatilgan uchta Dihni ta'kidlaydi₄ kichik guruhlar.

Ushbu turli xil ko'rinish simmetriyani ta'kidlaydi inversiya o'ng tomonda.

Shuningdek qarang

Tashqi havolalar

Vayshteyn, Erik V. "Grafik tsikli". MathWorld.

Adabiyotlar

^ Sara Perkins (2000). "A˜n uchun involution grafikalarini almashtirish, 2.2-bo'lim, 3-qism, birinchi rasm" (PDF). Birkbek kolleji, Malet ko'chasi, London, WC1E 7HX: Iqtisodiyot, matematika va statistika maktabi. Olingan 2016-01-31.CS1 tarmog'i: joylashuvi (havola)
^ Shanks 1978 yil, p. 246.
^ Shanks 1978 yil, p. xii.
^ Shanks 1978 yil, 83-98, 206-208-betlar.
^ Shanks 1978 yil, p. 225.
^ Karter, Natan (2009), Vizual guruh nazariyasi, Classroom Resurs Materiallari, Amerika Matematik Uyushmasi, ISBN 978-0-88385-757-1

Skiena, S. (1990). Velosipedlar, yulduzlar va g'ildiraklar. Diskret matematikani amalga oshirish: Matematika bilan kombinatorika va grafikalar nazariyasi (144-147 betlar).
Shanks, Daniel (1978) [1962], Raqamlar nazariyasida echilgan va echilmagan masalalar (2-nashr), Nyu-York: Chelsi nashriyot kompaniyasi, ISBN 0-8284-0297-3
Pemmaraju, S., & Skiena, S. (2003). Velosipedlar, yulduzlar va g'ildiraklar. Hisoblash diskret matematikasi: Matematika bilan kombinatorika va grafikalar nazariyasi (248-249-betlar). Kembrij universiteti matbuoti.

[1] Sara Perkins (2000). "A˜n uchun involution grafikalarini almashtirish, 2.2-bo'lim, 3-qism, birinchi rasm" (PDF). Birkbek kolleji, Malet ko'chasi, London, WC1E 7HX: Iqtisodiyot, matematika va statistika maktabi. Olingan 2016-01-31.CS1 tarmog'i: joylashuvi (havola)

[FOOTNOTEShanks1978246-2] Shanks 1978 yil, p. 246.

[FOOTNOTEShanks1978xii-3] Shanks 1978 yil, p. xii.

[FOOTNOTEShanks197883–98,_206–208-4] Shanks 1978 yil, 83-98, 206-208-betlar.

[FOOTNOTEShanks1978225-5] Shanks 1978 yil, p. 225.

[6] Karter, Natan (2009), Vizual guruh nazariyasi, Classroom Resurs Materiallari, Amerika Matematik Uyushmasi, ISBN 978-0-88385-757-1

[1]

[2]

[3]

[4]

[5]

[6]