Schnyder's theorem
گراف تھیوری میں، شنائڈر تھیوریم پلانر گرافوں کی ان کے انسیڈنس پوسیٹس کے آرڈر طول و عرض کے لحاظ سے ایک خصوصیت ہے۔ اس کا نام والٹر شنائڈر کے نام پر رکھا گیا ہے، جس نے 1989 میں اس کا ثبوت شائع کیا تھا۔ ورٹیکس سیٹ اور ایج سیٹ کے ساتھ غیر ہدایت شدہ گراف کا انسیڈنس پوزیٹ اونچائی 2 کا جزوی طور پر ترتیب شدہ سیٹ ہے جس میں اس کے عناصر ہوتے ہیں۔ اس جزوی ترتیب میں، ایک ترتیب کا تعلق ہوتا ہے جب ایک ورٹیکس ہوتا ہے، ایک کنارہ ہوتا ہے، اور اس کے دو اختتامی نکات میں سے ایک ہوتا ہے۔ جزوی ترتیب کا ترتیب طول و عرض کل ترتیبات کی سب سے چھوٹی تعداد ہے جس کا چوراہا دیا ہوا جزوی ترتیب ہے۔ ترتیبات کے اس طرح کے سیٹ کو جزوی ترتیب کا حقیقت پسند کہا جاتا ہے۔ شنائڈر تھیوریم میں کہا گیا ہے کہ گراف پلانر ہوتا ہے اگر اور صرف اس صورت میں جب اس کی ترتیب کا طول و عرض زیادہ سے زیادہ تین ہو۔ ایکسٹینشنز اس تھیوریم کو اونچائی کے طول و عرض پر ایک سخت باؤنڈ کے ذریعے عام کیا گیا ہے-تین جزوی طور پر ترتیب شدہ سیٹ جو کنویکس پولی ہیڈرون کے عمودی، کناروں اور چہروں سے، یا زیادہ عام طور پر سرایت شدہ پلینر گراف کے متوازی طور پر تشکیل پائے ہیں: دونوں صورتوں میں، پوزیشن کا آرڈر طول و عرض زیادہ سے زیادہ چار ہوتا ہے۔ تاہم، اس نتیجے کو اعلی جہتی کنویکس پولی ٹاپس میں عام نہیں کیا جا سکتا، کیونکہ چار جہتی پولی ٹاپس موجود ہیں جن کے چہرے کی جالی غیر محدود ترتیب کی جہت رکھتے ہیں۔ اس سے بھی زیادہ عام طور پر، تجریدی سادہ کمپلیکس کے لیے، کمپلیکس کے چہرے کی پوزیشن کا آرڈر طول و عرض زیادہ سے زیادہ ہوتا ہے، جہاں یوکلڈین اسپیس کا کم از کم طول و عرض ہوتا ہے جس میں کمپلیکس کو ہندسی احساس ہوتا ہے۔ دوسرے گراف جیسا کہ شنائڈر مشاہدہ کرتا ہے، گراف G کے انسیڈنس پوزیٹ میں آرڈر طول و عرض دو ہوتا ہے اگر اور صرف اس صورت میں جب گراف کسی راستے کا راستہ یا ذیلی گراف ہو۔ کیونکہ، جب کسی انسیڈنس پوسیٹ میں آرڈر کا طول و عرض دو ہوتا ہے، تو اس کا واحد ممکنہ احساس دو کل آرڈرز پر مشتمل ہوتا ہے جو (جب گراف کے عمودی حصوں تک محدود ہوتا ہے) ایک دوسرے کے برعکس ہوتے ہیں۔ کسی بھی دوسرے دو آرڈرز کا ایک چوراہا ہوگا جس میں دو عمودی کے درمیان آرڈر کا تعلق شامل ہوتا ہے، جس کی اجازت انسیڈنس پوزیشنز کے لیے نہیں ہے۔ چوٹیوں پر ان دو آرڈرز کے لیے، لگاتار چوٹیوں کے درمیان ایک کنارے کو ترتیب میں شامل کیا جا سکتا ہے جسے دو کنارے کے اختتامی نکات کے بعد فوری طور پر رکھا جا سکتا ہے، لیکن کسی دوسرے کنارے کو شامل نہیں کیا جا سکتا۔ اگر کسی گراف کو چار رنگوں سے رنگا جا سکتا ہے، تو اس کے انسیڈنس پوزیٹ کی جہت زیادہ سے زیادہ چار ہوتی ہے۔ n عمودی پر ایک مکمل گراف کے انسیڈنس پوزیٹ میں ترتیب کا طول و عرض ہوتا ہے۔ حوالہ جات۔ ۔ ۔ ۔ ۔ ۔ آرڈر تھیوری پلانر گراف تھیوری میں نظریات گراف