केली ग्राफ

File:Cayley graph of F2.svg

दो उत्पादक ए और बी पर मुक्त समूह का केली ग्राफ

गणित में, केली ग्राफ, जिसे केली वर्ण ग्राफ, केली आरेख, समूह आरेख या वर्ण समूह के रूप में भी जाना जाता है एक ग्राफ(असतत गणित) है जो समूह(गणित) की अमूर्त संरचना को कूटबद्ध करता है। इसकी परिभाषा केली के प्रमेय(आर्थर केली के नाम पर) द्वारा सुझाई गई है, और समूह के लिए समूह के निर्दिष्ट उत्पादक समुच्चय का उपयोग करती है। यह संयोजी समूह सिद्धांत और ज्यामितीय समूह सिद्धांत में एक केंद्रीय साधन है। केली ग्राफ़ की संरचना और समरूपता उन्हें विस्तारक ग्राफ़ के वर्गों के निर्माण के लिए विशेष रूप से अच्छे पदान्वेषी बनाती है।

परिभाषा

माना $G$ एक समूह(गणित) है और $S$ $G$ का उत्पादक समुच्चय है। केली ग्राफ $\Gamma =\Gamma (G,S)$ एक ग्राफ वर्णना निर्देशित ग्राफ है जिसे इस प्रकार बनाया गया है:

• $G$ के प्रत्येक अवयव $g$ को शीर्ष नियत किया गया है: $\Gamma$ के शीर्ष समुच्चय की तत्समक $G$ से की जाती है।
• $S$ के प्रत्येक अवयव $s$ को एक वर्ण $c_{s}$ दिया गया है।
• प्रत्येक $g\in G$ और $s\in S$ के लिए, $g$ के अनुरूप शीर्ष से वर्ण $c_{s}$ का एक निर्देशित किनारा होता है जो $gs$ के अनुरूप होता है।

प्रत्येक स्रोत के लिए आवश्यक नहीं है कि $S$ समूह उत्पन्न करें। यदि $S$ $G$ के लिए उत्पादक समुच्चय नहीं है, तो $\Gamma$ वियोजित(ग्राफ़ सिद्धांत) हो जाता है और प्रत्येक संयुक्त घटक $S$ द्वारा उत्पन्न उपसमूह के एक के एक सह समुच्चय का प्रतिनिधित्व करता है।

यदि $S$ का एक अवयव $s$ स्वयं का व्युत्क्रम, $s=s^{-1}$ है, तो यह सामान्यतः एक अप्रत्यक्ष किनारे द्वारा दर्शाया जाता है।

समुच्चय $S$ को कभी-कभी सममित समुच्चय(अर्थात $S=S^{-1}$) माना जाता है और इसमें समूह का तत्समक अवयव सम्मिलित नहीं है। इस विषय में, वर्णहीन केली ग्राफ को एक साधारण अप्रत्यक्ष ग्राफ(असतत गणित) के रूप में दर्शाया जा सकता है।

ज्यामितीय समूह सिद्धांत में, समुच्चय $S$ को प्रायः परिमित माना जाता है जो स्थानीय रूप से परिमित $\Gamma$ से मेल खाता है।

उदाहरण

• मान लीजिए कि $G=\mathbb {Z}$ अनंत चक्रीय समूह और समुच्चय $S$ में मानक उत्पादक 1 और इसके व्युत्क्रम(योगात्मक संकेतन में -1) सम्मिलित है; तो केली ग्राफ एक अनंत पथ है।
• इसी प्रकार यदि $G=\mathbb {Z} _{n}$ क्रम $n$ का परिमित चक्रीय समूह है और समुच्चय $S$ में दो अवयव होते हैं, $G$ का मानक उत्पादक और इसका व्युत्क्रम, तो केली ग्राफ चक्र ग्राफ $C_{n}$ है। अधिक सामान्यतः, परिमित चक्रीय समूहों के केली ग्राफ यथार्थत परिपत्र ग्राफ होते हैं।
• समूहों के प्रत्यक्ष उत्पाद का केली ग्राफ(उत्पादक समुच्चय के रूप में उत्पादक समुच्चय के कार्तीय उत्पाद के साथ) संबंधित केली ग्राफ का कार्तीय उत्पाद है। इस प्रकार चार अवयवों से युक्त $(\pm 1,0),(0,\pm 1)$ उत्पाद के समुच्चय के साथ एबेलियन समूह $\mathbb {Z} ^{2}$ का केली ग्राफ समतल $\mathbb {R} ^{2}$ पर अनंत जालक ग्राफ है, जबकि समान उत्पादक के साथ प्रत्यक्ष उत्पाद $\mathbb {Z} _{n}\times \mathbb {Z} _{m}$के लिए केली ग्राफ एक टोरस्र् पर $n\times m$ परिमित जालक है।

File:Dih 4 Cayley Graph; generators a, b.svg

द्वितल समूह का केली ग्राफ $D_{4}$ दो उत्पादक ए और बी पर

File:Dih 4 Cayley Graph; generators b, c.svg

$D_{4}$ का केली ग्राफ, दो उत्पादक पर जो दोनों स्व-व्युत्क्रम हैं

• दो उत्पादक पर $a$ और $b$ पर द्वितल समूह $D_{4}$ का केली ग्राफ बाईं ओर दर्शाया गया है। लाल तीर $a$ के साथ रचना का प्रतिनिधित्व करते हैं। चूँकि $b$ स्व-व्युत्क्रम(केली तालिका) है, नीली रेखाएँ, जो रचना का प्रतिनिधित्व करती हैं $b$ के साथ रचना का प्रतिनिधित्व करती हैं, अप्रत्यक्ष हैं। इसलिए ग्राफ मिश्रित है: इसमें आठ शीर्ष, आठ तीर और चार किनारे हैं। समूह $D_{4}$ की केली तालिका समूह की प्रस्तुति

$$\langle a,b\mid a^{4}=b^{2}=e,ab=ba^{3}\rangle$$

से प्राप्त की जा सकती है।

$D_{4}$ का एक भिन्न केली ग्राफ दाईं ओर दिखाया गया है। $b$ अभी भी क्षैतिज प्रतिबिंब है और नीली रेखाओं द्वारा दर्शाया गया है, और $c$ एक विकर्ण प्रतिबिंब है और गुलाबी रेखाओं द्वारा दर्शाया गया है। चूंकि दोनों प्रतिबिंब स्व-व्युत्क्रम हैं, दाईं ओर केली ग्राफ पूर्णता से अप्रत्यक्ष है। यह ग्राफ प्रस्तुति

$$\langle b,c\mid b^{2}=c^{2}=e,bcbc=cbcb\rangle$$

से मेल खाता है।

• लेख के शीर्ष पर दर्शाए गए समुच्चय $S=\{a,b,a^{-1},b^{-1}\}$ के अनुरूप दो उत्पादक $a$ और $b$ पर मुक्त समूह का केली ग्राफ, और $e$