క్రుస్కాల్ యొక్క అల్గోరిథం - ఒక సరైన ఫ్రేమ్ నిర్మాణం

ప్రారంభ 19 వ శతాబ్దం మహాగణితశాస్త్రజ్ఞుడు లో బెర్లిన్ నుండి జాకబ్ స్టినేర్ వారి పొడవు తక్కువ ఉంది కనుక మూడు గ్రామాలు కనెక్ట్ ఎలా పనిని. తరువాత, అతను సమస్య సంగ్రహంగా: ఇది ఒక సమతలంలో ఒక పాయింట్ కనుగొనేందుకు అవసరం, అది నుండి n ఇతర పాయింట్లకు దూరం అత్యల్ప ఉన్నాయి. 20 వ శతాబ్దంలో, ఈ అంశంపై పని కొనసాగుతోంది. ఇది కొన్ని పాయింట్లు పడుతుంది మరియు వాటి మధ్య దూరం తక్కువ అని విధంగా వాటిని కనెక్ట్ నిర్ణయించారు. ఈ అన్ని సమస్య యొక్క ఒక ప్రత్యేక నిదర్శనంగా అధ్యయనం చేయబడుతుంది.

"అత్యాశ" అల్గోరిథం

క్రుస్కాల్ యొక్క అల్గోరిథం "అత్యాశ" అల్గోరిథం (గ్రేడియంట్ కూడా పిలుస్తారు) సూచిస్తుంది. ఆ యొక్క సారాంశం - ప్రతి అడుగు అత్యధిక విజయంగా పేర్కొంటుంది. ఎల్లప్పుడూ, "అత్యాశ" అల్గోరిథంలు సమస్యకు ఉత్తమ పరిష్కారం అందిస్తుంది. అక్కడ వారి అనువర్తన నిర్దిష్ట పనులను వారు వాంఛనీయ పరిష్కారం ఇచ్చే చూపిస్తున్న, ఒక సిద్ధాంతం ఉంది. ఈ matroids సిద్ధాంతం. క్రుస్కాల్ యొక్క అల్గోరిథం వంటి సమస్యలను సూచిస్తుంది.

కనీసం మృతదేహాన్ని బరువు ఫైండింగ్

వీక్షించినవి అల్గోరిథం ఒక సరైన ఫ్రేమ్ లెక్కింపు నిర్మిస్తుంది. ఈ విధంగా సమస్య. డాన్ సమాంతర అంచులు మరియు ఉచ్చులు లేకుండా గ్రాఫ్ undirected, మరియు అంచులు సమితి ప్రతి అంచు ఇ సంఖ్య కేటాయించే బరువు ఫంక్షన్ w, ఇవ్వబడుతుంది - బరువు ప్రక్కటెముకల - w (ఇ). ప్రక్కటెముక బహుత్వ ప్రతి ఉపవర్గాలను బరువు దాని అంచులు బరువులు మొత్తం. ఒక చిన్న బరువు అస్థిపంజరం కనుగొనేందుకు అవసరం.

వివరణ

క్రుస్కాల్ యొక్క అల్గోరిథం పనిచేస్తుంది. మొదటి, ప్రాధమిక గ్రాఫ్ అన్ని అంచులు బరువులు క్రమంలో అమర్చబడి ఉంటాయి. మొదట్లో, ఫ్రేమ్ ఏ ఎముకలు కలిగి కానీ శీర్షముల కలిగి లేదు. ఇది ఒక విస్తరించి అడవి మృతదేహాన్ని యొక్క ఇప్పటికే నిర్మించిన భాగం అల్గోరిథం యొక్క తదుపరి దశ తర్వాత, ఒక అంచున జోడిస్తారు. ఇది ఏకపక్ష ఎంపిక లేదు. గ్రాఫ్ అన్ని అంచులు, ఫ్రేమ్ సంబంధించని, ఎరుపు మరియు ఆకుపచ్చ పిలువబడుతుంది. ప్రతి ఎరుపు అంచులు పైన నిర్మాణం అటవీ కనెక్టివిటీ కింద అదే భాగం లో ఉన్నాయి, మరియు ఆకుపచ్చ బల్లలను - వివిధ. అందువలన, మీరు ఎరుపు అంచు జోడిస్తే, ఒక చక్రం ఉంటుంది, మరియు ఉంటే ఆకుపచ్చ - చెక్క కనెక్ట్ భాగాలు ఈ దశ తర్వాత కురిశాయి ఒకటి కంటే తక్కువగా ఉంటుంది. అందువలన, ఫలితంగా నిర్మాణ ఎరుపు అంచు జోడించడానికి కాదు, కానీ ఏ ఆకుపచ్చ అంచు అటవీ చెయ్యచ్చు. మరియు కనిష్ట బరువు ఒక ఆకుపచ్చ అంచు జతచేస్తుంది. ఫలితంగా కనీస బరువు ఒక ప్రణాళిక.

