Kruskal ዎቹ ስልተ - አንድ ለተመቻቸ ማዕቀፍ ግንባታ

መጀመሪያ በ 19 ኛው ክፍለ ዘመን geometer ውስጥ በርሊን ከ ያኮፕ ስቲነር ያላቸውን ርዝመት አጭር ነበር ስለዚህም ሦስት መንደሮች ለማገናኘት እንዴት ያለውን ተግባር ማዘጋጀት. ከጊዜ በኋላ ችግሩ ጠቅለል: አንድ በአውሮፕላን ውስጥ አንድ ነጥብ ማግኘት ያስፈልጋል, n ሌሎች ነጥቦች ጋር ከ ርቀት ዝቅተኛ ነበሩ. በ 20 ኛው ክፍለ ዘመን, በዚህ ጉዳይ ላይ መስራት ይቀጥላል. ይህም ጥቂት ነጥቦችን መውሰድ እና በእነርሱ መካከል ያለው ርቀት አጭር መሆኑን እንዲህ ያለ መንገድ እነሱን ለማገናኘት ወሰንን ነበር. ይህ ሁሉ እየተጠና ችግር ልዩ ሁኔታ ነው.

"ስግብግብ" ስልተ ቀመር

Kruskal ዎቹ ስልተ በ "ስግብግብ" ስልተ (በተጨማሪም ተብሎ ቅልመት) ያመለክታል. ሰዎች ማንነት - በእያንዳንዱ ደረጃ ላይ ከፍተኛው አሸነፉ. አይደለም ሁልጊዜ, "ስግብግብ" ስልተ ችግር ምርጥ መፍትሔ ይሰጣሉ. አንድ ንድፈ ተኮር ተግባራትን ያላቸውን ማመልከቻ ውስጥ እነርሱ ከብሔራዊ መፍትሔ መስጠት መሆኑን በማሳየት, አለ. ይህ matroids ንድፈ ሐሳብ ነው. Kruskal ዎቹ ስልተ እንዲህ ያሉ ችግሮች ያመለክታል.

ቢያንስ በድን ክብደት ማግኘት

የታየ ስልተ አንድ ለተመቻቸ ክፈፍ ቆጠራ constructs. እንደሚከተለው የሱን ችግር ነው. ዳን ትይዩ ጠርዞች እና ቀለበቶች ያለ ግራፍ በተከሰቱ, እና ጠርዞች ስብስብ እያንዳንዱ ጠርዝ ሠ ወደ ቁጥር ይመድባል ይህም ስ ክብደት ተግባር, የተሰጠው ነው - ክብደት የጎድን አጥንት - (ሠ) w. ጎድን መካከል የብዙ እያንዳንዱ ታህታይ ያለውን ክብደት በውስጡ ጠርዝ ያለውን ክብደት ድምር ነው. ትንሽ ክብደት ያለውን አጽም ማግኘት ያስፈልጋል.

መግለጫ

Kruskal ዎቹ ስልተ ይሰራል. በመጀመሪያ, የመጀመሪያ ግራፍ ሁሉ ጠርዝ ወደ ክብደቶች ቅደም ሲወጣ ዝግጅት ነው. መጀመሪያ, ፍሬም ማንኛውም የጎድን ሊይዝ ነገር ግን ሁሉ የመገናኛዎች ያካትታል አይደለም. አንድ ያልተሳካላቸው ደን ነው በድን, ያለውን ቀደም የተገነቡ ክፍል ወደ ስልተ ቀጣዩ ደረጃ በኋላ, አንድ ጠርዝ ታክሏል ነው. ይህ በዘፈቀደ የተመረጠ አይደለም. ግራፍ ሁሉም ጠርዝ ወደ ክፈፉ አባል አይደለም, ቀይ እና አረንጓዴ ተብሎ ይችላል. በእያንዳንዱ ቀይ ጠርዝ ጫፍ ግንባታ የደን ተያያዥነት ስር በተመሳሳይ ክፍል ውስጥ ናቸው, እና አረንጓዴ ጕልላቶች - የተለያዩ. ወደ ቀይ ጠርዝ ላይ ለማከል ከሆነ ስለዚህ በዚያ አንድ ዑደት ነው, እና ከሆነ አረንጓዴ - ይህን እርምጃ በኋላ የተቀበለው እንደ እንጨት የተገናኙ ክፍሎች ከአንድ ያነሰ ይሆናል. በመሆኑም ምክንያት የግንባታ ምንም ቀይ ጠርዝ ማከል ይችላሉ, ነገር ግን ማንኛውም አረንጓዴ ጠርዝ ደን ለማግኘት ሊታከሉ ይችላሉ. እና አነስተኛ ክብደት ጋር አንድ አረንጓዴ ጠርዝ ያክላል. ውጤቱም አነስተኛ ክብደት አንድ ማዕቀፍ ነው.

