مسطح گراف

آزاد دائرۃ المعارف، ویکیپیڈیا سے
(مسطح مخطط سے رجوع مکرر)
یہاں جائیں: رہنمائی، تلاش کریں
مثال گراف
مسطح غیر مسطح
6n-graf.svg Complete graph K5.svg
K5
CGK4PLN.svg
مکمل گراف K4 مستوی ہے
Complete bipartite graph K3,3.svg
K3,3
اصطلاح term

گراف
راس
کنارہ
مستوی
مسطح
یحیط
چہرہ

graph
vertex, vertices
edge
plane
planar
bounded
face

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

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

پانچوں افلاطونی ٹھوس سے بننے والے گراف مسطح ہیں، کیونکہ انھیں اس طرح صفحہ پر بنایا جا سکتا ہے کہ کوئی کنارہ دوسرے کو نہ کاٹے۔ مثلاً مکعب کو یوں بنایا جا سکتا ہے۔ 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 کی ذیلی تقسیم ہو، تو ہم فوراً بھانپ لیں گے کہ یہ گراف غیر مسطح ہے۔ عملی طور پر یہ طریقہ مسطحی پرکھنے کے کام نہیں آتا کیونکہ گراف کے ذیلی گراف کی تعداد بہت زیادہ ہو سکتی ہے۔

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

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