Moser spindle
گراف تھیوری میں، ریاضی کی ایک شاخ، موزر اسپنڈل (جسے موزرز اسپنڈل یا موزر گراف بھی کہا جاتا ہے) ایک غیر ہدایت شدہ گراف ہے، جس کا نام ریاضی دان لیو موزر اور اس کے بھائی ولیم کے نام پر رکھا گیا ہے، جس میں سات عمودی اور گیارہ کنارے ہیں۔ یہ ایک یونٹ ڈسٹنس گراف ہے جس میں کسی بھی گراف کے رنگ میں چار رنگوں کی ضرورت ہوتی ہے، اور اس کے وجود کو یہ ثابت کرنے کے لیے استعمال کیا جا سکتا ہے کہ طیارہ کا کرومیٹک نمبر کم از کم چار ہے۔ موزر تکلے کو گیوگی ہاجوس کے بعد ہاجوس گراف بھی کہا جاتا ہے، کیونکہ اسے ہاجوس کی تعمیر کی ایک مثال کے طور پر دیکھا جا سکتا ہے۔ تاہم، نام "ہاجوس گراف" کا اطلاق ایک مختلف گراف پر بھی کیا گیا ہے، جو ایک مسدس کے اندر کندہ مثلث کی شکل میں ہے۔ یونٹ ڈسٹنس گراف کی تعمیر کے طور پر، موزر اسپنڈل 60 اور 120 ڈگری کے زاویوں کے ساتھ دو رومبی سے بنتا ہے، تاکہ رومبی کے اطراف اور چھوٹے ترچھے مساوی مثلث تشکیل دیں۔ دونوں رومبی کو ہوائی جہاز میں رکھا جاتا ہے، جو اپنے ایک تیز زاویے والے عمودی حصے کو اس طرح بانٹتے ہیں کہ باقی دو تیز زاویے والے عمودی حصے ایک دوسرے سے ایک یونٹ کا فاصلہ رکھتے ہیں۔ گراف کے گیارہ کناروں میں آٹھ رومبس اطراف، رومبی کے دو چھوٹے ترچھا، اور تیز زاویے والے عمودی حصوں کی اکائی فاصلے کی جوڑی کے درمیان کا کنارہ شامل ہیں۔ موزر اسپنڈل کو جیومیٹرک ایمبیڈنگ کے حوالے کے بغیر، نظریاتی طور پر گراف بھی بنایا جا سکتا ہے، جس میں چار عمودی حصوں پر دو مکمل گرافوں سے شروع ہونے والی ہجس کی تعمیر کا استعمال کیا جاتا ہے۔ یہ تعمیر ہر مکمل گراف سے ایک کنارے کو ہٹا دیتی ہے، ہٹائے گئے کناروں کے دو اختتامی نکات کو دونوں گروہوں کے اشتراک سے ایک واحد سرے میں ضم کر دیتی ہے، اور ہٹائے گئے کنارے کے باقی دو اختتامی نکات کو جوڑنے والے ایک نئے کنارے کا اضافہ کرتی ہے۔ موزر اسپنڈل کی تعمیر کا ایک اور طریقہ یوٹیلیٹی گراف K3,3 سے اس کے ایک کنارے کو ذیلی تقسیم کرکے بنائے گئے گراف کے تکمیل گراف کے طور پر ہے۔ ہاڈوگر-نیلسن مسئلہ پر اطلاق ہاڈوگر-نیلسن مسئلہ یہ پوچھتا ہے کہ یوکلڈین سطح کے نکات کو اس طرح رنگنے کے لیے کتنے رنگوں کی ضرورت ہوتی ہے کہ ایک دوسرے سے اکائی فاصلے پر موجود نکات کے ہر جوڑے کو مختلف رنگ تفویض کیے جائیں۔ یعنی یہ لامحدود گراف کا کرومیٹک نمبر مانگتا ہے جس کے عمودی حصے سطح کے تمام نکات ہوتے ہیں اور جس کے کنارے یونٹ فاصلے پر تمام نکات کے جوڑے ہوتے ہیں۔ موزر اسپنڈل کو کسی بھی گراف کے رنگ میں چار رنگوں کی ضرورت ہوتی ہے: دو رومبی میں سے کسی ایک کے تین رنگوں میں جس سے یہ تشکیل پاتا ہے، رومبی کے دو تیز زاویے والے عمودی حصے لازمی طور پر ایک دوسرے کے رنگ کے ہوتے ہیں۔ لیکن اگر دونوں رومبی کے مشترکہ سرے کا رنگ دو مخالف تیز زاویے والے سرے کے رنگ جیسا ہے، تو یہ دونوں سرے ایک دوسرے کے رنگ کے ہوتے ہیں، اس ضرورت کی خلاف ورزی کرتے ہوئے کہ ان کو جوڑنے والے کنارے میں مختلف رنگ کے اختتامی نکات ہوں۔ اس تضاد سے پتہ چلتا ہے کہ تین رنگ ناممکن ہیں، اس لیے کم از کم چار رنگ ضروری ہیں۔ موزر تکلے کو رنگنے کے لیے چار رنگ بھی کافی ہیں، ایک حقیقت جو مثال کے طور پر اس حقیقت سے ملتی ہے کہ اس کی انحطاط تین ہے۔ اس بات کا ایک متبادل ثبوت کہ موزر تکلے کے لیے چار رنگوں کی ضرورت ہوتی ہے، ہاجوس کی تعمیر سے ملتا ہے۔ دونوں مکمل گراف جن سے موزر تکلا بنتا ہے ان کے لیے چار رنگوں کی ضرورت ہوتی ہے، اور ہاجوس کی تعمیر اس خاصیت کو محفوظ رکھتی ہے۔ اس سے بھی زیادہ براہ راست، موزر اسپنڈل میں ہر آزاد سیٹ میں زیادہ سے زیادہ دو عمودی ہوتے ہیں، لہذا یہ تمام سات عمودی حصوں کا احاطہ کرنے کے لیے کم از کم چار آزاد سیٹ لیتا ہے۔ چونکہ موزر تکلا طیارہ کے لامحدود اکائی فاصلے کے گراف کا ذیلی گراف ہے، اس لیے ہوائی جہاز کے گراف کو بھی کسی بھی رنگ میں کم از کم چار رنگوں کی ضرورت ہوتی ہے۔ ڈی بروجن-ایرڈس تھیوریم کے مطابق (اس مفروضے کے ساتھ کہ انتخاب کا محور درست ہے)، طیارہ کا کرومیٹک نمبر اس کے کسی بھی محدود ذیلی گراف کے سب سے بڑے کرومیٹک نمبر کے برابر ہے۔ 2018 میں 5 کرومیٹک یونٹ ڈسٹنس گراف کے خاندان کی دریافت ہونے تک، لامحدود یونٹ ڈسٹنس گراف کا کوئی ذیلی گراف نہیں ملا تھا جس کے لیے موزر اسپنڈل سے زیادہ رنگوں کی ضرورت ہو۔ تاہم، طیارہ کے کرومیٹک نمبر کے لیے سب سے بہترین اوپری حد سات ہے، جو موزر اسپنڈل کے لیے درکار رنگوں کی تعداد سے نمایاں طور پر زیادہ ہے۔ دیگر خصوصیات اور ایپلی کیشنز موزر اسپنڈل ایک پلانر گراف ہے، جس کا مطلب ہے کہ اسے ہوائی جہاز میں کراسنگ کے بغیر کھینچا جا سکتا ہے۔ تاہم، سیدھی لکیر کے کناروں کے ساتھ ایسی ڈرائنگ بنانا ممکن نہیں ہے جو یونٹ ڈسٹنس ڈرائنگ بھی ہو ؛ یعنی یہ میچ اسٹک گراف نہیں ہے۔ موزر اسپنڈل بھی ایک لامان گراف ہے، جس کا مطلب ہے کہ جب یہ جہاز میں سرایت کرتا ہے تو یہ کم سے کم سخت نظام بناتا ہے۔ پلانر لامان گراف کے طور پر، یہ ایک نکیلی سیڈو ٹرینگولشن کا گراف ہے، جس کا مطلب ہے کہ اسے جہاز میں اس طرح سے سرایت کیا جا سکتا ہے کہ غیر محدود چہرہ سرایت کا کنویکس ہل ہو اور ہر پابند چہرہ ایک سیڈو ٹرینگل ہو جس میں صرف تین کنویکس عمودی ہوں۔ موزر گراف کا تکمیل گراف مثلث سے پاک گراف ہے۔ اس طرح، موزر گراف کی یونٹ ڈسٹنس ایمبیڈنگ کو طیارہ میں سات پوائنٹس رکھنے کے مسئلے کو اس طرح حل کرنے کے لیے استعمال کیا جا سکتا ہے کہ ہر تین پوائنٹس میں ایک دوسرے سے یونٹ فاصلے پر کم از کم ایک جوڑا ہو۔ موزر تکلے میں کسی بھی کنارے کو شامل کرنے کے نتیجے میں ایک ایسا گراف بنتا ہے جسے طیارہ میں یونٹ ڈسٹنس گراف کے طور پر سرایت نہیں کیا جا سکتا، اور موزر تکلے سے لے کر کسی چھوٹے یونٹ ڈسٹنس گراف تک کوئی گراف ہومومورفزم موجود نہیں ہے۔ موزر اسپنڈل کی ان دو خصوصیات کو جانچ کی این پی سختی کو ظاہر کرنے کے لیے استعمال کیا گیا تھا کہ آیا کسی دیئے گئے گراف میں دو جہتی یونٹ فاصلے کی نمائندگی ہے۔ ثبوت 3 ایس اے ٹی سے کمی کا استعمال کرتا ہے جس میں موزر اسپنڈل کو کمی میں مرکزی سچائی ترتیب دینے والے گیجٹ کے طور پر استعمال کیا جاتا ہے۔ موزر اسپنڈل کو یوکلڈین رمسی تھیوری میں نتیجہ ثابت کرنے کے لیے بھی استعمال کیا جا سکتا ہے: اگر T طیارہ میں کوئی مثلث ہے، اور طیارہ کے نکات دو رنگ کے سیاہ اور سفید ہیں، تو یا تو T کا سیاہ ترجمہ ہوتا ہے یا ایک دوسرے سے اکائی فاصلے پر سفید نکات کا جوڑا ہوتا ہے۔ کیونکہ، M کو موزر تکلے کی اکائی فاصلے کی سرایت ہونے دیں، اور M + T کو M اور T کا منکوسکی مجموعہ ہونے دیں۔ اگر M + T کا کوئی سفید اکائی فاصلے کا جوڑا نہیں ہے، تو M + T میں موزر تکلے کی تین کاپیوں میں سے ہر ایک میں زیادہ سے زیادہ دو سفید نکات ہونے چاہئیں، کیونکہ ہر کاپی میں سفید نکات کو ایک آزاد سیٹ بنانا چاہیے اور موزر تکلے میں سب سے بڑے آزاد سیٹ کا سائز دو ہونا چاہیے۔ لہذا، موزر تکلے کے سات عمودی حصوں میں سے، زیادہ سے زیادہ چھ ایسے ہیں جن کی سفید کاپی M + T میں ہے، لہذا سات عمودی حصوں میں سے ایک ہونا ضروری ہے جس کی تمام کاپیاں کالی ہوں۔ لیکن پھر اس ورٹیکس کی تین کاپیاں ٹی کا ترجمہ بناتی ہیں۔ یہ بھی دیکھیں گولمب گراف حوالہ جات بیرونی لنکس انفرادی گراف پلانر گراف