Algebraic graph theory
الجبرائی گراف تھیوری ریاضی کی ایک شاخ ہے جس میں گراف کے مسائل پر الجبرائی طریقوں کا اطلاق ہوتا ہے۔ یہ ہندسی، مشترکہ، یا الگورتھمک طریقوں کے برعکس ہے۔ الجبرائی گراف تھیوری کی تین اہم شاخیں ہیں، جن میں لکیری الجبرا کا استعمال، گروپ تھیوری کا استعمال، اور گراف کے غیر متغیرات کا مطالعہ شامل ہے۔ الجبرائی گراف تھیوری کی شاخیں لکیری الجبرا کا استعمال کرتے ہوئے الجبرائی گراف تھیوری کی پہلی شاخ میں لکیری الجبرا کے سلسلے میں گراف کا مطالعہ شامل ہے۔ خاص طور پر، یہ ملحقہ میٹرکس کے سپیکٹرم، یا گراف کے لیپلاشین میٹرکس کا مطالعہ کرتا ہے (الجبرائی گراف تھیوری کے اس حصے کو سپیکٹرم گراف تھیوری بھی کہا جاتا ہے)۔ مثال کے طور پر، پیٹرسن گراف کے لیے، ملحقہ میٹرکس کا سپیکٹرم (−2، −2، −2، −2، 1، 1، 1، 1، 3) ہے۔ کئی تھیوریمز سپیکٹرم کی خصوصیات کو گراف کی دیگر خصوصیات سے جوڑتے ہیں۔ ایک سادہ سی مثال کے طور پر، قطر D کے ساتھ منسلک گراف کے سپیکٹرم میں کم از کم D + 1 الگ الگ اقدار ہوں گی۔ نیٹ ورک کی ہم آہنگی کا تجزیہ کرنے میں گراف سپیکٹرم کے پہلوؤں کا استعمال کیا گیا ہے۔ گروپ تھیوری کا استعمال الجبرائی گراف تھیوری کی دوسری شاخ میں گروپ تھیوری، خاص طور پر آٹومورفزم گروپس اور جیومیٹرک گروپ تھیوری کے سلسلے میں گراف کا مطالعہ شامل ہے۔ ہم آہنگی کی بنیاد پر گراف کے مختلف خاندانوں پر توجہ مرکوز کی جاتی ہے (جیسے سمیٹرک گراف، ورٹیکس-ٹرانزیٹیو گراف، ایج-ٹرانزیٹیو گراف، ڈسٹنس-ٹرانزیٹیو گراف، ڈسٹنس-ریگولر گراف، اور مضبوطی سے باقاعدہ گراف)، اور ان خاندانوں کے درمیان شمولیت کے تعلقات پر۔ گراف کے کچھ زمرے اتنے کم ہیں کہ گراف کی فہرستیں تیار کی جا سکتی ہیں۔ فروخت کے نظریہ کے مطابق، تمام گروہوں کو منسلک گراف (درحقیقت، کیوبک گراف کے) کے آٹومورفزم گروپ کے طور پر پیش کیا جا سکتا ہے۔ گروپ تھیوری کے ساتھ ایک اور تعلق یہ ہے کہ، کسی بھی گروپ کو دیکھتے ہوئے، سمیٹریکل گراف تیار کیے جا سکتے ہیں جنہیں کیلی گراف کہا جاتا ہے، اور ان میں گروپ کی ساخت سے متعلق خصوصیات ہوتی ہیں۔ الجبرائی گراف تھیوری کی یہ دوسری شاخ پہلے سے متعلق ہے، کیونکہ گراف کی ہم آہنگی کی خصوصیات اس کے سپیکٹرم میں جھلکتی ہیں۔ خاص طور پر، پیٹرسن گراف جیسے انتہائی ہم آہنگ گراف کے سپیکٹرم کی چند الگ الگ اقدار ہیں (پیٹرسن گراف میں 3 ہے، جو اس کے قطر کو دیکھتے ہوئے کم از کم ممکن ہے)۔ کیلی گراف کے لیے، سپیکٹرم کا براہ راست تعلق گروپ کی ساخت سے ہو سکتا ہے، خاص طور پر اس کے ناقابل تلافی حروف سے۔ گراف کے غیر متغیرات کا مطالعہ آخر میں، الجبرائی گراف تھیوری کی تیسری شاخ گراف کے غیر متغیرات کی الجبرائی خصوصیات سے متعلق ہے، اور خاص طور پر کرومیٹک کثیرالجہتی، ٹوٹے کثیرالجہتی اور گرہ غیر متغیرات۔ مثال کے طور پر، گراف کا کرومیٹک کثیرالجہتی اس کے مناسب ورٹیکس رنگوں کی تعداد کو شمار کرتا ہے۔ پیٹرسن گراف کے لیے، یہ کثیر الجہتی ہے۔ خاص طور پر، اس کا مطلب یہ ہے کہ پیٹرسن گراف کو ایک یا دو رنگوں سے صحیح طریقے سے رنگین نہیں کیا جا سکتا، لیکن اسے 3 رنگوں کے ساتھ 120 مختلف طریقوں سے رنگا جا سکتا ہے۔ الجبرائی گراف تھیوری کے اس شعبے میں زیادہ تر کام چار رنگ تھیوریم کو ثابت کرنے کی کوششوں سے متاثر ہوا۔ تاہم، اب بھی بہت سے کھلے مسائل ہیں، جیسے کہ گراف کی خصوصیت جس میں ایک ہی کرومیٹک کثیر الجہتی ہے، اور اس بات کا تعین کرنا کہ کون سے کثیر الجہتی کرومیٹک ہیں۔ سپیکٹرل گراف تھیوری الجبرائی امتزاج الجبرائی رابطہ ڈولماج-مینڈلسوہن سڑنا گراف پراپرٹی ایڈجسینسی میٹرکس حوالہ جات بھی دیکھیں۔ بیرونی روابط