Euler tour technique
یولر ٹور تکنیک (ای ٹی ٹی)، جس کا نام لیون ہارڈ یولر کے نام پر رکھا گیا ہے، درختوں کی نمائندگی کے لیے گراف تھیوری کا ایک طریقہ ہے۔ درخت کو ایک ہدایت شدہ گراف کے طور پر دیکھا جاتا ہے جس میں درخت کے ہر کنارے کے لیے دو سمت والے کنارے ہوتے ہیں۔ اس کے بعد درخت کو ہدایت شدہ گراف کے یولیرین سرکٹ کے طور پر پیش کیا جا سکتا ہے، جسے درخت کی یولر ٹور نمائندگی (ای ٹی آر) کہا جاتا ہے۔ ای ٹی ٹی الگورتھمک گراف تھیوری میں عام مسائل کے حل کے موثر، متوازی حساب کی اجازت دیتا ہے۔ اسے ٹارجن اور وشکن نے 1984 میں متعارف کرایا تھا۔ کنسٹرکشن کو کناروں کے ایک سیٹ کے طور پر پیش کیے گئے ایک غیر ہدایت شدہ درخت کو دیکھتے ہوئے، یولر ٹور کی نمائندگی (ای ٹی آر) کو متوازی طور پر اس طرح بنایا جا سکتا ہے: ہم ہدایت شدہ کناروں کی ایک ہم آہنگ فہرست بناتے ہیں: درخت میں ہر غیر ہدایت شدہ کنارے {یو، وی} کے لیے، کنارے کی فہرست میں (یو، وی) اور (وی، یو) ڈالیں۔ کنارے کی فہرست کو لغت کے لحاظ سے ترتیب دیں۔ (یہاں ہم فرض کرتے ہیں کہ درخت کے نوڈس کو ترتیب دیا گیا ہے، اور یہ کہ جڑ اس ترتیب میں پہلا عنصر ہے۔) ہر نوڈ (جسے اگلا کہا جاتا ہے) کے لیے ملحقہ فہرستیں بنائیں اور نوڈس سے ملحقہ فہرستیں (جسے پہلے کہا جاتا ہے) کی پہلی اندراجات تک کا نقشہ بنائیں: فہرست میں ہر کنارے (u، v) کے لیے متوازی طور پر کریں: اگر پچھلے کنارے (x، y) میں x  ऒत्त u ہے، یعنی۔ ایک مختلف نوڈ سے شروع ہوتا ہے، پہلے سیٹ کریں (u) = (u، v) ورنہ اگر x = u، یعنی۔ ایک ہی نوڈ سے شروع ہوتا ہے، اگلا سیٹ کریں (x, y) = (u, v) مندرجہ ذیل اصول کے مطابق متوازی طور پر تمام کناروں (u, v) کے لیے پوائنٹر سک (u, v) سیٹ کر کے اویلر ٹور آرڈر میں ایک ایج لسٹ (جسے سک کہا جاتا ہے) بنائیں: نتیجہ خیز لسٹ سک سرکلر ہوگی۔ مجموعی طور پر تعمیر میں کام W (n) = O (ترتیب (n)) لگتا ہے (n اشیاء کو متوازی طور پر ترتیب دینے میں لگنے والا وقت) اگر درخت میں n نوڈس ہوں، جیسا کہ درختوں میں کناروں کی تعداد نوڈس کی تعداد سے ایک کم ہوتی ہے۔ جڑیں، آگے اور پیچھے ہٹنے والے کنارے اگر درخت کی جڑ ہے، تو ہم اس جڑ پر سرکلر لسٹ سک کو تقسیم کر سکتے ہیں۔ اس صورت میں، ہم پیشگی اور پیچھے ہٹنے والے کناروں کے بارے میں بات کر سکتے ہیں: نوڈس u، v کی ایک جوڑی کو دیکھتے ہوئے، ETR میں (u، v) یا (v، u) میں سے کسی ایک کی پہلی موجودگی کو پیشگی کنارہ کہا جاتا ہے، اور دوسرے واقعے کو ریٹریٹ ایج کہا جاتا ہے۔ یہ وجدان کو اپیل کرتا ہے کہ پہلی بار اس طرح کے کنارے کو عبور کرنے سے جڑ تک کا فاصلہ بڑھ جاتا ہے، جبکہ دوسری بار فاصلہ کم ہو جاتا ہے۔ درخت کو نئے جڑ پر سرکلر لسٹ سک کو تقسیم کرکے مستقل وقت O (1) میں دوبارہ ترتیب دیا جا سکتا ہے۔ ایپلی کیشنز مندرجہ ذیل تمام مسائل کو O (پریفیکس سم (n)) میں حل کیا جا سکتا ہے (n آئٹمز کی فہرست کے متوازی میں پریفیکس سم کے مسئلے کو حل کرنے میں لگنے والا وقت): پیشگی اور پیچھے ہٹنے والے کناروں کی درجہ بندی کرنا: ETR پر فہرست کی درجہ بندی کریں اور نتیجہ کو دو جہتی صف A میں محفوظ کریں۔ پھر (u، v) A (u، v) <A (v، u) کا ایک پیشگی کنارہ ہے، اور بصورت دیگر ایک پسپائی کنارہ ہے۔ ہر نوڈ کی سطح کا تعین کریں: ای ٹی آر پر ایک سابقہ رقم کریں، جہاں ہر پیشگی کنارے کو 1 کے طور پر شمار کیا جاتا ہے، اور ہر پیچھے ہٹنے والے کنارے کو −1 کے طور پر شمار کیا جاتا ہے۔ پھر ایڈوانس ایج (u، v) پر ویلیو v کی سطح ہے۔ v پر جڑے ہوئے سبٹری میں نوڈس کی تعداد: فرض کریں کہ v کا پیرنٹ u ہے، ایڈوانس ایج (u، v)، اور ریٹریٹ ایج (v، u) کا متوازی تعین کریں، اور پھر پریفیکس سم کا استعمال کرتے ہوئے (u، v) اور (v، u) کے درمیان ایڈوانس ایجز کی تعداد شمار کریں۔ نوڈ v کا ڈیپتھ-فرسٹ سرچ انڈیکس: (u، v) تک اور اس میں شامل پیشگی کناروں کی تعداد شمار کرتا ہے۔ دو نوڈس کے سب سے کم مشترکہ آباؤ اجداد کا تعین کریں۔ اویلر ٹور ٹری ہینزنگر اور کنگ تجویز کرتے ہیں کہ اس کے اویلر ٹور کو متوازن بائنری سرچ ٹری میں رکھ کر کسی دیئے گئے درخت کی نمائندگی کریں، جو ٹور میں انڈیکس کے ذریعہ کلیدی ہے۔ لہذا مثال کے طور پر، اوپر کی مثال میں غیر متوازن درخت، جس میں 7 نوڈس ہوں گے، کی نمائندگی 14 نوڈس کے ساتھ ایک متوازن بائنری ٹری کے ذریعے کی جائے گی، ہر بار ہر نوڈ کے دورے پر ظاہر ہونے پر ایک۔ ہم ای ٹی درختوں کے مجموعے کا استعمال کرتے ہوئے جنگل (ایک سایکلک گراف) کی نمائندگی کر سکتے ہیں-ایک جنگل کے درخت کے لیے ایک ای ٹی درخت۔ یہ نمائندگی ہمیں اس سوال کا فوری جواب دینے کی اجازت دیتی ہے کہ "نوڈ v کی جڑ کیا ہے؟" صرف ای ٹی ٹری کے پہلے نوڈ پر منتقل ہو کر (چونکہ ای ٹی ٹری میں نوڈس کو اویلر ٹور میں ان کے مقام سے کلیدی شکل دی جاتی ہے، اور جڑ ٹور میں پہلا اور آخری نوڈ ہوتا ہے)۔ جب نمائندگی شدہ جنگل کو اپ ڈیٹ کیا جاتا ہے (مثال کے طور پر دو درختوں کو ایک ہی درخت سے جوڑ کر یا ایک درخت کو دو درختوں میں تقسیم کر کے)، متعلقہ اویلر ٹور ڈھانچے کو وقت O (لاگ (n)) میں اپ ڈیٹ کیا جا سکتا ہے۔ لنک/کٹے ہوئے درختوں کی کارکردگی کی اسی طرح کی ضمانت ہوتی ہے۔ جبکہ ایل سی درخت درخت کے راستوں پر مجموعوں کو برقرار رکھنے کے لیے اچھے ہوتے ہیں (یہ نیٹ ورک فلو الگورتھم میں ایک اچھا انتخاب ڈیٹا ڈھانچہ بناتا ہے)، ای ٹی درخت ذیلی درختوں پر مجموعی معلومات رکھنے میں بہتر ہوتے ہیں۔ حوالہ جات گراف الگورتھم متوازی کمپیوٹنگ