Hadwiger conjecture (graph theory)
گراف تھیوری میں، ہاڈوگر قیاس یہ بتاتا ہے کہ اگر لوپ لیس ہے اور اس میں کوئی معمولی نہیں ہے تو اس کا کرومیٹک نمبر مطمئن کرتا ہے۔ یہ قیاس چار رنگوں کے نظریہ کی عمومی شکل ہے اور اسے میدان میں سب سے اہم اور چیلنجنگ کھلے مسائل میں سے ایک سمجھا جاتا ہے۔ مزید تفصیل سے، اگر کسی غیر ہدایت شدہ گراف کے تمام مناسب رنگ یا زیادہ رنگ استعمال کرتے ہیں، تو کوئی اس طرح کے جداگانہ منسلک ذیلی گراف تلاش کر سکتا ہے کہ ہر ذیلی گراف ایک دوسرے کے ذیلی گراف سے ایک کنارے سے جڑا ہو۔ ان ذیلی گرافوں میں سے ہر ایک کے اندر کناروں کو سکڑنا تاکہ ہر ذیلی گراف ایک ہی سرے پر گر جائے، یہ قیاس، چار رنگوں کے مسئلے کی ایک دور رس عمومی شکل، ہیوگو ہاڈویگر نے 1943 میں بنایا تھا اور اب بھی حل نہیں ہوا ہے۔ اسے "گراف تھیوری میں سب سے گہرے غیر حل شدہ مسائل میں سے ایک" کہتے ہیں۔ مساوی شکلیں ہاڈوگر قیاس کی ایک مساوی شکل (اوپر بیان کردہ شکل کا متضاد) یہ ہے کہ، اگر کنارے کے سکڑنے کا کوئی سلسلہ نہیں ہے (ہر ایک کسی کنارے کے دو اختتامی نکات کو ایک ہی سپر ورٹیکس میں ضم کرتا ہے) جو ایک گراف کو مکمل طور پر لاتا ہے تو اس میں رنگوں کے ساتھ ورٹیکس رنگ ہونا ضروری ہے۔ کم سے کم کسی بھی سکڑنے میں رنگ کی ہر کلاس ایک ہی سرے پر ایک مکمل سکڑ پیدا کرے گی تاہم، یہ سکڑنے کا عمل معمولی پیدا نہیں کرتا ہے کیونکہ (تعریف کے مطابق) ایک ہی رنگ کی کلاس میں کسی بھی دو سرے کے درمیان کوئی کنارہ نہیں ہوتا ہے، اس طرح سکڑنا کنارے کا سکڑنا نہیں ہے (جو نابالغوں کے لیے ضروری ہے)۔ ہاڈویگر کے قیاس میں کہا گیا ہے کہ عمودی حصوں کے سیٹوں کو ایک ہی عمودی حصوں پر مناسب طریقے سے کنکریکٹ کرنے کا ایک مختلف طریقہ موجود ہے، جس سے مکمل طور پر اس طرح پیدا ہوتا ہے کہ تمام کنکریکٹ شدہ سیٹ جڑے ہوئے ہوں۔ اگر گراف کے خاندان کی نشاندہی کرتا ہے جس کی خاصیت یہ ہے کہ گراف کے تمام نابالغ ہو سکتے ہیں تو یہ رابرٹسن-سیمور تھیوریم کی پیروی کرتا ہے جس کی خصوصیت ممنوعہ نابالغوں کے ایک محدود سیٹ سے کی جا سکتی ہے۔ ہاڈوگر کا قیاس یہ ہے کہ یہ سیٹ ایک ہی ممنوع سیٹ پر مشتمل ہے۔ گراف کا ہاڈوگر نمبر سب سے بڑے مکمل گراف کا سائز ہے جو معمولی ہے (یا مساوی طور پر کنکریکٹ کنج سے حاصل کیا جا سکتا ہے۔ اسے سنکچن کلک نمبر بھی کہا جاتا ہے۔ ہاڈوگر قیاس کو سادہ الجبرائی شکل میں بیان کیا جا سکتا ہے جہاں کرومیٹک نمبر کی نشاندہی ہوتی ہے۔ خاص معاملات اور جزوی نتائج۔ معاملہ معمولی ہے: گراف کو ایک سے زیادہ رنگوں کی ضرورت ہوتی ہے اگر اور صرف اس صورت میں جب اس کا کنج ہو، اور وہ کنج خود معمولی ہو۔ معاملہ بھی آسان ہے: تین رنگوں کی ضرورت والے گراف غیر بپارٹائٹ گراف ہوتے ہیں، اور ہر غیر بپارٹائٹ گراف میں ایک عجیب سائیکل ہوتا ہے، جسے 3 سائیکل یعنی ایک معمولی سائیکل میں معاہدہ کیا جا سکتا ہے۔ اسی مقالے میں جس میں انہوں نے قیاس پیش کیا، ہاڈوگر نے اس کی سچائی کو ثابت کیا۔ جن گرافوں میں کوئی معمولی بات نہیں ہے وہ سیریز متوازی گراف اور ان کے ذیلی گراف ہیں۔ اس قسم کے ہر گراف میں زیادہ سے زیادہ دو واقع کناروں کے ساتھ ایک ورٹیکس ہوتا ہے۔ کوئی بھی اس طرح کے کسی ایک ورٹیکس کو ہٹا کر، بقیہ گراف کو بار بار رنگ دے کر، اور پھر ہٹائے گئے ورٹیکس کو جوڑ کر اور رنگ کر کے اس طرح کے کسی بھی گراف کو 3 رنگ دے سکتا ہے۔ چونکہ ہٹائے گئے ورٹیکس کے زیادہ سے زیادہ دو کنارے ہوتے ہیں، اس لیے جب ورٹیکس کو دوبارہ شامل کیا جائے گا تو تین رنگوں میں سے ایک اسے رنگنے کے لیے ہمیشہ دستیاب رہے گا۔ قیاس کی سچائی چار رنگوں کے نظریہ کو ظاہر کرتی ہے: کیونکہ، اگر قیاس درست ہے، تو پانچ یا اس سے زیادہ رنگوں کی ضرورت والے ہر گراف میں ایک معمولی ہوگا اور (ویگنر کے نظریہ کے مطابق) غیر پلینر ہوگا۔ کلاؤس ویگنر نے 1937 میں ثابت کیا کہ یہ معاملہ دراصل چار رنگوں کے نظریہ کے مساوی ہے اور اس لیے اب ہم جانتے ہیں کہ یہ درست ہے۔ جیسا کہ ویگنر نے دکھایا، ہر گراف جس میں کوئی معمولی نہیں ہے اسے کلیک سمز کے ذریعے ٹکڑوں میں تقسیم کیا جا سکتا ہے جو یا تو پلینر یا 8-ورٹیکس موبیئس سیڑھی ہیں، اور ان میں سے ہر ٹکڑا ایک دوسرے سے آزادانہ طور پر 4 رنگ کا ہو سکتا ہے، لہذا-مائنر فری گراف کی 4 رنگت ہر پلینر ٹکڑے کی 4 رنگت سے ملتی ہے۔ چار رنگوں کے نظریہ کا استعمال کرتے ہوئے بھی قیاس کو ثابت کیا۔ اس ثبوت کے ساتھ ان کے مقالے نے 1994 کا فلکرسن انعام جیتا۔ یہ ان کے ثبوت سے ملتا ہے کہ لنک لیس ایمبیڈ ایبل گراف، پلانر گراف کے تین جہتی اینالاگ، میں زیادہ سے زیادہ پانچ کرومیٹک نمبر ہوتے ہیں۔ اس نتیجے کی وجہ سے، قیاس درست معلوم ہوتا ہے لیکن یہ اس کے لیے حل نہیں ہوتا ہے کیونکہ، کچھ جزوی نتائج معلوم ہوتے ہیں: ہر 7-کرومیٹک گراف میں یا تو ایک معمولی یا ایک نابالغ اور ایک نابالغ دونوں ہونا چاہیے۔ ہر گراف میں زیادہ تر واقع کناروں کے ساتھ ایک ورٹیکس ہوتا ہے، جس سے یہ پتہ چلتا ہے کہ ایک لالچی رنگ الگورتھم جو اس نچلے درجے کے ورٹیکس کو ہٹاتا ہے، باقی گراف کو رنگ دیتا ہے، اور پھر ہٹائے گئے ورٹیکس کو واپس جوڑتا ہے اور اسے رنگ دیتا ہے، دیئے گئے گراف کو رنگوں سے رنگ دے گا۔ 1980 کی دہائی میں، الیگزینڈر وی کوسٹوچکا اور اینڈریو تھامسن دونوں نے آزادانہ طور پر ثابت کیا کہ ہر گراف جس میں کوئی معمولی نہیں ہے اس کی اوسط ڈگری ہوتی ہے اور اس طرح اسے رنگوں کا استعمال کرتے ہوئے رنگا جا سکتا ہے۔ اس باؤنڈ میں بہتری کے سلسلے کی وجہ سے گرافوں کے لیے-رنگین ہونے کا اعلان کیا گیا ہے جس میں عمومی کاری کے بغیر گیوگی ہاجوس نے قیاس کیا کہ ہاڈویگر کے قیاس کو نابالغوں کے بجائے ذیلی تقسیم میں مضبوط کیا جا سکتا ہے: یعنی، کہ رنگین نمبر والے ہر گراف میں ایک مکمل ہاجوس کے قیاس کی ذیلی تقسیم ہوتی ہے جو درست ہے لیکن اس مضبوط قیاس آرائی کے خلاف مثالیں ملتی ہیں اور مشاہدہ کیا جاتا ہے کہ ہاجوس کا قیاس بے ترتیب گرافوں کے لیے بری طرح ناکام ہوتا ہے: کیونکہ حد میں جیسے جیسے عمودی نقاط کی تعداد، لامحدود تک جاتی ہے، امکان اس کے قریب پہنچ جاتا ہے کہ بے ترتیب گراف میں رنگین ہوتا ہے اور اس کے سب سے بڑے کلیک ذیلی تقسیم میں عمودی ہوتے ہیں۔ اس تناظر میں، یہ بات قابل غور ہے کہ امکان اس کے قریب بھی پہنچ جاتا ہے کہ ایک بے ترتیب گراف میں ہاڈوگر نمبر اس کے کرومیٹک نمبر سے زیادہ یا اس کے برابر ہوتا ہے، لہذا ہاڈوگر قیاس اعلی امکان کے ساتھ بے ترتیب گرافوں کے لیے ہے۔ زیادہ واضح طور پر، ہاڈوگر نمبر اعلی امکان متناسب کے ساتھ ہے جس میں پوچھا گیا کہ کیا ہاڈوگر کے قیاس کو فہرست رنگ تک بڑھایا جا سکتا ہے۔ فہرست کرومیٹک نمبر والے ہر گراف میں ایک کلیک مائنر ہوتا ہے۔ تاہم، پلانر گراف کی زیادہ سے زیادہ فہرست کرومیٹک تعداد 5 ہے، 4 نہیں، لہذا گراف کے لیے توسیع پہلے ہی ناکام ہو چکی ہے۔ زیادہ عام طور پر، ایسے گراف موجود ہیں جن کا ہاڈوگر نمبر ہے اور جن کی فہرست کرومیٹک نمبر گیرارڈز اور سیمور نے قیاس کیا ہے کہ کرومیٹک نمبر والے ہر گراف میں ایک مکمل گراف ہوتا ہے جو کہ عجیب معمولی ہوتا ہے۔ اس طرح کے ڈھانچے کو عمودی-جداگانہ ذیلی درختوں کے خاندان کے طور پر پیش کیا جا سکتا ہے، جن میں سے ہر ایک دو رنگ کا ہوتا ہے، اس طرح کہ ذیلی درختوں کا ہر جوڑا یک رنگ کنارے سے جڑا ہوتا ہے۔ اگرچہ کوئی عجیب معمولی نہ ہونے والے گراف لازمی طور پر کم ہوتے ہیں، لیکن ان کے لیے اسی طرح کی اوپری حد برقرار رہتی ہے جیسا کہ یہ معیاری ہاڈوگر قیاس کے لیے ہوتی ہے: کوئی عجیب معمولی نہ ہونے والے گراف میں رنگین نمبر ہوتا ہے۔ اضافی شرائط عائد کرنے سے، بڑے نابالغوں کے وجود کو ثابت کرنا ممکن ہو سکتا ہے۔ ایک مثال اسنارک تھیوریم ہے، کہ ہر کیوبک گراف جس میں کسی بھی کنارے کے رنگ میں چار رنگوں کی ضرورت ہوتی ہے اس میں پیٹرسن گراف معمولی ہوتا ہے، جس کا قیاس ڈبلیو ٹی ٹوٹے نے کیا تھا اور 2001 میں رابرٹسن، سینڈرز، سیمور اور تھامس نے اسے ثابت کرنے کا اعلان کیا تھا۔ نوٹ حوالہ جات گراف کلرنگ گراف معمولی نظریہ گراف تھیوری میں حل نہ ہونے والے مسائل کا قیاس کرتا ہے