ትግበራ

ረ ይህ ግንኙነት መስክ ውስጥ የመገናኛዎች ስብስብ ያካፍላል የአሁኑ ደን ያመለክታል (ጥምረታቸውን ቅጾች F, እና እነሱ የየቅል ናቸው). ቀይ የመገናኛዎች መካከል በሁለቱም ጫፎቹ ላይ አንድ ቁራጭ ይተኛል. ክፍል (x) - ለእያንዳንዱ ነቁጥን x ለ ስም አንድ ክፍል ይመልሳል ያለውን ተግባር, ይህም x የርሱ ብቻ ነው. ይኖር (x, y) - x እና y ክፍሎች ሁሉ ሌሎች ክፍሎች በማጣመር የያዘ, አዲስ ክፍልፋይ ያንጻል የሆነ አሠራር. n እንመልከት - ጠርዝ ብዛት. እነዚህ ሁሉ ጽንሰ Kruskal ዎቹ ስልተ ውስጥ ተካተዋል. ትግበራ:

1. n-ኛ ሲከፈት ክብደት ወደ 1 ኛ እስከ ግራፍ ሁሉ ጠርዞች ማመቻቸት. (ጋይን, bi - እኔ የሚይዝ ጠርዝ ቁጥር ጋር).

2. ለ i = 1 n ማድረግ.

3. x: = ክፍል (AI).

4. የ y: = ክፍል (bi).

5. x አይደለም እኩል ከዚያም y ይኖር (x, y) የሚያደርግ ከሆነ, ጠርዝ ረ i ቁጥር ጋር ለማካተት.

በትክክል

ቲ እንመልከት - በውስጡ የዘፈቀደ ፍሬም - የመጀመሪያው ግራፍ ክፈፍ ወደ Kruskal ስልተ ቀመር እና S በመጠቀም ይገነባሉ. (T) (S) ወ አይበልጥም ስ እኛ መሆኑን ማረጋገጥ አለብን.

M እንመልከት - ክንፍና ኤስ, P ውስጥ የብዙ - ቲ ከሆነ S ቲ እኩል አይደለም ክንፍ የሆነ የብዙ ቁጥር, ከዚያም አንድ ክፈፍ የጎድን et ቲ, ኤስ ኤስ et አባል አይደለም, ይህ ሲ ሲ ተብሎ ዑደት, ማንኛውም ጠርዝ es ከ ለማስወገድ አባል adjoin አለ ጠርዞቹን እና የመገናኛዎች ተመሳሳይ ስለሆነ ኤስ እኛ አዲስ ፍሬም ማግኘት. በውስጡ ክብደት (S), W (et) ጀምሮ ከእንግዲህ ወዲህ አንድ ኃይል Kruskal ስልተ ውስጥ (es) ወ ስ አይበልጥም. ይህ ክወና (የጎድን ላይ ምትክ T S የጎድን) እስካለ ቲ እያንዳንዱ በቀጣይነት ተቀበሉ ክፈፍ ክብደት መቀበል እንደ ተደጋጋሚ ይሆናል የሚያመለክተው ቀደም ክብደት, አይበልጥም ነው (T) (S) ወ አይበልጥም w.

