Graph canonization
گراف تھیوری میں، ریاضی کی ایک شاخ، گراف کینونائزیشن ایک دیئے گئے گراف جی کی کینونکل شکل کو تلاش کرنے کا مسئلہ ہے۔ ایک کینونکل شکل ایک لیبل شدہ گراف کینن (جی) ہے جو جی کے لیے آئسومورفک ہے، اس طرح کہ ہر گراف جو جی کے لیے آئسومورفک ہے، جی کی طرح ایک ہی کینونکل شکل رکھتا ہے۔ اس طرح، گراف کینونائزیشن کے مسئلے کے حل سے، کوئی بھی گراف آئسومورفزم کے مسئلے کو بھی حل کر سکتا ہے: یہ جانچنے کے لیے کہ آیا دو گراف جی اور ایچ آئسومورفک ہیں، ان کی کینونکل شکلوں کینن (جی) اور کینن (ایچ) کا حساب لگائیں، اور جانچ کریں کہ آیا یہ دونوں کینونکل شکلیں ایک جیسی ہیں۔ گراف کی کینونکل شکل ایک مکمل گراف غیر متغیر کی ایک مثال ہے: ہر دو آئسومورفک گراف کی ایک ہی کینونکل شکل ہوتی ہے، اور ہر دو غیر آئسومورفک گراف کی مختلف کینونکل شکلیں ہوتی ہیں۔ اس کے برعکس، گراف کے ہر مکمل غیر متغیر کو کینونکل فارم کی تعمیر کے لیے استعمال کیا جا سکتا ہے۔ این-ورٹیکس گراف کے ورٹیکس سیٹ کی شناخت 1 سے این تک کے انٹیجرز کے ساتھ کی جا سکتی ہے، اور اس طرح کی شناخت کا استعمال کرتے ہوئے گراف کی کینونکل شکل کو اس کے عمودی حصوں کی ترتیب کے طور پر بھی بیان کیا جا سکتا ہے۔ گراف کی کینونکل شکلوں کو کینونکل لیبلنگ بھی کہا جاتا ہے، اور گراف کینونائزیشن کو بعض اوقات گراف کینونکلائزیشن بھی کہا جاتا ہے۔ کمپیوٹیشنل پیچیدگی واضح طور پر، گراف کینونائزیشن کا مسئلہ کم از کم کمپیوٹیشنل طور پر اتنا ہی مشکل ہے جتنا کہ گراف آئسومورفزم کا مسئلہ۔ درحقیقت، گراف آئسومورفزم گراف کینونائزیشن کے لیے یہاں تک کہ AC0-کم کرنے کے قابل ہے۔ تاہم، یہ اب بھی ایک کھلا سوال ہے کہ آیا یہ دونوں مسائل کثیر الجہتی وقت کے مساوی ہیں۔ اگرچہ گراف آئسومورفزم کے لیے (تعیناتی) کثیر الجہتی الگورتھم کا وجود اب بھی کمپیوٹیشنل پیچیدگی کے نظریہ میں ایک کھلا مسئلہ ہے، 1977 میں لاسزلو بابائی نے اطلاع دی کہ امکان کے ساتھ کم از کم 1 − ایکسپ (−O (n))، ایک سادہ ورٹیکس درجہ بندی الگورتھم صرف دو اصلاحات کے مراحل کے بعد تمام n-ورٹیکس گرافوں کے سیٹ سے بے ترتیب طور پر یکساں طور پر منتخب کردہ گراف کی کینونکل لیبلنگ تیار کرتا ہے۔ چھوٹی تبدیلیاں اور ایک اضافی ڈیپتھ-فرسٹ سرچ مرحلہ لکیری متوقع وقت میں اس طرح کے یکساں طور پر منتخب بے ترتیب گرافوں کی کینونکل لیبلنگ پیدا کرتا ہے۔ یہ نتیجہ اس حقیقت پر کچھ روشنی ڈالتا ہے کہ کیوں بہت سے رپورٹ شدہ گراف آئسومورفزم الگورتھم عملی طور پر اچھا برتاؤ کرتے ہیں۔ یہ امکانی پیچیدگی کے نظریہ میں ایک اہم پیشرفت تھی جو اپنے مخطوطات کی شکل میں وسیع پیمانے پر مشہور ہوئی اور جسے سمپوزیم میں رپورٹ کیے جانے کے کافی عرصے بعد بھی "غیر شائع شدہ مخطوطات" کے طور پر حوالہ دیا گیا۔ ایک عام طور پر معروف کینونکل شکل آئسومورفزم کلاس کے اندر لیکسیگرافک طور پر سب سے چھوٹا گراف ہے، جو لیکسیگرافک طور پر سب سے چھوٹے ملحقہ میٹرکس کے ساتھ کلاس کا گراف ہے جسے لکیری سٹرنگ سمجھا جاتا ہے۔ تاہم، لغت کے لحاظ سے سب سے چھوٹے گراف کی گنتی این پی-ہارڈ ہے۔ درختوں کے لیے، ایک جامع کثیر الجہتی کینونائزیشن الگورتھم پیش کیا جاتا ہے جس میں O (n) جگہ کی ضرورت ہوتی ہے۔ ہر سرے پر سٹرنگ 01 کا لیبل لگا کر شروع کریں۔ ہر غیر پتی x کے لیے بار بار x کے لیبل سے لیڈنگ 0 اور ٹریلنگ 1 کو ہٹا دیں ؛ پھر x کے لیبل کو تمام ملحقہ پتوں کے لیبل کے ساتھ لغت کی ترتیب میں ترتیب دیں۔ ان ترتیب شدہ لیبلز کو مربوط کریں، ایک لیڈنگ 0 اور ٹریلنگ 1 کو دوبارہ شامل کریں، اسے x کا نیا لیبل بنائیں، اور ملحقہ پتوں کو حذف کریں۔ اگر دو عمودی حصے باقی ہیں، تو ان کے لیبل کو لغت کی ترتیب میں جوڑ دیں۔ ایپلی کیشنز گراف کینونائزیشن بہت سے گراف آئسومورفزم الگورتھم کا جوہر ہے۔ اہم ٹولز میں سے ایک Nauty ہے۔ گراف کینونائزیشن کا ایک عام اطلاق گرافیکل ڈیٹا مائننگ میں ہے، خاص طور پر کیمیائی ڈیٹا بیس ایپلی کیشنز میں۔ کیمیائی مادوں کے لیے متعدد شناخت کار، جیسے کہ ایس ایم آئی ایل ای ایس اور آئی این سی ایچ آئی اپنے حساب میں کینونکلائزیشن کے مراحل استعمال کرتے ہیں، جو بنیادی طور پر گراف کی کینونکلائزیشن ہے جو مالیکیول کی نمائندگی کرتا ہے۔ یہ شناخت کار سالماتی معلومات کو انکوڈ کرنے اور ڈیٹا بیس اور ویب پر ایسی معلومات کی تلاش کو آسان بنانے کے لیے ایک معیاری (اور بعض اوقات انسان کے پڑھنے کے قابل) طریقہ فراہم کرنے کے لیے ڈیزائن کیے گئے ہیں۔ حوالہ جات گراف تھیوری