கிருஸ்கால் வழிமுறை - ஒரு உகந்த கட்டமைப்பை கட்டுமான

19 ஆம் நூற்றாண்டின் ஆரம்பத்தில் geometer பேர்லினில் இருந்து ஜேகப் ஸ்டெய்னர் என்று அவற்றின் நீளம் குறுகிய மூன்று கிராமங்களில் இணைக்க எப்படி பணி அமைக்க வேண்டும். பின்னர், அவர் பிரச்சனை சுருக்கி: அது ஒரு விமானம் ஒரு புள்ளி கண்டுபிடிக்க வேண்டும், N மற்ற புள்ளிகள் அதை தொலைவு அளவு குறைவாக இருந்தது. 20 ஆம் நூற்றாண்டில், அது இந்த தலைப்பில் வேலை தொடர்கிறது. அது ஒரு சில புள்ளிகள் எடுத்து அவர்களுக்கு இடையே தூரம் குறுகிய என்று போன்ற ஒரு வழியில் அவர்களை இணைக்க முடிவு செய்யப்பட்டது. இந்த அனைத்து ஆய்வு செய்யப்படும் பிரச்சனையின் ஒரு சிறப்பு வகையாகும்.

"பேராசை" வழிமுறை

கிருஸ்கால் வழிமுறை "பேராசை" வழிமுறை (சாய்வு என்றும் அழைக்கப்படுவது) குறிக்கிறது. அந்த சாரம் - ஒவ்வொரு அடியிலும் உயர்ந்த வெற்றி. எப்போதும், "பேராசை" வழிமுறைகளும் பிரச்சினைக்கு சிறந்த தீர்வு வழங்கும். ஒரு கோட்பாடு குறிப்பிட்ட பணிகளை தங்களின் விண்ணப்பத்தில் அவர்கள் உகந்த தீர்வு கொடுக்கும் காண்பிக்கப்படுகிறது உள்ளது. இந்த matroids பற்றிய கோட்பாடு ஆகும். கிருஸ்கால் வழிமுறை போன்ற பிரச்சினைகள் குறிக்கிறது.

ஒரு குறைந்தபட்ச உடலில் எடை கண்டுபிடித்து

பார்க்கப்பட்டவை வழிமுறை ஒரு உகந்த சட்ட எண்ணிக்கை கட்டமைக்கிறது. பின் வருமாறு பிரச்சனை. டான் இணை விளிம்புகள் மற்றும் சுழல்கள் இல்லாமல் வரைபடம் undirected, மற்றும் ஓரங்களில் தொகுப்பு ஒவ்வொரு விளிம்பு இ எண்ணை ஒப்படைக்கும் எடை செயல்பாடு W, கொடுக்கப்பட்ட - எடை, தூக்குதல் விலா எலும்பு - W (உ). விலா பன்மை ஒவ்வொரு துணைக்குழு எடை அதன் முனைகளை எடைகள் கூடுதல் ஆகும். ஒரு சிறிய எடை எலும்புக்கூட்டை கண்டுபிடிக்க தேவை.

விளக்கம்

கிருஸ்கால் வழிமுறை செயல்படுகிறது. முதலாவதாக, ஆரம்ப வரைபடத்தின் அனைத்து விளிம்புகள் எடைகள் ஏறுவரிசைப்படி அமைக்கப்பட்டுள்ளன. ஆரம்பத்தில், பிரேம் எந்த விலா கொண்டிருக்கும் ஆனால் அனைத்து முனைகளை அடங்கும் இல்லை. இது ஒரு பலவகையான காடாக இருக்கிறது உடலில், ஏற்கனவே கட்டப்பட்ட பகுதியாக வழிமுறையை அடுத்த கட்ட நடவடிக்கையாக பிறகு, ஒரு விளிம்பில் சேர்க்கப்படுகிறது. அந்த தன்னிச்சையாக தேர்வு இல்லை. வரைபடத்தின் அனைத்து விளிம்புகள், பிரேம் சேர்ந்த இல்லை, சிவப்பு மற்றும் பச்சை அழைக்க முடியும். வெவ்வேறு - ஒவ்வொரு சிவப்பு விளிம்புகள் மேல் பச்சை டாப்ஸ் கட்டுமான காட்டில் இணைப்பு கீழ் அதே கூறு உள்ளன. எனவே, நீங்கள் சிவப்பு விளிம்பில் சேர்க்க என்றால், ஒரு சுழற்சி, மற்றும் என்றால் பச்சை - இந்த நிலைக்குப் பின்னர் பெற்றார் மரம் இணைக்கப்பட்டுள்ளது கூறுகள் ஒன்றுக்கொன்று காட்டிலும் குறைவாக இருக்கும். இதனால், இதன் விளைவாக கட்டுமான எந்த சிவப்பு விளிம்பில் சேர்க்க முடியாது, ஆனால் எந்த பச்சை விளிம்பில் காட்டில் கிடைக்கும் சேர்க்க முடியும். மற்றும் குறைந்தபட்ச எடை கொண்ட ஒரு பச்சை விளிம்பில் சேர்க்கிறது. விளைவாக குறைந்தபட்ச எடை நிலைகளின் கட்டமைப்பாக இருக்கிறது.