Kruskal የሰጠው ስልተ ያለውን ጠንካሬ matroids ላይ Rado-Edmonds መካከል የካልኩለስ ከ ይከተላል.

የመተግበሪያ ምሳሌዎች Kruskal ስልተ

የአንጓዎች a, b, ሐ, መ, ሠ እና ጎድን (ሀ, ለ), (ሀ, ሠ), (ለ, ሐ), (ለ, ሠ) ጋር ዳን ግራፍ, (ሐ, መ), (ሐ, ሠ) , (መ, ሠ). ጠርዞች መካከል ክብደት ባለው ሠንጠረዥ ውስጥ እና ቁጥር ውስጥ ይታያሉ. መጀመሪያ, የግንባታ ደን ረ ግራፍ ሁሉ የመገናኛዎች ይዟል ማንኛውም የጎድን አልያዘም. ከዚያም, ሠራት ክብደት ዝቅተኛ ነበር ጀምሮ አልጎሪዝም Kruskal በመጀመሪያ, የጎድን አጥንት (ሀ, ሠ), ማከል እና የመገናኛዎች የሆነ እና ሠ እንጨት ተያያዥነት F (ሠራት; (ሀ, ሠ) አረንጓዴ ነው) በተለያዩ ክፍሎች ውስጥ ናቸው (ሐ, መ), ምክንያቱም ግራፍ ጠርዞች መካከል ቢያንስ በዚህ ጠርዝ ክብደት ሳይሆን F ንብረት, እንዲሁም አረንጓዴ ነው, ተመሳሳይ ምክንያቶች ጠርዝ እናከናውን ከዚያም ለ (ሀ, ለ). ነገር ግን ጫፍ (ለ, ሠ) እርሱም የቀሩት ጠርዝ ዝቅተኛ ክብደት, ቀይ ስለሆነ እንኳ አልፈዋል ነው: ወደ የመገናኛዎች ለ እና ሠ ደን ግንኙነት F ተመሳሳይ አካል አባል, እኛ F ወደ ጫፍ (ለ, ሠ) ለማከል ከሆነ, ሠራኸኝ ነው ዑደት. ከዚያም አረንጓዴ ጠርዝ (ለ, ሐ), አልፈዋል ነው ቀይ ጠርዝ (ሐ, ሠ), ከዚያም መ, ሠ አክለዋል. በመሆኑም, ጠርዞች አክለዋል ናቸው በቅደም ተከተል (ሀ, ሠ), (ሐ, መ), (ሀ, ለ), (ለ, ሐ). እና nihera ለተመቻቸ ፍሬም ጀምሮ የመጀመሪያውን ግራፍ ያካትታል. በመሆኑም በዚህ ሁኔታ ውስጥ አንድ ስልተ ይሰራል Kruskal. አንድ ምሳሌ ይታያል.

ይህ አኃዝ ሁለት የተገናኙ ክፍሎች ያካተተ አንድ ግራፍ ያሳያል. የ ደማቅ መስመሮች (አረንጓዴ) የ Kruskal ስልተቀመር በመጠቀም የሠራው ከፍተኛውን ፍሬም ጎድን ያመለክታሉ.

ዝቅተኛ ክብደት አንድ አጽም, ከእርሱ የተሰራ የ ስልተቀመር በመጠቀም በማድረግ - የላይኛው ስዕል የመጀመሪያው ግራፍ እና ግርጌ ያሳያል.

ወደ ታክሏል የጎድን ተከታታይነት (1.6); (0,3), (2,6) ወይም (2,6), (0,3) - አስፈላጊ አይደለም; (3,4); (0,1), (1,6) ወይም (1,6), (0,1), እንዲሁም እንክብካቤ (5,6).

Kruskal ዎቹ ስልተ በእያንዳንዱ አገር ውስጥ አዲስ የመኖሪያ ቤት ገዝ አካባቢዎች, እንዲሁም በሌሎች ሁኔታዎች ውስጥ gasket ግንኙነቶች መንገዶች ለማመቻቸት, ለምሳሌ, ተግባራዊ ማመልከቻ ያገኛል.