Scheinerman's conjecture
ریاضی میں، شینر مین کا قیاس، جو اب ایک نظریہ ہے، بیان کرتا ہے کہ ہر پلینر گراف طیارہ میں لائن سیگمنٹس کے ایک سیٹ کا انٹرسیکشن گراف ہے۔ اس قیاس کو ای آر شینر مین نے اپنے پی ایچ ڈی تھیسس (1984) میں پہلے کے نتائج کے بعد وضع کیا تھا کہ ہر پلینر گراف کو طیارہ میں سادہ منحنی خطوط کے ایک سیٹ کے انٹرسیکشن گراف کے طور پر پیش کیا جا سکتا ہے۔ کے ذریعے ثابت کیا گیا۔ مثال کے طور پر، نیچے بائیں طرف دکھائے گئے گراف G کو نیچے دائیں طرف دکھائے گئے حصوں کے سیٹ کے انٹرسیکشن گراف کے طور پر پیش کیا جا سکتا ہے۔ یہاں، G کے عمودی حصوں کو سیدھی لکیر کے حصوں سے ظاہر کیا جاتا ہے اور G کے کناروں کو انٹرسیکشن پوائنٹس سے ظاہر کیا جاتا ہے۔ شینر مین نے یہ بھی قیاس کیا کہ صرف تین سمتوں والے حصے 3 رنگین گرافوں کی نمائندگی کرنے کے لیے کافی ہوں گے، اور قیاس کیا کہ یکساں طور پر ہر پلینر گراف کو چار سمتوں کا استعمال کرتے ہوئے پیش کیا جا سکتا ہے۔ اگر کسی گراف کی نمائندگی صرف k سمتوں والے حصوں کے ساتھ کی جاتی ہے اور کوئی دو حصے ایک ہی لکیر سے تعلق نہیں رکھتے ہیں، تو گراف کو k رنگوں کا استعمال کرتے ہوئے رنگا جا سکتا ہے، ہر سمت کے لیے ایک رنگ۔ لہذا، اگر ہر طیارہ گراف کو صرف چار سمتوں کے ساتھ اس طرح سے پیش کیا جا سکتا ہے، تو چار رنگوں کا نظریہ اس کے بعد آتا ہے۔ اور ثابت کیا کہ ہر دو طرفہ طیارہ گراف کو افقی اور عمودی لکیر کے حصوں کے چوراہے کے گراف کے طور پر پیش کیا جا سکتا ہے۔ اس نتیجے کے لیے یہ بھی دیکھیں۔ یہ ثابت کیا کہ ہر مثلث سے پاک طیارہ گراف کو صرف تین سمتوں والے لکیر کے حصوں کے چوراہے کے گراف کے طور پر پیش کیا جا سکتا ہے۔ اس نتیجے سے گرٹزش کے نظریہ کا اشارہ ہوتا ہے کہ مثلث سے پاک طیارہ گراف کو تین رنگوں سے رنگا جا سکتا ہے۔ یہ ثابت کیا کہ اگر ایک طیارہ گراف G 4 رنگ کا اس طرح سے ہو سکتا ہے کہ کوئی علیحدہ سائیکل چاروں رنگوں کا استعمال نہ کرے، تو G کی نمائندگی حصوں کے چوراہے کے گراف کے طور پر ہوتی ہے۔ یہ ثابت کیا کہ طیارہ گراف 1-سٹرنگ میں ہیں، طیارہ میں سادہ منحنی خطوط کے انٹرسیکشن گراف کی کلاس جو فی جوڑے میں زیادہ سے زیادہ ایک کراسنگ پوائنٹ پر ایک دوسرے کو کاٹتی ہے۔ یہ کلاس شینر مین کے قیاس میں ظاہر ہونے والے حصوں کے انٹرسیکشن گراف اور ایرلچ ایٹ ال کے نتیجے سے غیر محدود سادہ منحنی خطوط کے انٹرسیکشن گراف کے درمیان انٹرمیڈیٹ ہے۔ اسے سرکل پیکنگ تھیوریم کی عمومی شکل کے طور پر بھی دیکھا جا سکتا ہے، جو اسی نتیجے کو ظاہر کرتا ہے جب منحنی خطوط کو ٹینجینٹ میں کاٹنے کی اجازت دی جاتی ہے۔ قیاس آرائی کا ثبوت اس نتیجے میں بہتری پر مبنی تھا۔ حوالہ جات۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ پلانر گراف قیاس آرائیاں جو ثابت ہو چکی ہیں