Barnette's conjecture
بارنیٹ کا قیاس گراف تھیوری میں ایک غیر حل شدہ مسئلہ ہے، جو ریاضی کی ایک شاخ ہے، جو گراف میں ہیملٹنین چکروں سے متعلق ہے۔ اس کا نام ڈیوڈ ڈبلیو بارنیٹ کے نام پر رکھا گیا ہے، جو یونیورسٹی آف کیلیفورنیا، ڈیوس میں پروفیسر ایمریٹس ہیں۔ اس میں کہا گیا ہے کہ ہر دو طرفہ پولی ہیڈرل گراف جس کے تین کنارے فی ورٹیکس ہوتے ہیں، اس میں ہیملٹنین سائیکل ہوتا ہے۔ تعریفیں طیارہ گراف ایک غیر ہدایت شدہ گراف ہے جسے بغیر کسی کراسنگ کے یوکلڈین طیارہ میں سرایت کیا جا سکتا ہے۔ پلانر گراف کو پولی ہیڈرل کہا جاتا ہے اگر اور صرف اس صورت میں جب یہ 3-ورٹیکس سے منسلک ہو، یعنی اگر دو عمودی نہ ہوں جن کو ہٹانے سے باقی گراف منقطع ہو جائے گا۔ گراف دو طرفہ ہوتا ہے اگر اس کے عمودی حصوں کو دو مختلف رنگوں سے اس طرح رنگا جا سکے کہ ہر کنارے پر ہر رنگ کا ایک اختتامی نقطہ ہو۔ گراف کیوبک (یا 3-ریگولر) ہوتا ہے اگر ہر ایک ورٹیکس بالکل تین کناروں کا اختتامی نقطہ ہو۔ آخر میں، ایک گراف ہیملٹنین ہے اگر کوئی ایسا چکر موجود ہو جو اس کے ہر ایک سرے سے بالکل ایک بار گزرتا ہو۔ بارنیٹ کے قیاس میں کہا گیا ہے کہ ہر کیوبک دو طرفہ پولی ہیڈرل گراف ہیملٹنین ہے۔ سٹینٹز تھیوریم کے مطابق، ایک پلینر گراف ایک کنویکس پولی ہیڈرون کے کناروں اور عمودی حصوں کی نمائندگی کرتا ہے اگر اور صرف اس صورت میں جب یہ پولی ہیڈرل ہو۔ تین جہتی پولی ہیڈرون میں کیوبک گراف ہوتا ہے اگر اور صرف اس صورت میں جب یہ ایک سادہ پولی ہیڈرون ہو۔ اور، ایک پلانر گراف دو طرفہ ہوتا ہے اگر اور صرف اس صورت میں جب، گراف کے پلانر ایمبیڈنگ میں، تمام چہرے کے چکروں کی لمبائی یکساں ہو۔ لہذا، بارنیٹ کے قیاس کو مساوی شکل میں بیان کیا جا سکتا ہے: فرض کریں کہ تین جہتی سادہ کنویکس پولی ہیڈرون کے ہر چہرے پر برابر تعداد میں کنارے ہوتے ہیں۔ پھر، قیاس کے مطابق، پولی ہیڈرون کے گراف میں ہیملٹنین سائیکل ہوتا ہے۔ تاریخ نے قیاس کیا کہ ہر کیوبک پولی ہیڈرل گراف ہیملٹنین ہے ؛ یہ ٹائٹ کے قیاس کے نام سے جانا جانے لگا۔ اس کی تردید کی گئی، جس نے 46 عمودی کے ساتھ ایک جوابی مثال بنائی ؛ دوسرے محققین کو بعد میں اس سے بھی چھوٹی جوابی مثالیں ملیں۔ تاہم، ان معروف جوابی مثالوں میں سے کوئی بھی دو طرفہ نہیں ہے۔ خود ٹوٹے نے اندازہ لگایا کہ ہر کیوبک 3 سے منسلک دو طرفہ گراف ہیملٹنین ہے، لیکن یہ ایک جوابی مثال، ہارٹن گراف کی دریافت سے غلط ثابت ہوا۔ ٹائٹ اور ٹوٹے کے قیاس آرائیوں کے ایک کمزور امتزاج کی تجویز پیش کی، جس میں کہا گیا کہ ہر دو طرفہ کیوبک پولی ہیڈرون ہیملٹنین ہے، یا، مساوی طور پر، کہ ٹائٹ کے قیاس آرائی کی ہر جوابی مثال غیر دو طرفہ ہے۔ مساوی شکلوں سے پتہ چلتا ہے کہ بارنیٹ کا قیاس ایک سطحی طور پر مضبوط بیان کے مساوی ہے، کہ دو طرفہ کیوبک پولی ہیڈرون کے ایک ہی چہرے پر ہر دو کناروں e اور f کے لیے، ایک ہیملٹنین سائیکل موجود ہے جس میں e ہوتا ہے لیکن f نہیں ہوتا ہے۔ واضح طور پر، اگر یہ بیان درست ہے، تو ہر دو طرفہ کیوبک پولی ہیڈرون میں ہیملٹنین سائیکل ہوتا ہے: صرف من مانی طور پر e اور f کا انتخاب کریں۔ دوسری سمتوں میں، کیلمینز نے دکھایا کہ ایک جوابی مثال کو اصل بارنیٹ قیاس آرائی کے جوابی مثال میں تبدیل کیا جا سکتا ہے۔ بارنیٹ کا قیاس بھی اس بیان کے مساوی ہے کہ ہر کیوبک دو طرفہ پولی ہیڈرل گراف کے دوہری کے عمودی حصوں کو دو ذیلی سیٹوں میں تقسیم کیا جا سکتا ہے جن کے محرک ذیلی گراف درخت ہیں۔ دوہری گراف میں اس طرح کی تقسیم سے متاثر ہونے والی کٹ ابتدائی گراف میں ہیملٹنین سائیکل سے مطابقت رکھتی ہے۔ جزوی نتائج اگرچہ بارنیٹ کے قیاس کی سچائی نامعلوم ہے، کمپیوٹیشنل تجربات سے پتہ چلتا ہے کہ 86 سے کم عمودی کے ساتھ کوئی جوابی مثال نہیں ہے۔ اگر بارنیٹ کا قیاس غلط ثابت ہوتا ہے، تو یہ جانچنے کے لیے کہ آیا دو طرفہ کیوبک پولی ہیڈرون ہیملٹنین ہے، اسے این پی مکمل دکھایا جا سکتا ہے۔ اگر پلانر گراف دو طرفہ اور کیوبک ہے لیکن صرف کنیکٹوٹی 2 کا ہے، تو یہ غیر ہیملٹنین ہو سکتا ہے، اور ان گرافوں کے لیے ہیملٹنسیٹی کی جانچ کرنا این پی مکمل ہے۔ ایک اور نتیجہ اس طرح حاصل کیا گیا: اگر دوہری گراف نیلے، سرخ اور سبز رنگوں کے ساتھ ورٹیکس رنگ کا ہو سکتا ہے جیسے کہ ہر سرخ سبز سائیکل ڈگری 4 کے ورٹیکس پر مشتمل ہو، تو ابتدائی گراف ہیملٹنین ہے۔ متعلقہ مسائل بارنیٹ کا ایک متعلقہ قیاس یہ بتاتا ہے کہ ہر کیوبک پولی ہیڈرل گراف جس میں تمام چہروں کے چھ یا اس سے کم کنارے ہوتے ہیں، ہیملٹنین ہے۔ کمپیوٹیشنل تجربات سے پتہ چلتا ہے کہ اگر کوئی جوابی مثال موجود ہے تو اس کے 177 سے زیادہ عمودی ہونے چاہئیں گے۔ اس قیاس کو ثابت کیا گیا۔ ان دونوں قیاس آرائیوں کا چوراہا یہ ہوگا کہ ہر دو طرفہ کیوبک پولی ہیڈرل گراف جس میں تمام چہروں کے چار یا چھ کنارے ہوتے ہیں، ہیملٹنین ہے۔ یہ بات سچ ثابت ہوئی۔ نوٹس حوالہ جات ؛ سائنٹیفک پیپرز، جلد میں دوبارہ شائع ہوا۔ II، پی پی۔ 85-98 بیرونی روابط اوپن پروبلم گارڈن میں بارنیٹ کا قیاس، رابرٹ سمال، 2007۔ گراف تھیوری میں غیر حل شدہ مسائل پلانر ہیملٹنین راستوں اور چکروں کو گراف کرتا ہے