Expected linear time MST algorithm
எதிர்பார்க்கப்படும் நேரியல் நேர எம்எஸ்டி வழிமுறை என்பது தனிமைப்படுத்தப்பட்ட செங்குத்துகள் இல்லாத எடையுள்ள வரைபடத்தின் குறைந்தபட்ச பரவலான காடுகளைக் கணக்கிடுவதற்கான சீரற்ற வழிமுறையாகும். இது டேவிட் கார்கர், பிலிப் க்ளீன் மற்றும் ராபர்ட் டார்ஜன் ஆகியோரால் உருவாக்கப்பட்டது. இந்த வழிமுறையானது பொர்வ்காவின் வழிமுறை நுட்பங்களையும், நேரியல் நேரத்தில் குறைந்தபட்ச பரவலான மரத்தை சரிபார்க்க ஒரு வழிமுறையையும் நம்பியுள்ளது. இது எதிர்பார்க்கப்படும் நேரியல் செயல்திறனை அடைய வகுத்தல் மற்றும் கைப்பற்றுதல் வழிமுறைகள், பேராசை வழிமுறைகள் மற்றும் சீரற்ற வழிமுறைகள் ஆகியவற்றின் வடிவமைப்பு முன்னுதாரணங்களை ஒருங்கிணைக்கிறது. குறைந்தபட்ச பரவலான மரத்தைக் கண்டுபிடிக்கும் தீர்மானகரமான வழிமுறைகளில் ப்ரைமின் வழிமுறை, க்ருஸ்கலின் வழிமுறை, தலைகீழ்-நீக்குதல் வழிமுறை மற்றும் போர்வ்காவின் வழிமுறை ஆகியவை அடங்கும். கண்ணோட்டம் வழிமுறைக்கான முக்கிய நுண்ணறிவு ஒரு சீரற்ற மாதிரி படியாகும், இது ஒவ்வொரு துணை வரைபடத்திலும் சேர்க்க சீரற்ற முறையில் விளிம்புகளைத் தேர்ந்தெடுப்பதன் மூலம் ஒரு வரைபடத்தை இரண்டு துணை வரைபடங்களாகப் பிரிக்கிறது. வழிமுறை முதல் துணைப் பிரச்சினையின் குறைந்தபட்ச பரவலான காடுகளை மீண்டும் மீண்டும் கண்டறிந்து, குறைந்தபட்ச பரவலான மரத்தில் இருக்க முடியாத வரைபடத்தில் உள்ள விளிம்புகளை நிராகரிக்க ஒரு நேரியல் நேர சரிபார்ப்பு வழிமுறையுடன் இணைந்து தீர்வைப் பயன்படுத்துகிறது. ஒவ்வொரு மறுசுழற்சியிலும் வரைபடத்தின் அளவைக் குறைக்க போர்வ்காவின் வழிமுறையிலிருந்து எடுக்கப்பட்ட ஒரு செயல்முறையும் பயன்படுத்தப்படுகிறது. முறையின் ஒவ்வொரு மறு செய்கையும் போர்வ்கா படி என்று குறிப்பிடப்படும் போர்வ்காவின் வழிமுறையின் தழுவலை நம்பியுள்ளதுஃ உள்ளீடுஃ தனிமைப்படுத்தப்பட்ட செங்குத்துகள் இல்லாத ஒரு வரைபடம் ஜி 1 ஒவ்வொரு உச்சிக்கும், வி 2 இல் இலகுவான விளிம்பு சம்பவத்தைத் தேர்ந்தெடுக்கவும் படி 1 இல் தேர்ந்தெடுக்கப்பட்ட விளிம்புகளால் இணைக்கப்பட்ட ஜி இன் ஒவ்வொரு கூறுகளையும் ஒற்றை உச்சியுடன் மாற்றுவதன் மூலம் ஒரு சுருக்கப்பட்ட வரைபடம் ஜி 'ஐ உருவாக்கவும் 3 ஜி வெளியீட்டில் இருந்து தனிமைப்படுத்தப்பட்ட செங்குத்துகள், சுய சுழற்சிகள் மற்றும் குறைந்தபட்சம் அல்லாத மீண்டும் மீண்டும் விளிம்புகளை அகற்றவும்ஃ படி 1 இல் தேர்ந்தெடுக்கப்பட்ட விளிம்புகள் மற்றும் சுருக்கப்பட்ட வரைபடம் ஜி ஏ போர்வ்கா படி போர்வ்காவின் வழிமுறையின் உள் வளையத்திற்கு சமம், இது ஓ (எம்) நேரத்தில் இயங்குகிறது எனவே, ஒரு போர்வ்கா படி குறைந்தபட்சம் இரண்டு காரணிகளால் வரைபடத்தில் உள்ள செங்குத்துகளின் எண்ணிக்கையைக் குறைக்கிறது மற்றும் குறைந்தபட்சம் n/2 விளிம்புகளை நீக்குகிறது, அங்கு n என்பது G இல் செங்குத்துகளின் எண்ணிக்கை. இவை எஃப்-கனமான விளிம்புகள் என்று அழைக்கப்படுகின்றன, மேலும் அவை பின்வருமாறு வரையறுக்கப்படுகின்றன. H வரைபடத்தில் F ஒரு காடாக இருக்கட்டும். ஒரு F-கனமான விளிம்பு என்பது u, v ஐ இணைக்கும் ஒரு விளிம்பாகும், அதன் எடை F இல் u முதல் v வரையிலான பாதையில் உள்ள கனமான விளிம்பின் எடையை விட கண்டிப்பாக அதிகமாக இருக்கும். (F இல் ஒரு பாதை இல்லையென்றால் அது எல்லையற்ற எடையைக் கொண்டதாகக் கருதப்படுகிறது). எஃப்-ஹெவி இல்லாத எந்த விளிம்பும் எஃப்-லைட் ஆகும். F என்பது G இன் துணை வரைபடமாக இருந்தால், G இல் உள்ள எந்த F-கனமான விளிம்பும் சுழற்சி பண்பு மூலம் G இன் குறைந்தபட்ச பரவலான மரத்தில் இருக்க முடியாது. ஒரு காட்டைப் பொறுத்தவரை, எஃப்-கனமான விளிம்புகளை குறைந்தபட்ச விரிவான மர சரிபார்ப்பு வழிமுறையைப் பயன்படுத்தி நேரியல் நேரத்தில் கணக்கிட முடியும். அல்காரிதம் உள்ளீடுஃ தனிமைப்படுத்தப்பட்ட செங்குத்துகள் இல்லாத ஒரு வரைபடம் G. G காலியாக இருந்தால், ஒரு காலியான காடு திரும்பும், G இல் இரண்டு தொடர்ச்சியான போர்வ்கா படிகளை இயக்கி ஒரு சுருக்கப்பட்ட வரைபடத்தை உருவாக்குங்கள். அதன் குறைந்தபட்ச பரவலான காடு F ஐப் பெற H க்கு வழிமுறையை மீண்டும் மீண்டும் பயன்படுத்தவும். ஒரு நேரியல் நேர குறைந்தபட்ச பரவலான மரம் சரிபார்ப்பு வழிமுறையைப் பயன்படுத்தி G இலிருந்து அனைத்து F-கனமான விளிம்புகளையும் அகற்றவும் (இங்கு F என்பது படி 3 இலிருந்து காடு). குறைந்தபட்ச பரவலான காடுகளைப் பெற G க்கு வழிமுறையை மீண்டும் மீண்டும் பயன்படுத்தவும். வெளியீடுஃ G இன் குறைந்தபட்ச பரவலான காடு மற்றும் போர்வ்கா படிகளிலிருந்து சுருக்கப்பட்ட விளிம்புகள் சரியானது வரைபடத்தில் உள்ள செங்குத்துகளின் எண்ணிக்கையில் தூண்டுவதன் மூலம் நிரூபிக்கப்படுகிறது. அடிப்படை வழக்கு அற்பமான உண்மை. ஒரு போர்வ்கா படியில் தேர்ந்தெடுக்கப்பட்ட ஒவ்வொரு விளிம்பும் வெட்டு பண்பால் டி * இல் உள்ளது மற்றும் சுருக்கப்பட்ட வரைபடத்தை உருவாக்க அகற்றப்பட்ட விளிம்புகள் எதுவும் வெட்டு பண்பு (தேவையற்ற விளிம்புகளுக்கு) மற்றும் சுழற்சி பண்பு (சுய சுழல்களுக்கு) மூலம் டி * இல் இல்லை. படி 2 இல் தேர்ந்தெடுக்கப்படாத T * இன் மீதமுள்ள விளிம்புகள் வெட்டு பண்பால் சுருக்கப்பட்ட வரைபடத்தின் குறைந்தபட்ச பரவலான மரத்தை உருவாக்குகின்றன (ஒவ்வொரு வெட்டும் ஒரு சூப்பர்நோடாக இருக்கட்டும்). நீக்கப்பட்ட ஒவ்வொரு எஃப்-கனமான விளிம்பும் சுழற்சி பண்பால் குறைந்தபட்ச பரவலான மரத்தில் இல்லை. இறுதியாக F 'என்பது தூண்டல் கருதுகோள் மூலம் சுருக்கப்பட்ட வரைபடத்தின் குறைந்தபட்ச பரவலான மரமாகும். இவ்வாறு எஃப் 'மற்றும் போருவ்கா படிகளிலிருந்து சுருக்கப்பட்ட விளிம்புகள் குறைந்தபட்ச பரவலான மரத்தை உருவாக்குகின்றன. செயல்திறன் எதிர்பார்க்கப்படும் செயல்திறன் சீரற்ற மாதிரி படியின் விளைவாகும். சீரற்ற மாதிரி படியின் செயல்திறன் பின்வரும் லெம்மாவால் விவரிக்கப்படுகிறது, இது G இல் உள்ள F-ஒளி விளிம்புகளின் எண்ணிக்கையில் ஒரு வரம்பை வைக்கிறது, இதன் மூலம் இரண்டாவது துணை சிக்கலின் அளவைக் கட்டுப்படுத்துகிறது. சீரற்ற மாதிரி லெம்மா லெம்மா-H என்பது G இன் ஒவ்வொரு விளிம்பையும் சுயாதீனமாக நிகழ்தகவு p உடன் சேர்ப்பதன் மூலம் உருவாகும் G இன் துணை வரைபடமாக இருக்கட்டும், மேலும் F என்பது H இன் குறைந்தபட்ச பரவலான காடாக இருக்கட்டும். G இல் எதிர்பார்க்கப்படும் F-ஒளி விளிம்புகளின் எண்ணிக்கை அதிகபட்சமாக n/p ஆகும், அங்கு n என்பது G இல் செங்குத்துகளின் எண்ணிக்கை. லெம்மாவை நிரூபிக்க G இன் விளிம்புகளை அவை H உடன் சேர்க்கப்படுவதை ஆராயவும். G இல் உள்ள F-ஒளி விளிம்புகளின் எண்ணிக்கை H இன் விளிம்புகள் தேர்ந்தெடுக்கப்படும் வரிசையில் இருந்து சுயாதீனமாக உள்ளது, ஏனெனில் H இன் குறைந்தபட்ச பரவலான காடு அனைத்து தேர்வு வரிசைகளுக்கும் ஒரே மாதிரியாக உள்ளது. ஆதாரத்திற்காக, H க்கான விளிம்புகளைத் தேர்ந்தெடுப்பதன் மூலம் G ஒன்றின் விளிம்புகளை ஒரு நேரத்தில் விளிம்பு எடையின் வரிசையில் இலகுவானது முதல் கனமானது வரை எடுத்துக் கொள்ளுங்கள். e என்பது தற்போதைய விளிம்பாக கருதப்படுவதாக இருக்கட்டும். e இன் இறுதிப் புள்ளிகள் H இன் இரண்டு துண்டிக்கப்பட்ட கூறுகளில் இருந்தால், e என்பது அந்த கூறுகளை இணைக்கும் இலகுவான விளிம்பாகும், மேலும் இது H உடன் சேர்க்கப்பட்டால் அது வெட்டு பண்பால் F இல் இருக்கும். இதன் பொருள் என்னவென்றால், ஈ என்பது எஃப்-ஒளி, இது எச் உடன் சேர்க்கப்படுகிறதா இல்லையா என்பதைப் பொருட்படுத்தாமல், கனமான விளிம்புகள் மட்டுமே பின்னர் கருதப்படுகின்றன. e இன் இரண்டு இறுதிப் புள்ளிகளும் H இன் ஒரே கூறுகளில் இருந்தால், அது சுழற்சி பண்பால் F-கனமாக இருக்கும் (மற்றும் எப்போதும் இருக்கும்). விளிம்பு e பின்னர் நிகழ்தகவு p உடன் H உடன் சேர்க்கப்படுகிறது. H இன் எந்த குறைந்தபட்ச பரவலான மரமும் n-1 விளிம்புகளைக் கொண்டிருப்பதால், H உடன் சேர்க்கப்படும் F-ஒளி விளிம்புகளின் அதிகபட்ச எண்ணிக்கை n-1 ஆகும். n-1 F-ஒளி விளிம்புகள் H இல் சேர்க்கப்பட்டவுடன், அடுத்தடுத்த விளிம்புகள் எதுவும் சுழற்சி பண்பால் F-ஒளி என்று கருதப்படுவதில்லை. எனவே, G இல் உள்ள F-ஒளி விளிம்புகளின் எண்ணிக்கை, H இல் n-1 F-ஒளி விளிம்புகள் உண்மையில் சேர்க்கப்படுவதற்கு முன்பு H க்கு கருதப்படும் F-ஒளி விளிம்புகளின் எண்ணிக்கையால் கட்டுப்படுத்தப்படுகிறது. எந்தவொரு F-ஒளி விளிம்பும் நிகழ்தகவு p உடன் சேர்க்கப்படுவதால், இது n-1 தலைகள் தோன்றும் வரை தலைகள் மேலே வரும் நிகழ்தகவு p உடன் ஒரு நாணயத்தை புரட்டுவதற்கு சமம். நாணய சுழல்களின் மொத்த எண்ணிக்கை G இல் உள்ள F-ஒளி விளிம்புகளின் எண்ணிக்கைக்கு சமம். நாணய சுழல்களின் எண்ணிக்கையின் விநியோகம் n-1 மற்றும் p அளவுருக்களுடன் தலைகீழ் இருமப் பகிர்வு மூலம் வழங்கப்படுகிறது. இந்த அளவுருக்களுக்கு இந்த விநியோகத்தின் எதிர்பார்க்கப்படும் மதிப்பு (n-1)/p ஆகும். எதிர்பார்க்கப்படும் பகுப்பாய்வு தொடர்ச்சியான துணை சிக்கல்களில் செய்யப்படும் வேலையை புறக்கணிப்பது, வழிமுறையின் ஒற்றை அழைப்பில் செய்யப்படும் மொத்த வேலையின் அளவு உள்ளீட்டு வரைபடத்தில் உள்ள விளிம்புகளின் எண்ணிக்கையில் நேரியல் ஆகும். படி 1 நிலையான நேரத்தை எடுக்கும். போர்வ்கா படி பிரிவில் குறிப்பிடப்பட்டுள்ளபடி விளிம்புகளின் எண்ணிக்கையில் நேர நேர்கோட்டில் போர்வ்கா படிகளை செயல்படுத்தலாம். படி 3 விளிம்புகள் வழியாக மீண்டும் மீண்டும் செய்கிறது மற்றும் ஒவ்வொன்றிற்கும் ஒரு நாணயத்தை புரட்டுகிறது, எனவே இது விளிம்புகளின் எண்ணிக்கையில் நேரியல் ஆகும். மாற்றியமைக்கப்பட்ட நேரியல் நேர குறைந்தபட்ச விரிவாக்க மர சரிபார்ப்பு வழிமுறையைப் பயன்படுத்தி படி 4 ஐ நேரியல் நேரத்தில் செயல்படுத்தலாம். வழிமுறையின் ஒரு மறு செய்கையில் செய்யப்படும் வேலை விளிம்புகளின் எண்ணிக்கையில் நேரியல் என்பதால், வழிமுறையின் ஒரு முழுமையான ஓட்டத்தில் செய்யப்படும் வேலை (அனைத்து தொடர்ச்சியான அழைப்புகளும் உட்பட) ஒரு நிலையான காரணி மடங்கு அசல் சிக்கலில் உள்ள மொத்த விளிம்புகள் மற்றும் அனைத்து தொடர்ச்சியான துணை சிக்கல்களால் கட்டுப்படுத்தப்படுகிறது. வழிமுறையின் ஒவ்வொரு அழைப்பும் அதிகபட்சம் இரண்டு துணை சிக்கல்களை உருவாக்குகிறது, எனவே துணை சிக்கல்களின் தொகுப்பு ஒரு பைனரி மரத்தை உருவாக்குகிறது. ஒவ்வொரு போர்வ்கா படியும் செங்குத்துகளின் எண்ணிக்கையை குறைந்தது இரண்டு காரணிகளால் குறைக்கிறது, எனவே இரண்டு போர்வ்கா படிகளுக்குப் பிறகு செங்குத்துகளின் எண்ணிக்கை நான்கு காரணிகளால் குறைக்கப்பட்டுள்ளது. எனவே, அசல் வரைபடத்தில் n செங்குத்துகள் மற்றும் m விளிம்புகள் இருந்தால், மரத்தின் ஆழம் d இல் ஒவ்வொரு துணைப் பிரச்சினையும் அதிகபட்சம் n/4d செங்குத்துகளின் வரைபடத்தில் இருக்கும். மேலும் இந்த மரம் பெரும்பாலான log4n நிலைகளைக் கொண்டுள்ளது. மறுநிகழ்வு மரத்தைப் பற்றி நியாயப்படுத்த, படி 3 இல் உள்ள மறுநிகழ்வு அழைப்பில் இடது குழந்தை சிக்கல் துணைப் பிரச்சினையாக இருக்கட்டும், மேலும் படி 5 இல் உள்ள மறுநிகழ்வு அழைப்பில் வலது குழந்தை சிக்கல் துணைப் பிரச்சினையாக இருக்கட்டும். மரத்தின் ஒவ்வொரு இடது பாதையிலும் உள்ள விளிம்புகளின் எண்ணிக்கையை எண்ணுவதன் மூலம் அசல் சிக்கலில் உள்ள மொத்த விளிம்புகளின் எண்ணிக்கையையும் அனைத்து துணை சிக்கல்களையும் எண்ணுங்கள். ஒரு இடது பாதை வலது குழந்தை அல்லது வேரில் தொடங்குகிறது மற்றும் இடது குழந்தைகளின் பாதை வழியாக அடையக்கூடிய அனைத்து முனைகளையும் உள்ளடக்கியது. ஒரு பைனரி மரத்தின் இடது பாதைகள் வலதுபுறத்தில் உள்ள வரைபடத்தில் நீல நிறத்தில் வட்டமிடப்பட்டுள்ளன. ஒரு இடது குழந்தை சிக்கலின் ஒவ்வொரு விளிம்பும் அதன் பெற்றோர் சிக்கலின் விளிம்புகளிலிருந்து தேர்ந்தெடுக்கப்படுகிறது (போர்வ்கா படிகளில் சுருக்கப்பட்ட விளிம்புகள் குறைவாக) நிகழ்தகவு 1/2 உடன். ஒரு பெற்றோர் சிக்கலில் x விளிம்புகள் இருந்தால், இடது குழந்தை சிக்கலில் எதிர்பார்க்கப்படும் விளிம்புகளின் எண்ணிக்கை அதிகபட்சமாக x/2 ஆகும். x ஒரு சீரற்ற மாறி X ஆல் மாற்றப்பட்டால், எதிர்பார்ப்பின் நேரியல் மூலம் இடது குழந்தை சிக்கலான Y இல் எதிர்பார்க்கப்படும் விளிம்புகளின் எண்ணிக்கை வழங்கப்படுகிறது. எனவே ஒரு இடது பாதையின் மேற்புறத்தில் உள்ள ஒரு சிக்கலில் எதிர்பார்க்கப்படும் விளிம்புகளின் எண்ணிக்கை k ஆக இருந்தால், இடது பாதையில் உள்ள ஒவ்வொரு துணைப் பிரச்சினையிலும் எதிர்பார்க்கப்படும் விளிம்புகளின் கூட்டுத்தொகை அதிகபட்சமாக இருக்கும் (வடிவியல் தொடரைப் பார்க்கவும்). வேர் m விளிம்புகளைக் கொண்டுள்ளது, எனவே எதிர்பார்க்கப்படும் விளிம்புகளின் எண்ணிக்கை 2 மீ மற்றும் ஒவ்வொரு வலது துணை சிக்கலிலும் எதிர்பார்க்கப்படும் விளிம்புகளின் எண்ணிக்கையை விட இரண்டு மடங்கு சமம். ஒவ்வொரு வலது துணை சிக்கலிலும் எதிர்பார்க்கப்படும் விளிம்புகளின் எண்ணிக்கை பெற்றோர் சிக்கலில் எஃப்-ஒளி விளிம்புகளின் எண்ணிக்கைக்கு சமம், அங்கு எஃப் என்பது இடது துணை சிக்கலின் குறைந்தபட்ச பரவலான மரமாகும். எஃப்-ஒளி விளிம்புகளின் எண்ணிக்கை மாதிரி லெம்மாவால் துணைப் பிரச்சினையில் உள்ள செங்குத்துகளின் எண்ணிக்கையை விட இரண்டு மடங்கு குறைவாகவோ அல்லது சமமாகவோ இருக்கும். d ஆழத்தில் ஒரு துணைப்பிரச்சினையில் உள்ள செங்குத்துகளின் எண்ணிக்கை n/4d ஆகும், எனவே அனைத்து சரியான துணைப்பிரச்சினைகளிலும் உள்ள செங்குத்துகளின் மொத்த எண்ணிக்கை பின்வருமாறு கொடுக்கப்படுகிறது. எனவே, அசல் சிக்கல் மற்றும் அனைத்து துணை சிக்கல்களிலும் எதிர்பார்க்கப்படும் விளிம்புகளின் எண்ணிக்கை அதிகபட்சம் 2m + n ஆகும். தனிமைப்படுத்தப்பட்ட செங்குத்துகள் இல்லாத ஒரு வரைபடத்திற்கு n அதிகபட்சம் 2 மீ என்பதால், வழிமுறை எதிர்பார்க்கப்பட்ட நேரத்தில் O (m) இல் இயங்குகிறது. மோசமான வழக்கு பகுப்பாய்வு மோசமான வழக்கு இயக்க நேரம் போர்வ்காவின் வழிமுறையின் இயக்க நேரத்திற்கு சமம். ஒவ்வொரு அழைப்பிலும் இடது அல்லது வலது துணைப் பிரச்சினையில் அனைத்து விளிம்புகளும் சேர்க்கப்பட்டால் இது நிகழ்கிறது. இந்த வழக்கில் வழிமுறை n செங்குத்துகள் மற்றும் m விளிம்புகளுடன் ஒரு வரைபடத்தில் O (குறைந்தபட்சம் {n2, mlogn}) இல் இயங்கும் போர்வ்காவின் வழிமுறையை ஒத்திருக்கிறது. குறிப்புகள் மேலும் வாசிப்பு குறைந்தபட்ச பரவலான மர சரிபார்ப்பு நேரியல் நேர சீரற்ற வழிமுறைகள் பரவலான மரத்தில்