Hajós construction
گراف تھیوری میں، ریاضی کی ایک شاخ، ہاجوس کنسٹرکشن گرافوں پر ایک عمل ہے جس کے نام پر رکھا گیا ہے جسے کسی بھی تنقیدی گراف یا کسی بھی گراف کی تعمیر کے لیے استعمال کیا جا سکتا ہے جس کا کرومیٹک نمبر کم از کم کچھ دی گئی حد ہے۔ تعمیر دو غیر ہدایت شدہ گراف ہونے دیں، ایک کنارے ہونے دیں، اور ایک کنارے ہونے دیں۔ پھر ہاجوس کی تعمیر ایک نیا گراف بناتی ہے جو دونوں گرافوں کو عمودی اور ایک واحد سرے میں شناخت کرکے، دونوں کناروں کو ہٹا کر اور ایک نیا کنارہ شامل کرکے جوڑتی ہے۔ مثال کے طور پر، ہر ایک کو چار عمودی حصوں پر ایک مکمل گراف ہونے دیں ؛ ان گرافوں کی ہم آہنگی کی وجہ سے، ان میں سے ہر ایک میں سے کس کنارے کا انتخاب کرنا غیر اہم ہے۔ اس صورت میں، ہاجوس کی تعمیر کو لاگو کرنے کا نتیجہ موزر اسپنڈل ہے، جو سات ورٹیکس یونٹ کا فاصلہ گراف ہے جس کے لیے چار رنگوں کی ضرورت ہوتی ہے۔ ایک اور مثال کے طور پر، اگر اور بالترتیب لمبائی کے سائیکل گراف ہیں، تو ہاجوس کی تعمیر کو لاگو کرنے کا نتیجہ خود لمبائی کا ایک سائیکل گراف ہے۔ تعمیری گراف ایک گراف کو-تعمیری (یا ہاجوس-تعمیری) کہا جاتا ہے جب یہ مندرجہ ذیل تین طریقوں میں سے کسی ایک میں تشکیل پاتا ہے: مکمل گراف-تعمیری ہے۔ کسی بھی دو تعمیری گراف کو ہونے دیں۔ پھر ہاجوس کی تعمیر کو لاگو کرکے بنایا گیا گراف-قابل تعمیر ہے۔ کوئی بھی-تشکیل پذیر گراف ہونے دیں، اور کسی بھی دو غیر ملحقہ عمودی حصوں کو اندر ہونے دیں۔ پھر یکجا کرکے اور ایک ہی سرے میں تشکیل پانے والا گراف بھی-تشکیل پذیر ہوتا ہے۔ اسی طرح، یہ گراف گراف میں کنارے کو شامل کرکے اور پھر اسے سکڑ کر بنایا جا سکتا ہے۔ رنگ کاری سے تعلق اس بات کی تصدیق کرنا سیدھا ہے کہ ہر تشکیل پذیر گراف کو کسی بھی مناسب گراف رنگ کاری میں کم از کم رنگوں کی ضرورت ہوتی ہے۔ درحقیقت، یہ مکمل گراف کے لیے واضح ہے، اور دو غیر ملحقہ چوٹیوں کی شناخت کا اثر انہیں کسی بھی رنگ میں ایک دوسرے کے جیسا رنگ رکھنے پر مجبور کرنا ہے، ایسی چیز جو رنگوں کی تعداد کو کم نہیں کرتی ہے۔ ہاجوس کی تعمیر میں ہی، نیا کنارہ کم از کم دو عمودی حصوں میں سے ایک کو مجبور کرتا ہے اور اس کے لیے مشترکہ عمودی سے مختلف رنگ رکھتا ہے، لہذا مشترکہ گراف کا کوئی بھی مناسب رنگ ان دو چھوٹے گرافوں میں سے کسی ایک کے مناسب رنگ کا باعث بنتا ہے جس سے یہ بنا تھا، جس کی وجہ سے اسے دوبارہ رنگوں کی ضرورت ہوتی ہے۔ ہاجوس نے زیادہ مضبوطی سے ثابت کیا کہ گراف میں کم از کم رنگوں کی ضرورت ہوتی ہے، کسی بھی مناسب رنگ میں، اگر اور صرف اس صورت میں جب اس میں ذیلی گراف کے طور پر-تشکیل پذیر گراف موجود ہو۔ مساوی طور پر، ہر اہم گراف (ایک ایسا گراف جس کے لیے رنگوں کی ضرورت ہوتی ہے لیکن جس کے لیے ہر مناسب ذیلی گراف کو کم رنگوں کی ضرورت ہوتی ہے)-تشکیل پذیر ہوتا ہے۔ متبادل طور پر، ہر گراف جس میں رنگوں کی ضرورت ہوتی ہے اسے ہاجوس کی تعمیر، کسی بھی دو غیر ملحقہ عمودی کی شناخت کرنے کا عمل، اور دیئے گئے گراف میں ایک عمودی یا کنارے کو شامل کرنے کی کارروائیوں کو مکمل گراف سے شروع کرکے تشکیل دیا جا سکتا ہے۔ رنگنے کی جگہ فہرست رنگنے کے لیے اسی طرح کی تعمیر کا استعمال کیا جا سکتا ہے۔ تنقیدی گراف کی تعمیر پذیری اس لیے کہ ہر اہم گراف (یعنی ہر عجیب چکر) کو اس طرح تشکیل پزیر گراف کے طور پر تیار کیا جا سکتا ہے کہ اس کی تعمیر میں بنے تمام گراف بھی اہم ہوں۔ کیونکہ، یہ سچ نہیں ہے: ایک گراف جسے ہاجوس کے قیاس کے جوابی مثال کے طور پر پایا جاتا ہے کہ-کرومیٹک گراف کی ذیلی تقسیم ہوتی ہے، اس مسئلے کی جوابی مثال کے طور پر بھی کام کرتا ہے۔ اس کے بعد، سب کے لیے-اہم لیکن غیر-تشکیل پذیر گراف صرف-اہم گراف کے ذریعے پائے گئے۔ کیونکہ دو غیر ملحقہ عمودی حصوں کو ضم کرنے سے نتیجے میں گراف میں عمودی حصوں کی تعداد کم ہو جاتی ہے، اس لیے کسی دیے گئے گراف کی نمائندگی کرنے کے لیے درکار کارروائیوں کی تعداد، جس میں ہاجوس کے ذریعے بیان کردہ کارروائیوں کو استعمال کرتے ہوئے عمودی حصوں کی تعداد سے تجاوز کر سکتی ہے، ایسی ہی ایک مثال ڈوڈیکاہڈرون گراف سے حاصل کردہ گراف ہے جس میں اینٹی پوڈل عمودی حصوں کے ہر جوڑے کے درمیان ایک نیا کنارہ شامل کیا جاتا ہے۔ مزید خاص طور پر، کرومیٹک گراف کے ہاجوس نمبر کو کم سے کم ان مراحل کی تعداد کے طور پر بیان کریں جن سے تعمیر کرنے کی ضرورت ہوتی ہے، جہاں ہر قدم پہلے سے تشکیل شدہ دو گرافوں کو ملا کر، پہلے سے تشکیل شدہ گراف کے دو غیر ملحقہ عمودی حصوں کو ضم کرکے، یا پہلے سے تشکیل شدہ گراف میں ایک عمودی یا کنارے کو شامل کرکے ایک نیا گراف بناتا ہے۔ انہوں نے دکھایا کہ، کناروں کے ساتھ-ورٹیکس گراف کے لیے،۔ اگر ہر گراف میں کثیر الجہتی ہاجوس نمبر ہے، تو اس کا مطلب یہ ہوگا کہ غیر متعین کثیر الجہتی وقت میں غیر رنگین ثابت کرنا ممکن ہے، اور اس وجہ سے یہ ظاہر ہوتا ہے کہ NP = شریک-NP، ایک ایسا نتیجہ جسے پیچیدگی کے تھیوریسٹوں کے ذریعہ ناممکن سمجھا جاتا ہے۔ تاہم، یہ معلوم نہیں ہے کہ کچھ پیچیدگی-نظریاتی مفروضہ بنائے بغیر ہاجوس نمبر پر غیر کثیر الجہتی نچلی حدود کو کیسے ثابت کیا جائے، اور اگر اس طرح کی حد کو ثابت کیا جا سکتا ہے تو یہ ریاضیاتی منطق میں فریج سسٹم کی بعض اقسام پر غیر کثیرالجہتی حدود کے وجود کو بھی ظاہر کرے گا۔ کسی دیے گئے گراف کے لیے ہاجوس کی تعمیر کو بیان کرنے والے ایکسپریشن ٹری کا کم از کم سائز ہاجوس کی تعداد سے نمایاں طور پر بڑا ہو سکتا ہے، کیونکہ ایک مختصر ترین اظہار ایک ہی گراف کو متعدد بار دوبارہ استعمال کر سکتا ہے، ایک ایسی معیشت جس کی ایکسپریشن ٹری میں اجازت نہیں ہے۔ 3 کرومیٹک گراف موجود ہیں جن کے لیے اس طرح کے سب سے چھوٹے ایکسپریشن ٹری کا سائز تیز ہوتا ہے۔ دیگر ایپلی کیشنز نے 4 اہم پولی ہیڈرل گرافوں کا ایک لامحدود سیٹ تیار کرنے کے لیے ہاجوس کی تعمیر کا استعمال کیا، جن میں سے ہر ایک میں عمودی سے دوگنا سے زیادہ کنارے ہوتے ہیں۔ اسی طرح، تعمیر کا استعمال کیا، گرٹزش گراف سے شروع کرتے ہوئے، بہت سے 4-اہم مثلث سے پاک گراف تیار کرنے کے لیے، جن کو انہوں نے روایتی بیک ٹریکنگ الگورتھم کا استعمال کرتے ہوئے رنگنا مشکل دکھایا۔ پولی ہیڈرل کمبینٹوریکس میں، مستحکم سیٹ پولیٹوپ کے پہلوؤں کو پیدا کرنے کے لیے ہاجوس کی تعمیر کا استعمال کیا گیا۔ حوالہ جات نوٹ کریں۔ ۔ ۔ ۔ ۔ جیسا کہ حوالہ دیا گیا ہے۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ گراف آپریشنز گراف کلرنگ