Heawood conjecture
گراف تھیوری میں، ہیووڈ قیاس آرائی یا رنگل-ینگ تھیوریم ان رنگوں کی تعداد کے لیے ایک کم حد دیتا ہے جو کسی دی گئی جینس کی سطح پر گراف رنگنے کے لیے ضروری ہیں۔ جینس 0، 1، 2، 3، 4، 5، 6، 7، کی سطحوں کے لیے، رنگوں کی مطلوبہ تعداد 4، 7، 8، 9، 10، 11، 12، 12، کرومیٹک نمبر یا ہیووڈ نمبر ہے۔ یہ قیاس 1890 میں پرسی جان ہیووڈ نے وضع کیا تھا اور 1968 میں گیرہارڈ رنگل اور ٹیڈ ینگ نے ثابت کیا تھا۔ ایک معاملہ، غیر متصل کلین بوتل، عمومی فارمولے سے مستثنی ثابت ہوا۔ طیارہ یا دائرے کے لیے درکار رنگوں کی تعداد تلاش کرنے کے بہت پرانے مسئلے کے لیے ایک بالکل مختلف نقطہ نظر کی ضرورت تھی، جسے 1976 میں ہیکن اور ایپل نے چار رنگوں کے نظریہ کے طور پر حل کیا۔ دائرے پر نچلی حد آسان ہے، جبکہ اعلی نسل کے لیے اوپری حد آسان ہے اور یہ ہیووڈ کے اصل مختصر کاغذ میں ثابت ہوا جس میں قیاس آرائی تھی۔ دوسرے لفظوں میں، رنگل، ینگ اور دیگر کو ہر جینس جی = 1,2,3، کے لیے انتہائی مثالیں بنانا پڑتی تھیں۔ اگر g = 12s + k، تو جنرا k = 0,1,2، 3,4,5، 6,7,8، 9,10,11 کے مطابق 12 صورتوں میں آتا ہے۔ آسان بنانے کے لیے، فرض کریں کہ کیس k قائم کیا گیا ہے اگر 12s + k فارم کے g کی صرف ایک محدود تعداد شک میں ہو۔ پھر وہ سال جن میں بارہ مقدمات نمٹائے گئے اور جن کے ذریعے درج ذیل ہیں: 1954، رنگل: کیس 5 1961، رنگل: کیس 3,7,10 1963، ٹیری، ویلچ، ینگز: کیس 0,4 1964، گسٹن، ینگز: کیس 1 1965، گسٹن: کیس 9 1966، ینگز: کیس 6 1967، رنگل، ینگز: کیس 2,8,11 آخری سات وقفے وقفے سے مستثنیات کو درج ذیل طریقے سے طے کیا گیا: 1967، میئر: کیس 18، 20، 23 1968، رنگل، ینگز: کیس 30، 35، 47، 59، اور قیاس ثابت ہوا۔ رسمی بیان پرسی جان ہیووڈ نے 1890 میں قیاس کیا کہ کسی دی گئی جینس جی> 0 کے لیے، اس جینس کی سمت کی سطح پر تیار کردہ تمام گرافوں کو رنگنے کے لیے ضروری رنگوں کی کم از کم تعداد (یا سطح کی کسی بھی تقسیم کے علاقوں کو محض منسلک علاقوں میں رنگنے کے مساوی) اس کے ذریعے دی جاتی ہے کہ فرش کا فنکشن کہاں ہے۔ اویلر کی خصوصیت سے جینس کو تبدیل کرتے ہوئے، ہم ایک ایسا فارمولا حاصل کرتے ہیں جس میں واقفیت اور غیر واقفیت دونوں صورتوں کا احاطہ کیا جاتا ہے، جیسا کہ رنگیل اور ینگز نے دکھایا ہے، یہ تعلق کلین بوتل کے علاوہ تمام سطحوں کے لیے ہے۔ فلپ فرینکلن (1930) نے ثابت کیا کہ کلین بوتل کو فارمولے کے مطابق 7 کے بجائے زیادہ سے زیادہ 6 رنگوں کی ضرورت ہوتی ہے۔ فرینکلن گراف کو کلین بوتل پر اس طرح سے کھینچا جا سکتا ہے جس سے چھ باہمی ملحقہ علاقے بنتے ہیں، جس سے یہ ظاہر ہوتا ہے کہ یہ باؤنڈ تنگ ہے۔ اوپری باؤنڈ، جو ہی ووڈ کے اصل مختصر کاغذ میں ثابت ہوا ہے، لالچی رنگ الگورتھم پر مبنی ہے۔ اویلر کی خصوصیت میں ہیرا پھیری کرکے، کوئی یہ ظاہر کر سکتا ہے کہ دی گئی سطح میں سرایت شدہ ہر گراف میں دی گئی حد سے کم از کم ڈگری کا ایک ورٹیکس ہونا چاہیے۔ اگر کوئی اس سرے کو ہٹا دیتا ہے، اور باقی گراف کو رنگ دیتا ہے، تو ہٹائے گئے سرے سے منسلک کناروں کی چھوٹی تعداد اس بات کو یقینی بناتی ہے کہ اسے گراف میں واپس شامل کیا جا سکتا ہے اور حد سے باہر رنگوں کی مطلوبہ تعداد میں اضافہ کیے بغیر رنگ دیا جا سکتا ہے۔ دوسری سمت میں، ثبوت زیادہ مشکل ہے، اور اس میں یہ دکھانا شامل ہے کہ ہر معاملے میں (کلین بوتل کے علاوہ) رنگوں کی دی گئی تعداد کے برابر متعدد عمودی حصوں کے ساتھ ایک مکمل گراف سطح پر سرایت کیا جا سکتا ہے۔ مثال ٹورس میں g = 1 ہے، اس لیے χ = 0 ہے۔ لہذا، جیسا کہ فارمولا میں کہا گیا ہے، ٹورس کی خطوں میں کسی بھی ذیلی تقسیم کو زیادہ سے زیادہ سات رنگوں کا استعمال کرتے ہوئے رنگا جا سکتا ہے۔ مثال میں ٹورس کی ایک ذیلی تقسیم دکھائی گئی ہے جس میں سات خطوں میں سے ہر ایک ایک دوسرے خطے سے متصل ہے۔ اس ذیلی تقسیم سے پتہ چلتا ہے کہ رنگوں کی تعداد پر سات کی حد اس معاملے کے لیے سخت ہے۔ اس ذیلی تقسیم کی حد ٹورس پر ہیووڈ گراف کی سرایت بناتی ہے۔ حوالہ جات بیرونی روابط قیاس آرائیاں جو ثابت ہو چکی ہیں گراف کلرنگ ٹوپولوجیکل گراف تھیوری گراف تھیوری میں نظریات