مسطح گراف

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

اصطلاح	term
گراف راس کنارہ مستوی مسطح یحیط چہرہ	graph vertex, vertices edge plane planar bounded face

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

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

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

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

عائلر کلیہ

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

n-m+f = 2

ذیلی تقسیم

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

کراتوسکی مسئلہ اثباتی

گراف مسطح ہو گا اگر بشرط اگر اس گراف میں K₅ یا K_3,3 کی ذیلی‌تقسیم شامل نہ ہو بطور ذیلی‌گراف کے ۔

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

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

E=mc2     اردو ویکیپیڈیا پر ریاضی مساوات کو بائیں سے دائیں LTR پڑھیٔے     ریاضی علامات