مسطح گراف

مثال گراف مسطح غیر مسطح 100px 100px  K5 100px  مکمل گراف K4 مستوی ہے  100px  K3,3

ریاضی کی شاخ نظریۂ گراف میں ایسا گراف جسے صفحہ (مستوی میں) پر اس طرح بنایا جا سکے کہ کوئی کنارہ کسی دوسرے کو نہ کاٹے، کو مسطح گراف کہا جاتا ہے۔

ایسا گراف جسے اس طرح نہ بنایا جا سکے کو غیر مسطح گراف کہتے ہیں۔

پانچوں افلاطونی ٹھوس سے بننے والے گراف مسطح ہیں، کیونکہ انھیں اس طرح صفحہ پر بنایا جا سکتا ہے کہ کوئی کنارہ دوسرے کو نہ کاٹے۔ مثلاً مکعب کو یوں بنایا جا سکتا ہے۔ فائل:cube_planar_graph.svg

تعریف: چہرہ: مسطح گراف کو اس طرح بنایا جائے کہ کوئی کنارہ دوسرے کو نہ کاٹے، تو یہ گراف مستوی کو اضلاع میں تقسیم کرتا ہے، جنہیں چہرے کہا جاتا ہے۔ ان میں سے ایک چہرہ لایحیط ہو گا اور اسے لامتناہی چہرہ کہا جائے گا۔ اگر f چہرہ ہو، تو اس چہرہ کا درجہ  deg f  اس چہرے کے گرد چلتے ہوئے کناروں کی تعداد کو کہتے ہیں۔ اگر تمام چہروں کا درجہ برابر ہو (کہو d) تو گراف کو "چہرہ باقاعدگی درجہ d کے ساتھ" کہا جائے گا۔

 عائلر کلیہ 
متصل مسطح گراف (ایسے بنایا جائے کہ کوئی کنارہ کسی کو نہ کاٹے) کے راس کی تعداد کو n، کناروں کی تعداد کو m اور چہروں کی تعداد کو f کہتے ہوئے، یہ سچ ہو گا کہ
 n-m+f = 2 

 ذیلی تقسیم 
اگر گراف مسطح ہو تو اس گراف کی تمام ذیلی‌تقسیمات بھی مسطح ہوں گی۔ اسے ہم یوں بھی بیان کر سکتے ہیں کہ: اگر گراف G کسی غیر مسطح گراف کی ذیلی‌تقسیم ہو، تو G بھی غیر مسطح ہو گا۔ جیسا کہ نیچے دیے مسلئہ اثباتی سے ظاہر ہے اس سلسلہ میں غیر مسطح گراف K5 اور K3,3 (اُوپر تصویر) بہت اہمیت کے حامل ہیں۔

 کراتوسکی مسئلہ اثباتی 
گراف مسطح ہو گا اگر بشرط اگر اس گراف میں K5 یا K3,3 کی ذیلی‌تقسیم شامل نہ ہو بطور ذیلی‌گراف کے ۔

اگر ہمیں کسی گراف کا ایسا ذیلی گراف نظر آ جائے جو K5 یا K5 کی ذیلی تقسیم ہو، تو ہم فوراً بھانپ لیں گے کہ یہ گراف غیر مسطح ہے۔ عملی طور پر یہ طریقہ مسطحی پرکھنے کے کام نہیں آتا کیونکہ گراف کے ذیلی گراف کی تعداد بہت زیادہ ہو سکتی ہے۔

 مزید دیکھیے == ==بیرونی روابط * 

زمرہ:کامنز زمرہ جس کا ربط ویکی ڈیٹا پر ہے
زمرہ:ویکی ڈیٹا سے مطابقت رکھنے والی مختصر تفصیل
زمرہ:نظریہ گراف
زمرہ:ہندسہ