செயல்படுத்த

இப்போதைய வனக் எஃப் அது இணைப்பு துறையில் முனைகளை தொகுப்பு பிரிக்கிறது குறிக்க (தங்கள் தொழிற்சங்க வகையிலான F ஆகவும், அவர்கள் பொதுவற்ற உள்ளன). சிவப்பு முனைகளை இரு முனைகளை மணிக்கு அவர்கள் ஒரு துண்டு ஆகியனவாகும். பகுதி (x) என்பது - ஒவ்வொரு உச்சி x க்காக பெயர் ஒரு பகுதியை கொடுக்கிறது என்று செயல்பாடு, அது x சொந்தமானது. யுனைட் (இது x, y) - x மற்றும் y இன் பகுதிகள் மற்றும் அனைத்து பிற பகுதிகளில் இணைந்த கொண்ட ஒரு புதிய பகிர்வு உருவாக்குகிறார் என்று ஒரு நடைமுறை. N நாம் - விளிம்புகள் எண்ணிக்கை. இந்த அனைத்து கருத்துக்கள் கிருஸ்கால் வழிமுறை அடங்கியுள்ளன. நடைமுறைப்படுத்தல்:

1. அன்-வது ஏறுவரிசையில் எடைகள் 1 முதல் வரைபடத்தின் அனைத்து விளிம்புகள் ஏற்பாடு. (AI, இரு - நான் நுனி விளிம்பில் எண்ணுடன்).

2. நான் = 1 மற்றும் n செய்ய.

3. எக்ஸ்: = பகுதி (AI).

4. ஒய்: = பகுதி (இரு).

5. x, பின்னர் y சமமாக யுனைட் (இது x, y) இல்லை என்றால், விளிம்பில் எஃப் நான் எண் சேர்க்கத்.

சரியான

டி நாம் - அதன் தன்னிச்சையான சட்ட - அசல் வரைபடத்தின் சட்ட கிருஸ்கால் வழிமுறை மற்றும் S பயன்படுத்தி கட்டமைக்கப்பட்டுள்ளன. நாம் என்று நிரூபிக்க வேண்டும் W (டி) W (எஸ்) விட அதிகமாக உள்ளது.

நாம் எம் - துடுப்புகள் எஸ், பி பன்முக - துடுப்புகள் ஒரு பன்முக டி என்றால் எஸ் டி சமமாக இல்லை, பின்னர் ஒரு சட்ட விலா எலும்பு மற்றும் டி, எஸ் எஸ் மற்றும் சொந்தமான இல்லை சுழற்சி, அது சி சி அழைக்கப்படுகிறது, ஏதாவது முனையை எஸ் இருந்து நீக்க சேர்ந்த அடுத்திரு உள்ளது எஸ் நாம் ஒரு புதிய சட்ட பெற விளிம்புகள் மற்றும் முனைகளை சொல்கிறோம் ஏனெனில். அதன் எடை W (எஸ்), முதல் W (மற்றும்) இனி ஒரு சக்தி கிருஸ்கால் வழிமுறைகளில் W (களை) விட அதிகமாக உள்ளது. இந்தச் செயல்பாடு (விலாப் பகுதியில் மாற்றாக டி எஸ் விலா) நீண்ட டி பெறும் ஒவ்வொரு அடுத்தடுத்த பெற்றார் பிரேம் எடை உள்ளிடப்பட்டிருக்கும் குறிக்கிறது முந்தைய எடை, விட அதிகம் என்று W (டி) W (எஸ்) விட அதிகமாக உள்ளது.

