عائلرین گراف

اصطلاح	term
گراف بند صراط عائلرین	graph closed trail Eulerian

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

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

وجہ تسمیہ

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

مسلئہ اثباتی

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

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

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

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

مزید دیکھیے

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

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