అమలు

ప్రస్తుత అటవీ ఎఫ్ ఇది కనెక్టివిటీ రంగంలో శీర్షాల సెట్ విభజిస్తుంది సూచించడానికి (తమ యూనియన్ రూపాల్లో F, మరియు వారు ఉమ్మడి మూలకాలు ఉండవు). ఎరుపు శీర్షాల రెండు అంచులు వద్ద వారు ఒక ముక్క లో ఉంటాయి. పార్ట్ (x) - చర్య ప్రతి శీర్షం x కోసం పేరుతో ఒక భాగం తిరిగి, x చెందినది. యునైట్ (x, y) - x మరియు y యొక్క భాగాలు మరియు ఇతర భాగాలు కలపడం కలిగి, ఒక కొత్త విభజన రూపొందించారు ఒక విధానం. n లెట్ - అంచుల సంఖ్య. ఈ భావనలు క్రుస్కాల్ యొక్క అల్గోరిథం లో చేర్చబడ్డాయి. అమలు:

1. n వ ఆరోహణ బరువులు కు 1 నుండి గ్రాఫ్ అన్ని అంచులు ఏర్పాట్లు. (ఐ, ద్వి - నేను అత్యున్నత అంచున నంబర్ తో).

2. కోసం i = 1 n చేయండి.

3. x: = పార్ట్ (AI).

4. y =: పార్ట్ (BI).

5. x సమాన y అప్పుడు యునైట్ (x, y) ఒకవేళ, అంచు F i సంఖ్యలో ఉన్నాయి.

సవ్యత

T లెట్ - దాని అసమగ్ర ఫ్రేమ్ - అసలు గ్రాఫ్ యొక్క ఫ్రేమ్ క్రుస్కాల్ అల్గోరిథం మరియు S ఉపయోగించి నిర్మించారు. మేము నిరూపించుకోవాలి (T) w w (ఎస్) కంటే ఎక్కువ కాదు.

M లెట్ - రెక్కల S, P యొక్క బహుత్వ - రెక్కల బహుత్వ T. ఉంటే S కు T సమానం కాదు, అప్పుడు ఒక ఫ్రేమ్ పక్కటెముక et టి, ఎస్ ఎస్ et చెందని చేరివుండు చక్రం, అది సి సి అంటారు ఏ అంచు ఎస్ నుండి, చెందిన తొలగించడానికి ఉంది ఎస్ మేము అంచులు మరియు శీర్షాలు అదే ఎందుకంటే, ఒక కొత్త ఫ్రేమ్ పొందటానికి. దీని బరువు w (ఎస్), నుండి w (ET) ఇకపై ఒక శక్తి క్రుస్కాల్ అల్గోరిథం లో w (ఎస్) కంటే ఎక్కువ కాదు. ఈ ఆపరేషన్ (ప్రత్యామ్నాయంగా ఎముకలు న T S పక్కటెముకలు) టి ప్రతి తదుపరి అందుకున్న ఫ్రేము బరువు అందుకుంటారు ఉన్నంత పునరావృతమవుతుంది సూచిస్తుంది మునుపటి బరువు కంటే ఎక్కువ కాదు అని (T) w w (ఎస్) కంటే ఎక్కువ కాదు.

