Strongly regular graph
گراف تھیوری میں، ایک مضبوط باقاعدہ گراف (ایس آر جی) عمودی اور ڈگری کے ساتھ ایک باقاعدہ گراف ہے جس میں کچھ دیئے گئے انٹیجرز کے لیے ہر دو ملحقہ عمودی مشترکہ پڑوسی ہوتے ہیں، اور ہر دو غیر ملحقہ عمودی مشترکہ پڑوسی ہوتے ہیں۔ اس طرح کے مضبوط باقاعدہ گراف کی نشاندہی کی جاتی ہے۔ اس کی تکمیل بھی سختی سے باقاعدہ ہے: ایک مضبوط باقاعدہ گراف قطر 2 کے ساتھ فاصلہ باقاعدہ گراف ہوتا ہے جب بھی μ غیر صفر ہوتا ہے۔ یہ جب بھی مقامی طور پر لکیری گراف ہوتا ہے۔ ایک مضبوط باقاعدہ گراف کو ادب میں ایس آر جی (v، k، λ، μ) سے ظاہر کیا جاتا ہے۔ روایت کے مطابق، وہ گراف جو معمولی طور پر تعریف کو پورا کرتے ہیں انہیں تفصیلی مطالعات اور سختی سے باقاعدہ گراف کی فہرستوں سے خارج کر دیا جاتا ہے۔ ان میں ایک یا زیادہ مساوی سائز کے مکمل گرافوں کا جداگانہ اتحاد، اور ان کی تکمیل، مساوی سائز کے آزاد سیٹوں کے ساتھ مکمل ملٹی پارٹیٹ گراف شامل ہیں۔ اینڈریس بروور اور ہینڈرک وین مالڈیگیم (دیکھیں #References) سپیکٹرم گراف تھیوری پر مبنی مضبوط باقاعدہ گراف کی ایک متبادل لیکن مکمل طور پر مساوی تعریف استعمال کرتے ہیں: ایک مضبوط باقاعدہ گراف ایک محدود باقاعدہ گراف ہے جس میں بالکل تین آئجن ویلیوز ہیں، جن میں سے صرف ایک ڈگری کے برابر ہے، ضرب 1 کی۔ یہ خود بخود مکمل طور پر جڑے ہوئے گراف (جن میں صرف دو الگ الگ آئجن ویلیوز ہیں، تین نہیں) اور منقطع گراف (جن کی ڈگری k کی ضرب مختلف جڑے ہوئے اجزاء کی تعداد کے برابر ہے، جو اس وجہ سے ایک سے زیادہ ہوگی) کو مسترد کرتا ہے۔ زیادہ تر ادب، بشمول بروور، بڑے آئجن ویلیو کو r (ضرب f کے ساتھ) اور چھوٹے کو s (ضرب g کے ساتھ) کے طور پر حوالہ دیتے ہیں۔ تاریخ مضبوط طور پر باقاعدہ گراف آر سی کے ذریعے متعارف کرائے گئے تھے۔ بوس 1963 میں۔ انہوں نے 1950 کی دہائی میں سپیکٹرم گراف تھیوری کے اس وقت کے نئے میدان میں پہلے کے کام پر تعمیر کیا۔ مثالیں لمبائی 5 کا چکر ایک ایس آر جی (5، 2، 0، 1) ہے۔ پیٹرسن گراف ایک ایس آر جی (10، 3، 0، 1) ہے۔ کلیبش گراف ایک ایس آر جی (16، 5، 0، 2) ہے۔ شری کھنڈے گراف ایک ایس آر جی (16، 6، 2، 2) ہے جو فاصلہ-عارضی گراف نہیں ہے۔ n × n مربع روک کا گراف، یعنی متوازن مکمل دو طرفہ گراف Kn، n کا لائن گراف، ایک srg (n2,2n−2, n−2,2) ہے۔ کے پیرامیٹرز شری کھنڈے گراف کے پیرامیٹرز کے ساتھ موافق ہیں، لیکن دونوں گراف آئسومورفک نہیں ہیں۔ مکمل گراف Kn کا لائن گراف an ہے۔ چانگ گراف ایس آر جی (28، 12، 6، 4) ہیں، جو کے 8 کے لائن گراف کی طرح ہیں، لیکن یہ چار گراف آئسومورفک نہیں ہیں۔ ترتیب (s، t) کا ہر عمومی کواڈرینگل اپنے لائن گراف کے طور پر ایک srg ((s + 1) (st + 1)، s (t + 1)، s −1، t + 1) دیتا ہے۔ مثال کے طور پر، جی کیو (2، 4) ایس آر جی (27، 10، 1، 5) کو اپنے لائن گراف کے طور پر دیتا ہے۔ شلافلی گراف ایک ایس آر جی (27، 16، 10، 8) ہے۔ ہوفمین-سنگلٹن گراف ایک ایس آر جی (50، 7، 0، 1) ہے۔ سمز-گیویرٹز گراف ایک (56، 10، 0، 2) ہے۔ M22 گراف عرف میسنر گراف ایک srg (77، 16، 0، 4) ہے۔ بروور-ہیمرز گراف ایک ایس آر جی (81، 20، 1، 6) ہے۔ ہیگ مین سمز گراف ایک ایس آر جی (100، 22، 0، 6) ہے۔ مقامی میک لولن گراف ایک ایس آر جی (162، 56، 10، 24) ہے۔ کیمرون گراف ایک ایس آر جی (239,30,9,3) ہے۔ برلیکمپ-وان لنٹ-سیڈل گراف ایک ایس آر جی (243، 22، 1، 2) ہے۔ میک لولن گراف ایک ایس آر جی (275، 112، 30، 56) ہے۔ ترتیب q کا پالی گراف ایک srg (q، (q−1)/2، (q−5)/4، (q−1)/4) ہے۔ سب سے چھوٹا پیلے گراف، کے ساتھ، 5 سائیکل (اوپر) ہے۔ خود تکمیل آرک-ٹرانزیکٹو گراف مضبوطی سے باقاعدہ ہیں۔ اگر گراف اور اس کی تکمیل دونوں جڑے ہوئے ہوں تو ایک مضبوط باقاعدہ گراف کو ابتدائی کہا جاتا ہے۔ مندرجہ بالا تمام گراف ابتدائی ہیں، جیسا کہ دوسری صورت میں یا۔ کونوے کا 99 گراف کا مسئلہ ایک ایس آر جی (99، 14، 1، 2) کی تعمیر کا مطالبہ کرتا ہے۔ یہ معلوم نہیں ہے کہ آیا ان پیرامیٹرز کے ساتھ کوئی گراف موجود ہے، اور جان ہارٹن کونوے نے اس مسئلے کے حل کے لیے $1000 کا انعام پیش کیا۔ مثلث سے پاک گراف λ = 0 والے مضبوط باقاعدہ گراف مثلث سے پاک ہوتے ہیں۔ 3 سے کم عمودی حصوں پر مکمل گراف اور تمام مکمل دو طرفہ گراف کے علاوہ، پہلے درج کردہ سات (پینٹاگون، پیٹرسن، کلیبش، ہوفمین-سنگلٹن، گیوئرٹز، میسنر-ایم 22، اور ہیگ مین-سمز) صرف معروف ہیں۔ جیوڈیٹک گراف ہر مضبوطی سے باقاعدہ گراف کے ساتھ ایک جیوڈیٹک گراف ہوتا ہے، ایک گراف جس میں ہر دو عمودی حصوں کا ایک منفرد غیر وزن والا مختصر ترین راستہ ہوتا ہے۔ صرف وہی معروف مضبوط باقاعدہ گراف ہیں جہاں 0 ہے، اس لیے مثلث سے پاک بھی ہیں۔ ان کو مور گراف کہا جاتا ہے اور ذیل میں مزید تفصیل سے دریافت کیا گیا ہے۔ پیرامیٹرز کے دیگر امتزاج جیسے (400، 21، 2، 1) کو ابھی تک مسترد نہیں کیا گیا ہے۔ ان خصوصیات پر جاری تحقیق کے باوجود جن کے ساتھ ایک مضبوط باقاعدہ گراف ہوگا، یہ معلوم نہیں ہے کہ آیا کوئی اور موجود ہے یا یہاں تک کہ آیا ان کی تعداد محدود ہے۔ صرف ابتدائی نتیجہ معلوم ہے، جو اس طرح کے گراف کے لیے 1 نہیں ہو سکتا۔ مضبوط باقاعدہ گراف کی الجبرائی خصوصیات پیرامیٹرز کے درمیان بنیادی تعلق ایک ایس آر جی (v, k, λ, μ) میں چار پیرامیٹرز آزاد نہیں ہیں۔ انہیں مندرجہ ذیل تعلق کی اطاعت کرنی چاہیے: مندرجہ بالا تعلق مندرجہ ذیل گنتی کی دلیل کے ذریعے اخذ کیا گیا ہے: تصور کریں کہ گراف کے عمودی حصے تین سطحوں پر واقع ہیں۔ لیول 0 میں کسی بھی ورٹیکس کو جڑ کے طور پر منتخب کریں۔ پھر اس کے k پڑوسی سطح 1 میں ہوتے ہیں، اور دیگر تمام عمودی سطح 2 میں ہوتے ہیں۔ لیول 1 میں عمودی سیدھے جڑ سے جڑے ہوتے ہیں، اس لیے ان کے پاس λ دوسرے پڑوسی جڑ کے ساتھ مشترک ہونے چاہئیں، اور یہ مشترکہ پڑوسی بھی لیول 1 میں ہونے چاہئیں۔ چونکہ ہر ورٹیکس کی ڈگری k ہوتی ہے، اس لیے ہر لیول 1 نوڈ کے لیے سطح 2 میں عمودی حصوں سے جڑنے کے لیے کنارے باقی رہتے ہیں۔ لہذا، سطح 1 اور سطح 2 کے درمیان کنارے ہیں۔ سطح 2 میں عمودی جڑیں براہ راست جڑ سے منسلک نہیں ہیں، اس لیے ان کے جڑ کے ساتھ مشترکہ پڑوسی ہونے چاہئیں، اور یہ مشترکہ پڑوسی سبھی سطح 1 میں ہونے چاہئیں۔ سطح 2 میں عمودی ہیں، اور ہر ایک سطح 1 میں μ عمودی سے جڑا ہوا ہے۔ لہذا سطح 1 اور سطح 2 کے درمیان کناروں کی تعداد ہے۔ سطح 1 اور سطح 2 کے درمیان کناروں کے لیے دو تاثرات کو مساوی کرتے ہوئے، تعلق اس کے بعد آتا ہے۔ ایڈجسینسی میٹرکس مساوات آئیے میں شناختی میٹرکس کی نشاندہی کرتا ہوں اور جے کو ایک کے میٹرکس کی نشاندہی کرتا ہوں، دونوں میٹرکس آرڈر v کے ہیں۔ مضبوطی سے باقاعدہ گراف کا ملحقہ میٹرکس A دو مساوات کو مطمئن کرتا ہے۔ پہلا: جو کہ باقاعدگی کی ضرورت کا اعادہ ہے۔ اس سے پتہ چلتا ہے کہ k آل ون آئجین ویکٹر کے ساتھ ملحقہ میٹرکس کی ایک آئجین ویلیو ہے۔ دوسرا: جو مضبوط باقاعدگی کا اظہار کرتا ہے۔ بائیں ہاتھ کی طرف کا ij-th عنصر i سے j تک دو مراحل والے راستوں کی تعداد دیتا ہے۔ دائیں ہاتھ کی طرف کی پہلی اصطلاح i سے i تک دو مراحل والے راستوں کی تعداد دیتی ہے، یعنی k کنارے باہر اور پیچھے۔ دوسری اصطلاح دو مراحل والے راستوں کی تعداد دیتی ہے جب i اور j براہ راست جڑے ہوتے ہیں۔ جب i اور j جڑے نہیں ہوتے ہیں تو تیسری اصطلاح متعلقہ قدر دیتی ہے۔ چونکہ تینوں معاملات باہمی طور پر خصوصی اور اجتماعی طور پر مکمل ہیں، اس کے بعد سادہ اضافی مساوات آتی ہے۔ اس کے برعکس، ایک ایسا گراف جس کا ملحقہ میٹرکس مذکورہ بالا دونوں شرائط کو پورا کرتا ہے اور جو مکمل یا کالعدم گراف نہیں ہے، ایک مضبوط باقاعدہ گراف ہے۔ آئجین ویلیوز اور گراف سپیکٹرم چونکہ ملحقہ میٹرکس A ہم آہنگ ہے، اس لیے اس کے آئجین ویکٹر آرتھوگنل ہیں۔ ہم نے پہلے ہی ایک آئجین ویوکٹر کا مشاہدہ کیا ہے جس کے اوپر تمام آئجین ویلیو k سے مطابقت رکھتا ہے۔ لہذا دوسرے آئجین ویوکٹر x کو سب کو مطمئن کرنا چاہیے جہاں J پہلے کی طرح آل ون میٹرکس ہے۔ پہلے سے قائم کردہ مساوات کو لیں: اور مندرجہ بالا مساوات کو آئجین ویکٹر x سے ضرب دیں: متعلقہ آئجین ویلیو p کو کال کریں (گراف پیرامیٹر کے ساتھ الجھن میں نہ پڑنا) اور متبادل بنائیں، اور: x کو ختم کریں اور کواڈریٹک حاصل کرنے کے لیے دوبارہ ترتیب دیں: اس سے دو اضافی آئجین ویلیوز ملتی ہیں۔ اس طرح ایک مضبوط باقاعدہ میٹرکس کے لیے بالکل تین آئجن ویلیوز ہیں۔ اس کے برعکس، صرف تین آئجن ویلیوز کے ساتھ منسلک باقاعدہ گراف مضبوطی سے باقاعدہ ہے۔ زیادہ تر مضبوط باقاعدہ گراف لٹریچر میں اصطلاحات کے بعد، بڑے آئجن ویلیو کو ضرب f کے ساتھ r کہا جاتا ہے اور چھوٹے کو ضرب g کے ساتھ s کہا جاتا ہے۔ چونکہ تمام آئجن ویلیوز کا مجموعہ ملحقہ میٹرکس کا سراغ ہے، جو اس معاملے میں صفر ہے، اس لیے متعلقہ ضرب f اور g کا حساب لگایا جا سکتا ہے: آئجن ویلیو k میں ضرب 1 ہے۔ آئجن ویلیو میں کثرت ہے۔ آئجن ویلیو میں کثرت ہے۔ چونکہ ضرب کو عدد ہونا چاہیے، اس لیے ان کے تاثرات v، k، μ، اور λ کی اقدار پر مزید رکاوٹیں فراہم کرتے ہیں۔ مضبوط طور پر باقاعدہ گراف جن کے لیے غیر مساوی ضرب کے ساتھ انٹیجر آئجن ویلیوز ہوتے ہیں۔ مضبوط طور پر باقاعدہ گراف جن کے لیے سمٹرک کانفرنس میٹرکس کے ساتھ تعلق کی وجہ سے انہیں کانفرنس گراف کہا جاتا ہے۔ ان کے پیرامیٹرز کم ہو کر کم ہو جاتے ہیں۔ ان کی آئجن ویلیوز ہیں اور، جن کی دونوں ضرب برابر ہیں۔ مزید برآں، اس معاملے میں، v کو دو مربعوں کے مجموعے کے برابر ہونا چاہیے، جو بروک-رائسر-چولا تھیوریم سے متعلق ہے۔ آئجین ویلیوز اور ان کی ضرب کی مزید خصوصیات یہ ہیں:، اس لیے ایک کو آئجین ویلیوز r اور s کے ساتھ دیتے ہوئے، اس کی تکمیل میں آئجین ویلیوز-1-s اور-1-r ہوتی ہیں۔ ضرب کے لیے متبادل مساوات یہ ہیں اور فریم کوشیئنٹ کی حالت: نتیجہ کے طور پر، اگر اور صرف اگر کسی ترتیب میں۔ کرین کے حالات: اور مطلق پابند: اور۔ پنجا بند: اگر، تب یا۔ اگر پیرامیٹرز کے کسی بھی سیٹ کے لیے مذکورہ بالا شرائط کی خلاف ورزی کی جاتی ہے، تو ان پیرامیٹرز کے لیے کوئی باقاعدہ گراف موجود نہیں ہے۔ بروور نے وجود یا عدم وجود کی ایسی فہرستیں یہاں غیر وجود کی وجوہات کے ساتھ مرتب کی ہیں۔ ہوفمین-سنگلٹن تھیوریم جیسا کہ اوپر بیان کیا گیا ہے، آئجن ویلیوز کی ضرب دی گئی ہے جس کے ذریعہ انٹیجر ہونا ضروری ہے۔ 1960 میں، ایلن ہوفمین اور رابرٹ سنگلٹن نے ان تاثرات کا جائزہ لیا جب مور گراف پر لاگو کیا گیا جس میں λ = 0 اور μ = 1 ہے۔ اس طرح کے گراف مثلث سے پاک ہوتے ہیں (بصورت دیگر λ صفر سے تجاوز کر جائے گا) اور چوطرفہ (بصورت دیگر μ 1 سے تجاوز کر جائے گا)، اس لیے ان کا دائرہ (سب سے چھوٹا سائیکل لمبائی) 5 ہوتا ہے۔ مساوات میں λ اور μ کی اقدار کو تبدیل کرتے ہوئے، یہ دیکھا جا سکتا ہے کہ، اور آئجن ویلیو کی ضرب کم ہو کر 1.0 ہو جاتی ہے۔ ضرب کو عدد ہونے کے لیے، مقدار عقلی ہونی چاہیے، اس لیے یا تو عدد صفر ہے یا ڈینومینیٹر ایک عدد ہے۔ اگر عدد صفر ہے، تو امکانات یہ ہیں: k = 0 اور v = 1 ایک سرے کے ساتھ ایک معمولی گراف دیتا ہے اور کوئی کنارے نہیں، اور k = 2 اور v = 5 سے 5-ورٹیکس سائیکل گراف حاصل ہوتا ہے، جو عام طور پر باقاعدہ پینٹاگون کے طور پر تیار کیا جاتا ہے۔ اگر ڈینومینیٹر ایک عدد t ہے، تو ایک کامل مربع ہے، تو۔ متبادل: چونکہ دونوں اطراف انٹیجر ہیں، اس لیے ایک انٹیجر ہونا چاہیے، اس لیے t 15 کا فیکٹر ہے، یعنی۔ بدلے میں: k = 1 اور v = 2 سے دو عمودی حصوں کا ایک معمولی گراف ملتا ہے جو ایک کنارے سے جڑا ہوا ہے، k = 3 اور v = 10 سے پیٹرسن گراف ملتا ہے، k = 7 اور v = 50 سے ہوف مین-سنگلٹن گراف ملتا ہے، جسے ہوف مین اور سنگلٹن نے اس تجزیے کے دوران دریافت کیا، اور k = 57 اور v = 3250 ایک مشہور گراف کی پیش گوئی کرتا ہے جو نہ تو 1960 سے دریافت ہوا ہے، اور نہ ہی اس کے وجود کی تردید کی گئی ہے۔ ہوفمین-سنگلٹن تھیوریم میں کہا گیا ہے کہ اوپر درج کردہ گرافوں کے علاوہ کوئی باقاعدہ گرتھ-5 مور گراف موجود نہیں ہیں۔ جزوی جیومیٹری سیڈل ملحقہ میٹرکس دو گراف نوٹ حوالہ جات اینڈریس بروور اور ہینڈرک وین مالڈیگیم (2022)، مضبوط باقاعدہ گراف بھی دیکھیں۔ کیمبرج: کیمبرج یونیورسٹی پریس۔ ۔ اے۔ ای۔ بروور، اے ایم کوہن، اور اے نیومیئر (1989)، ڈسٹنس ریگولر گراف۔ برلن، نیویارک: سپرنگر-ورلاگ۔ ، کرس گوڈسل اور گورڈن روئل (2004)، الجبرائی گراف تھیوری۔ نیو یارک: سپرنگر-ورلاگ۔ بیرونی روابط ایرک ڈبلیو ویسسٹین، متعدد مثالوں کے ساتھ میتھ ورلڈ مضمون۔ گورڈن روئل، بڑے گرافوں اور خاندانوں کی فہرست۔ اینڈریس ای بروور، مضبوط باقاعدہ گراف کے پیرامیٹرز۔ برینڈن میک کی، گراف کے کچھ مجموعے۔ ٹیڈ اسپینس، زیادہ سے زیادہ 64 چوٹیوں پر مضبوط طور پر باقاعدہ گراف۔ گراف خاندان الجبرائی گراف تھیوری باقاعدہ گراف