عائلرین گراف

آزاد دائرۃ المعارف، ویکیپیڈیا سے
(عائلرین مخطط سے رجوع مکرر)
Jump to navigation Jump to search
اصطلاح term

گراف
بند
صراط
عائلرین

graph
closed
trail
Eulerian


عائلرین گراف ریاضی کی شاخ "نظریہ گراف" میں متصل گراف کو عائلرین گراف کہا جاتا ہے اگر ایسی "بند صراط" ممکن ہو جس میں گراف کے تمام کنارے شامل ہوں۔ اور ایسی بند صراط کو عائلرین صراط کہا جائے گا۔

کونگسبرگ کے سات پُل

وجہ تسمیہ[ترمیم]

وجہ تسمیہ نامور ریاضی دان عائلر کے نام سے ہے۔ عائلر کو کونزبرگ شہر کے سات پلوں کے مسئلہ پر غور کرنے کے لیے کہا گیا تھا۔ شہر میں سات پل تھے (تصویر) اور شہری چاہتے تھے کہ parade کے لیے ایسا راستہ اختیار کیا جائے کہ سات پلوں سے صرف ایک دفعہ گزر ہو اور جہاں سے چلے وہیں واپسی ہو۔ اس مسئلہ میں دریا سے تقسیم ہونے والے چار ارضی علاقوں کو گراف کے راس خیال کرتے ہوئے اور سات پُلوں کو گراف کے کنارے، اس مسئلہ کو نظریہ گراف میں لایا جا سکتا ہے۔ عائلر نے ثابت کیا کہ ایسا کوئی راستہ ممکن نہیں اور اس مسئلہ اثباتی پر پہنچا۔

مسلئہ اثباتی[ترمیم]

متصل گراف عائلرین ہو گا اگر گراف کے ہر قمّہ کا درجہ جفت ہو۔ اگر ہر قمہ کا درجہ جفت نہیں تو گراف عائلرین نہیں۔ دوسرے الفاظ میں، متصل گراف عائلیرین ہو گا اگر بشرط اگر گراف کے ہر قمہ کا درجہ جفت ہو۔

بند صراط ڈھونڈنے کا الخوارزم[ترمیم]

عالرین گراف کے لیے نیچے دیے قدم اُٹھا کر ایک عائلرین صراط ہمیشہ ڈھونڈا جا سکتا ہے:

  1. کسی قمہ سے شروع کرو
  2. ہر مرحلہ پر کوئی بھی کنارہ چنو، "پُل" صرف اس صورت چنو اگر اور کوئی متبادل نہ ہو
  3. کنارہ پر چلنے کے بعد اسے مٹا دو۔ اگر درجہ صفر کا کوئی قمہ بنتا ہے تو اسے بھی مٹا دو۔ اس کے بعد پھر کنارہ چنو۔
  4. جب کوئی کنارہ نہ بچے تو رُک جاؤ۔

مزید دیکھیے[ترمیم]

== بیرونی روابط ==*

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