క్రుస్కాల్ క్రమసూత్ర పద్ధతి యొక్క పుష్టి matroids న rado-ఎడ్మండ్స్ సిద్ధాంతం నుండి అనుసరిస్తుంది.

అప్లికేషన్ ఉదాహరణలు క్రుస్కాల్ అల్గోరిథం

నోడ్స్ a, b, c, d, ఇ మరియు పక్కటెముకలు (a, b), (a, e), (బి, సి), (బి, ఇ) తో డాన్ గ్రాఫ్, (c, d), (సి, ఇ) (D, E). అంచులు బరువులు పట్టికలో చిత్రంలో చూపబడింది. మొదట్లో, నిర్మాణం అటవీ F గ్రాఫ్ యొక్క శీర్షముల కలిగి మరియు ఏ ఎముకలు కలిగి లేదు. అల్గోరిథం క్రుస్కాల్ మొదటి పక్కటెముక (a, e), బరువు అత్యల్ప కలిగి నుండి, అప్పుడు పక్కటెముక జోడించడానికి, మరియు శీర్షాలు ఒక మరియు ఇ వివిధ భాగాలు ఉన్నాయి కలప కనెక్టివిటీ F (పక్కటెముక (a, e) ఆకుపచ్చ) (c, d), ఎందుకంటే కనీసం గ్రాఫ్ అంచులు అంచు బరువు, F కు చెందిన లేదు, మరియు అది ఆకుపచ్చ, అదే కారణాల అంచున వచ్చే తరువాత (a, b). కానీ అంచు (బి, ఇ), పాస్ అతను మరియు మిగిలిన అంచులు కనీస బరువు, అది ఎరుపు ఎందుకంటే అయినప్పటికీ: శీర్షాల బి మరియు ఇ అటవీ F అదే కనెక్ట్ భాగం చెందిన, మేము అంచు (బి, ఇ) కు F జోడిస్తే, ఏర్పడుతుంది, ఉంది చక్రం. అప్పుడు ఆకుపచ్చ అంచు (బి, సి), పాస్ ఎరుపు అంచు (సి, ఇ), ఆపై d, ఇ జోడించారు. వరుసగా అందువలన, అంచులు కలుపుతారు (a, e), (c, d), (a, b), (బి, సి). nihera సరైన ఫ్రేమ్ నుండి మరియు అసలు గ్రాఫ్ కలిగి. కాబట్టి ఈ సందర్భంలో అది ఒక అల్గోరిథం నిర్వహించే క్రుస్కాల్. ఒక ఉదాహరణ చూపించాం.

చిత్రంలో రెండు కనెక్ట్ భాగాలు కలిగి ఉన్న ఒక గ్రాఫ్, చూపిస్తుంది. బోల్డ్ పంక్తులు సరైన ఫ్రేమ్ పక్కటెముకలు (ఆకుపచ్చ) క్రుస్కాల్ అల్గారిథమ్ ఉపయోగించి నిర్మించారు సూచిస్తున్నాయి.

తక్కువ బరువు ఒక అస్థిపంజరం, అతనికి నిర్మించారు అల్గోరిథం ఉపయోగించి - టాప్ చిత్రాన్ని అసలు గ్రాఫ్, మరియు దిగువన చూపిస్తుంది.

జోడించారు ప్రక్కటెముక క్రమం (1.6); (0,3), (2,6) లేదా (2,6), (0,3) - ముఖ్యమైనది కాదు; (3,4); (0,1), (1,6) లేదా (1,6), (0,1), కూడా శ్రద్ధ (5,6).

క్రుస్కాల్ యొక్క అల్గోరిథం ఆచరణీయ అనువర్తనం ప్రతి దేశంలో కొత్త నివాస ఆస్తులు ఉన్న ప్రాంతాలు, అలాగే ఇతర సందర్భాల్లో గాస్కెట్ సమాచార, రోడ్లు ఆప్టిమైజ్, ఉదాహరణకు, తెలుసుకుంటాడు.