கிருஸ்கால் வழிமுறை உறுதித்தன்மை matroids மீது Rado-எட்மண்ட்ஸ் தேற்றம் இருந்து பின்வருமாறு.

விண்ணப்ப எடுத்துக்காட்டுகள் கிருஸ்கால் வழிமுறை

முனையங்களும், ஆ, இ, ஈ, மின் மற்றும் விலா (அ, ஆ), (ஒரு உ), (ஆ, இ), (ஆ, இ) உடன் டான் வரைபடம், (இ, ஈ), (இ, உ) , (ஈ, உ). விளிம்புகள் எடைகள் அட்டவணையில் மற்றும் படத்தில் காண்பிக்கப்பட்டுள்ளது. ஆரம்பத்தில், கட்டுமான காட்டில் F இன் வரைபடத்தினை அனைத்து முனைகளை கொண்டுள்ளது மற்றும் எந்த விலா இல்லை. அல்காரிதம் கிருஸ்கால் முதல் விலா எலும்பு (அ, இ), எடை குறைந்த இருந்ததால் விலா எலும்பு சேர்க்க, மற்றும் முனைகளை ஒரு மற்றும் மின் வெவ்வேறு பகுதிகளுக்கு உள்ளன மர இணைப்பு எஃப் (விலா எலும்பு (அ, இ) பச்சை), பின்னர் (இ, ஈ), ஏனெனில் வரைபடம் விளிம்புகள் என்று குறைந்தது இந்த விளிம்பில் எடை, எஃப் சேர்ந்த இல்லை, அது பச்சையாக இருக்கிறது, அதே காரணங்கள் விளிம்பில் பெறுவார் பிறகு (ஒரு ஆ). ஆனால் விளிம்பில் (ஆ, இ) அவரும் மீதமுள்ள விளிம்புகள் குறைந்தபட்ச எடை, அது சிவப்பு ஏனெனில் கூட, கடந்து: முனைகளை ஆ மற்றும் இ காட்டில் இணைப்பு எஃப் அதே கூறு சேர்ந்தவை, முதல் F விளிம்பில் (ஆ, இ) நாம் சேர்க்க என்றால், அமைக்கப்படுகின்றது உள்ளது சுழற்சி. பின்னர் பச்சை விளிம்பில் (ஆ, இ), கடந்து சிவப்பு விளிம்பில் (இ, உ), பின்னர் ஈ, மின் சேர்க்கப்பட்டது. இவ்வாறு, விளிம்புகள் சேர்க்கப்படும் தொடர்ந்து (அ, இ), (இ, ஈ), (அ, ஆ), (ஆ, இ). nihera உகந்த சட்ட இருந்து மற்றும் அசல் வரைபடம் கொண்டுள்ளது. எனவே இந்த வழக்கில் அது ஒரு படிமுறை செயல்பட்டு கிருஸ்கால். ஒரு உதாரணம் காட்டப்பட்டுள்ளது.

எண்ணிக்கை இரண்டு இணைக்கப்பட்ட கூறுகளின் ஏற்படுவதே வரைபடம் காட்டுகிறது. தைரியமான வரிகளை உகந்த சட்ட விலாக்கள் (பச்சை) கிருஸ்கால் வழிமுறை மூலம் கட்டமைக்கப்படுகின்றன குறிப்பிடுகின்றன.

குறைந்த எடை ஒரு எலும்புக்கூட்டை, அவருக்கென்று உருவாக்கித் தந்த வழிமுறை பயன்படுத்தி - மேல் படம் அசல் வரைபடம் மற்றும் கீழே காட்டுகிறது.

சேர்க்கப்பட்டது விலா வரிசைமுறை (1.6); (0,3), (2,6) அல்லது (2,6), (0,3) - முக்கிய அல்ல; (3,4); (0,1), (1,6) அல்லது (1,6), (0,1), மேலும் கவலை (5,6).

கிருஸ்கால் வழிமுறை நடைமுறை ஒவ்வொரு நாட்டிலும் புதிய பண்ணை வீடுகளில் இடங்களில், அதே போல் மற்ற நேரங்களில் இணைப்பிறுக்கி தொடர்புகள், சாலைகள் மேம்படுத்த, எடுத்துக்காட்டாக காண்கிறது.