Expected linear time MST algorithm
প্রত্যাশিত রৈখিক সময় এম. এস. টি অ্যালগরিদম একটি এলোমেলো অ্যালগরিদম যা কোনও বিচ্ছিন্ন শীর্ষ ছাড়াই ওজনযুক্ত গ্রাফের ন্যূনতম বিস্তৃত বন গণনা করার জন্য। এটি ডেভিড কারগার, ফিলিপ ক্লেইন এবং রবার্ট টারজান দ্বারা তৈরি করা হয়েছিল। অ্যালগরিদমটি রৈখিক সময়ে ন্যূনতম স্প্যানিং ট্রি যাচাই করার জন্য একটি অ্যালগরিদম সহ বোরুভকার অ্যালগরিদমের কৌশলগুলির উপর নির্ভর করে। এটি প্রত্যাশিত রৈখিক কর্মক্ষমতা অর্জনের জন্য বিভাজন এবং জয় অ্যালগরিদম, লোভী অ্যালগরিদম এবং র্যান্ডমাইজড অ্যালগরিদমের নকশার দৃষ্টান্তগুলিকে একত্রিত করে। ন্যূনতম স্প্যানিং ট্রি খুঁজে পাওয়া নির্ধারক অ্যালগরিদমগুলির মধ্যে রয়েছে প্রিমের অ্যালগরিদম, ক্রুস্কালের অ্যালগরিদম, বিপরীত-মুছে ফেলার অ্যালগরিদম এবং বোরুভকার অ্যালগরিদম। সংক্ষিপ্ত বিবরণ অ্যালগরিদমের মূল অন্তর্দৃষ্টি হল একটি র্যান্ডম স্যাম্পলিং ধাপ যা প্রতিটি সাবগ্রাফ অন্তর্ভুক্ত করার জন্য এলোমেলোভাবে প্রান্ত নির্বাচন করে একটি গ্রাফকে দুটি সাবগ্রাফ-এ বিভক্ত করে। অ্যালগরিদমটি পুনরাবৃত্তভাবে প্রথম উপ-সমস্যার ন্যূনতম বিস্তৃত বন খুঁজে পায় এবং ন্যূনতম বিস্তৃত গাছের মধ্যে থাকতে পারে না এমন গ্রাফের প্রান্তগুলি ফেলে দেওয়ার জন্য একটি রৈখিক সময় যাচাইকরণ অ্যালগরিদমের সাথে সমাধানটি ব্যবহার করে। প্রতিটি পুনরাবৃত্তিতে গ্রাফের আকার কমাতে বোরুভকার অ্যালগরিদম থেকে নেওয়া একটি পদ্ধতিও ব্যবহার করা হয়। বোরুভকা ধাপ অ্যালগরিদমের প্রতিটি পুনরাবৃত্তি বোরুভকার অ্যালগরিদমের একটি অভিযোজনের উপর নির্ভর করে যা একটি বোরুভকা ধাপ হিসাবে উল্লেখ করা হয়ঃ ইনপুটঃ একটি গ্রাফ জি যার কোনও বিচ্ছিন্ন শীর্ষ নেই 1 প্রতিটি শীর্ষের জন্য, ভি 2-এ হালকা প্রান্তের ঘটনা নির্বাচন করুন 'একটি সংকুচিত গ্রাফ জি' তৈরি করুন 'ধাপ 1-এ নির্বাচিত প্রান্ত দ্বারা সংযুক্ত জি-এর প্রতিটি উপাদানকে একক শীর্ষ দিয়ে প্রতিস্থাপন করে 3 জি আউটপুট থেকে সমস্ত বিচ্ছিন্ন শীর্ষ, স্ব-লুপ এবং অ-ন্যূনতম পুনরাবৃত্তিমূলক প্রান্তগুলি সরিয়ে ফেলুনঃ ধাপ 1-এ নির্বাচিত প্রান্তগুলি এবং সংকুচিত গ্রাফ জিএ বোরুভকা ধাপটি বোরুভকার অ্যালগরিদমের অভ্যন্তরীণ লুপের সমতুল্য, যা ও (এম) সময়ে চলে যেখানে এম হল সুতরাং, একটি বোরুভকা ধাপ গ্রাফের শীর্ষগুলির সংখ্যা কমপক্ষে দুটির একটি গুণক দ্বারা হ্রাস করে এবং কমপক্ষে n/2 প্রান্তগুলি মুছে দেয় যেখানে n হল জি-তে শীর্ষগুলির সংখ্যা। একটি বোরুভকা ধাপের এফ-ভারী এবং এফ-হালকা প্রান্তগুলির উদাহরণ কার্যকর করা প্রতিটি পুনরাবৃত্তিতে অ্যালগরিদম নির্দিষ্ট বৈশিষ্ট্যযুক্ত প্রান্তগুলি সরিয়ে দেয় যা তাদের ন্যূনতম বিস্তৃত গাছ থেকে বাদ দেয়। এগুলিকে এফ-ভারী প্রান্ত বলা হয় এবং নিম্নরূপ সংজ্ঞায়িত করা হয়। ধরা যাক এইচ-এর আলেখ্যে এফ-কে একটি বন। একটি এফ-ভারী প্রান্ত হল একটি প্রান্ত যা ইউ, ভি-কে সংযুক্ত করে, যার ওজন এফ-এ ইউ থেকে ভি-এর পথে সবচেয়ে ভারী প্রান্তের ওজনের চেয়ে কঠোরভাবে বেশি। (যদি এফ-এ কোনও পথ না থাকে তবে এটির অসীম ওজন রয়েছে বলে মনে করা হয়)। এফ-ভারী নয় এমন যে কোনও প্রান্তকে এফ-লাইট বলা হয়। যদি এফ জি-এর একটি উপ-গ্রাফ হয় তবে চক্রের বৈশিষ্ট্য অনুসারে জি-এর যে কোনও এফ-ভারী প্রান্ত জি-এর ন্যূনতম বিস্তৃত গাছের মধ্যে থাকতে পারে না। একটি বনের পরিপ্রেক্ষিতে, এফ-ভারী প্রান্তগুলি ন্যূনতম বিস্তৃত গাছ যাচাইকরণ অ্যালগরিদম ব্যবহার করে রৈখিক সময়ে গণনা করা যেতে পারে। অ্যালগরিদম ইনপুটঃ একটি গ্রাফ জি যার কোনও বিচ্ছিন্ন শীর্ষ নেই যদি জি খালি থাকে তবে একটি খালি বন ফেরত দিন জি-তে পরপর দুটি বড়ভকা ধাপ চালিয়ে একটি সংকুচিত গ্রাফ জি তৈরি করুন জি-তে প্রতিটি প্রান্ত নির্বাচন করে একটি উপগ্রাফ এইচ তৈরি করুন। ন্যূনতম বিস্তৃত বন এফ পেতে এইচ-এর অ্যালগরিদমটি পুনরাবৃত্তভাবে প্রয়োগ করুন। একটি রৈখিক সময় ন্যূনতম বিস্তৃত গাছ যাচাইকরণ অ্যালগরিদম ব্যবহার করে জি থেকে সমস্ত এফ-ভারী প্রান্তগুলি সরিয়ে ফেলুন (যেখানে এফ হল 3য় ধাপ থেকে বন)। ন্যূনতম বিস্তৃত বন পেতে জি-তে অ্যালগরিদমটি পুনরাবৃত্তিমূলকভাবে প্রয়োগ করুন। আউটপুটঃ জি-এর ন্যূনতম বিস্তৃত বন এবং বোরুভকা ধাপ থেকে সংকুচিত প্রান্ত সঠিকতা গ্রাফের শীর্ষগুলির সংখ্যার উপর আনয়ন দ্বারা প্রমাণিত হয়। মূল মামলাটি তুচ্ছভাবে সত্য। টি * কে জি-এর ন্যূনতম বিস্তৃত গাছ হিসাবে ধরা যাক। একটি বোরুভকা ধাপে নির্বাচিত প্রতিটি প্রান্ত কাটা বৈশিষ্ট্য দ্বারা টি *-তে থাকে এবং সংকুচিত গ্রাফ গঠনের জন্য সরানো প্রান্তগুলির কোনওটিই কাটা বৈশিষ্ট্য (অপ্রয়োজনীয় প্রান্তের জন্য) এবং চক্র বৈশিষ্ট্য (স্ব-লুপগুলির জন্য) দ্বারা টি *-তে থাকে না। ধাপ 2-এ নির্বাচিত না হওয়া টি *-এর অবশিষ্ট প্রান্তগুলি কাটা বৈশিষ্ট্য দ্বারা সংকুচিত গ্রাফের ন্যূনতম বিস্তৃত গাছ গঠন করে (প্রতিটি কাটা একটি সুপারনোড হতে দিন)। মুছে ফেলা প্রতিটি এফ-ভারী প্রান্ত চক্রের বৈশিষ্ট্য দ্বারা ন্যূনতম বিস্তৃত গাছের মধ্যে থাকে না। পরিশেষে এফ 'হল ইন্ডাক্টিভ হাইপোথিসিস দ্বারা সংকুচিত গ্রাফের সর্বনিম্ন বিস্তৃত গাছ। এইভাবে এফ 'এবং বোরুভকা ধাপ থেকে সংকুচিত প্রান্তগুলি ন্যূনতম বিস্তৃত গাছ গঠন করে। কর্মক্ষমতা প্রত্যাশিত কর্মক্ষমতা র্যান্ডম স্যাম্পলিং ধাপের ফলাফল। র্যান্ডম স্যাম্পলিং ধাপের কার্যকারিতা নিম্নলিখিত লেম্মা দ্বারা বর্ণনা করা হয়েছে যা জি-তে এফ-আলোর প্রান্তের সংখ্যার উপর একটি সীমা স্থাপন করে যার ফলে দ্বিতীয় উপ-সমস্যার আকার সীমাবদ্ধ হয়। র্যান্ডম স্যাম্পলিং লেম্মা লেম্মা-ধরা যাক এইচ হল জি-এর একটি উপগ্রাফ যা জি-এর প্রতিটি প্রান্তকে স্বাধীনভাবে সম্ভাব্যতা পি-এর সাথে অন্তর্ভুক্ত করে গঠিত হয় এবং এফ-কে এইচ-এর সর্বনিম্ন বিস্তৃত বন হিসাবে ধরা যাক। জি-তে এফ-আলোর প্রান্তগুলির প্রত্যাশিত সংখ্যা সর্বাধিক এন/পি যেখানে এন হল জি-তে শীর্ষগুলির সংখ্যা। লেমা প্রমাণ করার জন্য জি-এর প্রান্তগুলি পরীক্ষা করুন কারণ সেগুলি এইচ-এর সাথে যুক্ত করা হচ্ছে। জি-তে এফ-আলোর প্রান্তগুলির সংখ্যা এইচ-এর প্রান্তগুলি নির্বাচিত হওয়ার ক্রম থেকে স্বাধীন কারণ সমস্ত নির্বাচন আদেশের জন্য এইচ-এর ন্যূনতম বিস্তৃত বনভূমি একই। প্রমাণের জন্য এইচ-এর জন্য প্রান্তগুলি বেছে নেওয়ার কথা বিবেচনা করুন, একটি সময়ে জি-এর প্রান্তগুলি প্রান্তের ওজনের ক্রমে হালকা থেকে ভারী পর্যন্ত নিয়ে। ই-কে বর্তমান প্রান্ত হিসাবে বিবেচনা করা হচ্ছে। যদি ই-এর শেষ বিন্দুগুলি এইচ-এর দুটি বিচ্ছিন্ন অংশে থাকে তবে ই হল সেই উপাদানগুলিকে সংযুক্ত করার সবচেয়ে হালকা প্রান্ত এবং যদি এটি এইচ-এর সাথে যুক্ত করা হয় তবে এটি কাটা বৈশিষ্ট্য দ্বারা এফ-এ থাকবে। এর অর্থ হল ই হল এফ-লাইট, এটি এইচ-এর সাথে যোগ করা হোক বা না হোক, যেহেতু শুধুমাত্র ভারী প্রান্তগুলি পরবর্তীকালে বিবেচনা করা হয়। যদি ই-এর উভয় প্রান্তবিন্দু এইচ-এর একই অংশে থাকে তবে চক্রের বৈশিষ্ট্য অনুসারে এটি এফ-ভারী (এবং সর্বদা হবে)। তারপর প্রান্ত ই যোগ করা হয় সম্ভাব্যতা পি সহ এইচ-এর সাথে। এইচ-এর সাথে যোগ করা এফ-লাইট প্রান্তের সর্বাধিক সংখ্যা হল এন-1 কারণ এইচ-এর যে কোনও ন্যূনতম বিস্তৃত গাছের এন-1 প্রান্ত রয়েছে। একবার এইচ-এ এন-1 এফ-লাইট প্রান্ত যুক্ত হয়ে গেলে পরবর্তী প্রান্তগুলির কোনওটিই চক্রের বৈশিষ্ট্য দ্বারা এফ-লাইট হিসাবে বিবেচিত হয় না। এইভাবে, জি-তে এফ-আলোর প্রান্তের সংখ্যা এইচ-এর জন্য বিবেচিত এফ-আলোর প্রান্তের সংখ্যা দ্বারা সীমাবদ্ধ, এন-1 এফ-আলোর প্রান্তগুলি আসলে এইচ-এর সাথে যুক্ত হওয়ার আগে। যেহেতু যে কোনও এফ-আলোর প্রান্তটি সম্ভাব্যতা পি-এর সাথে যুক্ত করা হয়, এটি এন-1 হেড উপস্থিত না হওয়া পর্যন্ত মাথা উপরে আসার সম্ভাবনা পি সহ একটি মুদ্রা উল্টানোর সমতুল্য। মুদ্রা উল্টানোর মোট সংখ্যা জি-তে এফ-লাইট প্রান্তের সংখ্যার সমান। মুদ্রা উল্টানোর সংখ্যার বন্টন এন-1 এবং পি পরামিতি সহ বিপরীত দ্বিপদী বন্টন দ্বারা দেওয়া হয়। এই পরামিতিগুলির জন্য এই বন্টনের প্রত্যাশিত মান হল (এন-1)/পি। প্রত্যাশিত বিশ্লেষণ পুনরাবৃত্তিমূলক উপ-সমস্যাগুলিতে করা কাজ উপেক্ষা করে অ্যালগরিদমের একক প্রার্থনায় করা মোট কাজের পরিমাণ ইনপুট গ্রাফের প্রান্তের সংখ্যায় রৈখিক হয়। প্রথম ধাপটি স্থির সময় নেয়। বোরুভকা ধাপগুলি বোরুভকা ধাপ বিভাগে উল্লিখিত প্রান্তের সংখ্যায় সময় রৈখিকভাবে কার্যকর করা যেতে পারে। ধাপ 3 প্রান্তের মধ্য দিয়ে পুনরাবৃত্তি করে এবং প্রত্যেকটির জন্য একটি করে মুদ্রা উল্টায় যাতে এটি প্রান্তের সংখ্যায় রৈখিক হয়। একটি পরিবর্তিত লিনিয়ার টাইম মিনিমাম স্প্যানিং ট্রি ভেরিফিকেশন অ্যালগরিদম ব্যবহার করে চতুর্থ ধাপটি লিনিয়ার টাইমে কার্যকর করা যেতে পারে। যেহেতু অ্যালগরিদমের একটি পুনরাবৃত্তিতে করা কাজটি প্রান্তের সংখ্যায় রৈখিক, তাই অ্যালগরিদমের একটি সম্পূর্ণ দৌড়ে (সমস্ত পুনরাবৃত্তিমূলক কল সহ) করা কাজটি মূল সমস্যার মোট প্রান্তের সংখ্যা এবং সমস্ত পুনরাবৃত্তিমূলক উপ-সমস্যাগুলির একটি ধ্রুবক গুণক দ্বারা আবদ্ধ। অ্যালগরিদমের প্রতিটি আহ্বান সর্বাধিক দুটি উপ-সমস্যা তৈরি করে যাতে উপ-সমস্যার সেট একটি বাইনারি ট্রি গঠন করে। প্রতিটি বোরুভকা ধাপ শীর্ষস্থানের সংখ্যা কমপক্ষে দুই গুণক দ্বারা হ্রাস করে তাই দুটি বোরুভকা ধাপের পরে শীর্ষস্থানের সংখ্যা চার গুণক দ্বারা হ্রাস করা হয়েছে। সুতরাং, যদি মূল গ্রাফের n শীর্ষ এবং m প্রান্ত থাকে তবে গাছের গভীরতায় প্রতিটি উপ-সমস্যা সর্বাধিক n/4d শীর্ষের গ্রাফের উপর থাকে। এছাড়াও গাছটির সর্বাধিক লগ4এন স্তর রয়েছে। রিকার্সন ট্রি সম্পর্কে যুক্তি দেওয়ার জন্য 3য় ধাপের রিকার্সিভ কলের উপ-সমস্যা বাম সন্তানের সমস্যা এবং 5ম ধাপের রিকার্সিভ কলের উপ-সমস্যা ডান সন্তানের সমস্যা হতে দিন। গাছের প্রতিটি বাম পথে প্রান্তের সংখ্যা গণনা করে মূল সমস্যার মোট প্রান্তের সংখ্যা এবং সমস্ত উপ-সমস্যা গণনা করুন। একটি বাম পথ একটি ডান শিশু বা মূল থেকে শুরু হয় এবং বাম শিশুদের পথের মাধ্যমে পৌঁছানো যায় এমন সমস্ত নোড অন্তর্ভুক্ত করে। বাইনারি গাছের বাম দিকের পথগুলি ডানদিকের রেখাচিত্রে নীল রঙে বৃত্তাকারভাবে দেখানো হয়েছে। একটি বাম শিশু সমস্যার প্রতিটি প্রান্ত তার মূল সমস্যার প্রান্ত থেকে (বোরুভকা পদক্ষেপে সংকুচিত প্রান্তগুলি কম) সম্ভাবনা 1/2 সহ নির্বাচন করা হয়। যদি একটি মূল সমস্যার x প্রান্ত থাকে তবে বাম সন্তানের সমস্যার প্রান্তের প্রত্যাশিত সংখ্যা সর্বাধিক x/2 হয়। যদি x একটি এলোমেলো পরিবর্তনশীল X দ্বারা প্রতিস্থাপিত হয় তবে প্রত্যাশার রৈখিকতা দ্বারা বাম চাইল্ড সমস্যা Y-তে প্রান্তের প্রত্যাশিত সংখ্যা দ্বারা দেওয়া হয়। সুতরাং যদি একটি বাম পথের শীর্ষে একটি সমস্যায় প্রান্তের প্রত্যাশিত সংখ্যা k হয় তবে বাম পথের প্রতিটি উপ-সমস্যায় প্রান্তের প্রত্যাশিত সংখ্যার যোগফল সর্বাধিক হয় (জ্যামিতিক সিরিজ দেখুন)। মূলটির এম প্রান্ত রয়েছে তাই প্রান্তের প্রত্যাশিত সংখ্যা 2 মিটারের সমান এবং প্রতিটি ডান উপ-সমস্যায় প্রান্তের প্রত্যাশিত সংখ্যার দ্বিগুণ। প্রতিটি ডান উপ-সমস্যায় প্রান্তের প্রত্যাশিত সংখ্যা মূল সমস্যায় এফ-লাইট প্রান্তের সংখ্যার সমান যেখানে এফ হল বাম উপ-সমস্যার ন্যূনতম বিস্তৃত গাছ। এফ-আলোর প্রান্তের সংখ্যা নমুনা লেমা দ্বারা উপ-সমস্যার শীর্ষগুলির সংখ্যার দ্বিগুণের চেয়ে কম বা সমান। d গভীরতায় একটি উপ-সমস্যায় শীর্ষগুলির সংখ্যা n/4d তাই সমস্ত সঠিক উপ-সমস্যায় শীর্ষগুলির মোট সংখ্যা দ্বারা দেওয়া হয়। সুতরাং, মূল সমস্যা এবং সমস্ত উপ-সমস্যায় প্রান্তের প্রত্যাশিত সংখ্যা সর্বাধিক 2 মি + এন। যেহেতু কোনও বিচ্ছিন্ন শীর্ষবিহীন গ্রাফের জন্য n সর্বাধিক 2 মিটার, তাই অ্যালগরিদমটি প্রত্যাশিত সময় O (m)-এ চলে। সবচেয়ে খারাপ কেস বিশ্লেষণ সবচেয়ে খারাপ কেস রানটাইম বোরুভকার অ্যালগরিদমের রানটাইমের সমতুল্য। এটি ঘটে যদি প্রতিটি আহ্বানের বাম বা ডান উপ-সমস্যার সাথে সমস্ত প্রান্ত যুক্ত করা হয়। এই ক্ষেত্রে অ্যালগরিদমটি বোরুভকার অ্যালগরিদমের অনুরূপ যা n শীর্ষ এবং m প্রান্ত সহ একটি গ্রাফের উপর O (ন্যূনতম {n2, mlogn}) এ চলে। রেফারেন্স আরও পড়া মিনিমাম স্প্যানিং ট্রি ভেরিফিকেশন ইন লিনিয়ার টাইম র্যান্ডমাইজড অ্যালগরিদম স্প্যানিং ট্রি