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)-এর প্রথম উপস্থিতিকে অগ্রিম প্রান্ত বলা হয়, এবং দ্বিতীয় ঘটনাটিকে পশ্চাদপসরণ প্রান্ত বলা হয়। এটি এই অন্তর্দৃষ্টিকে আকৃষ্ট করে যে, প্রথমবার এই ধরনের প্রান্ত অতিক্রম করলে মূলের দূরত্ব বৃদ্ধি পায়, এবং দ্বিতীয়বার দূরত্ব হ্রাস পায়। নতুন মূলে বৃত্তাকার তালিকাটি বিভক্ত করে গাছটিকে ধ্রুবক সময় ও (1)-এ পুনরায় রুট করা যেতে পারে। প্রয়োগগুলি নিম্নলিখিত সমস্ত সমস্যাগুলি ও-তে সমাধান করা যেতে পারে (উপসর্গ যোগফল (এন)) (এন আইটেমগুলির তালিকার সমান্তরালে উপসর্গ যোগফল সমস্যা সমাধান করতে যে সময় লাগে): অগ্রিম এবং পশ্চাদপসরণ প্রান্তগুলিকে শ্রেণীবদ্ধ করাঃ ইটিআর-এ তালিকা র্যাঙ্কিং করুন এবং ফলাফলকে দ্বি-মাত্রিক অ্যারে এ-তে সংরক্ষণ করুন। তারপর (u, v) হল একটি অগ্রিম প্রান্ত যদি A (u, v) <A (v, u) হয়, এবং অন্যথায় একটি পশ্চাদপসরণ প্রান্ত। প্রতিটি নোডের স্তর নির্ধারণ করুনঃ ই. টি. আর-এ একটি উপসর্গ যোগফল করুন, যেখানে প্রতিটি অগ্রিম প্রান্তকে 1 হিসাবে গণনা করা হয় এবং প্রতিটি পশ্চাদপসরণ প্রান্তকে-1 হিসাবে গণনা করা হয়। তারপর অগ্রিম প্রান্তের মান (u, v) হল v-এর স্তর। v-তে মূলযুক্ত একটি উপ-বৃক্ষের নোডের সংখ্যাঃ ধরে নিন যে v-এর প্যারেন্ট হল u, অগ্রিম প্রান্ত (u, v) এবং পশ্চাদপসরণ প্রান্ত (v, u) সমান্তরালে নির্ধারণ করুন, এবং তারপর উপসর্গ যোগফল ব্যবহার করে (u, v) এবং (v, u)-এর মধ্যে অগ্রিম প্রান্তের সংখ্যা গণনা করুন। একটি নোড ভি-এর গভীরতা-প্রথম অনুসন্ধান সূচকঃ (ইউ, ভি) পর্যন্ত এবং সহ অগ্রিম প্রান্তের সংখ্যা গণনা করুন। দুটি নোডের সর্বনিম্ন সাধারণ পূর্বপুরুষ নির্ধারণ করুন। অয়লার ট্যুর ট্রি হেনজিঙ্গার এবং কিং একটি প্রদত্ত গাছকে প্রতিনিধিত্ব করার পরামর্শ দেয় তার অয়লার ট্যুরকে একটি ভারসাম্যপূর্ণ বাইনারি সার্চ ট্রি-তে রেখে, যা ট্যুরের সূচক দ্বারা কী করা হয়। সুতরাং উদাহরণস্বরূপ, উপরের উদাহরণে ভারসাম্যহীন ট্রি, 7 টি নোড সহ, 14 টি নোড সহ একটি ভারসাম্যপূর্ণ বাইনারি ট্রি দ্বারা প্রতিনিধিত্ব করা হবে, প্রতিবার প্রতিটি নোড সফরে উপস্থিত হওয়ার জন্য একটি করে। আমরা ই. টি গাছের সংগ্রহ ব্যবহার করে একটি বনের (একটি অ্যাসাইক্লিক গ্রাফ) প্রতিনিধিত্ব করতে পারি-একটি বন গাছের জন্য একটি ই. টি গাছ। এই উপস্থাপনাটি আমাদের দ্রুত এই প্রশ্নের উত্তর দিতে সাহায্য করে "নোড ভি-এর মূল কী?" শুধুমাত্র ই. টি গাছের প্রথম নোডে গিয়ে (যেহেতু ই. টি গাছের নোডগুলি ইউলার সফরে তাদের অবস্থান দ্বারা চিহ্নিত করা হয়, এবং মূলটি সফরের প্রথম এবং শেষ নোড)। যখন প্রতিনিধিত্বকৃত বনটি আপডেট করা হয় (যেমন। একটি গাছের সঙ্গে দুটি গাছকে যুক্ত করে বা একটি গাছকে দুটি গাছে বিভক্ত করে), সংশ্লিষ্ট অয়লার-ট্যুর কাঠামো ও (লগ (এন)) সময়ে আপডেট করা যেতে পারে। লিঙ্ক/কাটা গাছগুলির অনুরূপ কর্মক্ষমতার নিশ্চয়তা রয়েছে। যদিও এলসি গাছগুলি গাছের পথে সমষ্টি বজায় রাখার জন্য ভাল (এটি নেটওয়ার্ক ফ্লো অ্যালগরিদমগুলিতে একটি ভাল পছন্দের ডেটা কাঠামো তৈরি করে), ইটি গাছগুলি সাবট্রির উপর সমষ্টিগত তথ্য রাখতে আরও ভাল। রেফারেন্স গ্রাফ অ্যালগরিদম সমান্তরাল কম্পিউটিং