Kruskal د الګوریتم - د مطلوبو چوکاټ د جوړولو

په 19th century geometer په لومړيو څخه د برلین Jakob شتاينر د دې چې د دوی په اوږدوالي د ټولو لنډه وه چې څنګه د درې کلیو سره نښلوي د دنده ټاکل. وروسته، هغه ستونزه خالصه: دا الزمه ده چې په يوه الوتکه یو ټکی د موندلو، له دا N نورو ټکو د واټن د ټیټ وو. په 20th century، دا دوام ته يې پر دې موضوع کار کوي. وپتيل شوه چې د يو څو ټکو واخلي او په داسې يوه لاره چې د دوی تر منځ د واټن د ټولو لنډه وه د هغوی سره ونښلوي. دا ټول د ستونزې یوه ځانګړې صورت کېږي مطالعه.

"حريص" الګوریتم

Kruskal د الګوریتم ته اشاره کوي د "حريص" الګوریتم (پړاويز هم نومیږی) ته. د هغه ذات - پر هر ګام لوړه ورکړه. تل نه، "حريص" الگوريتم د ستونزې د حل تر ټولو غوره کړي. يوه تيوري ده، ښيي چې د ځانګړو دندو خپل غوښتنلیک دوی مناسب حل ورکړي. دا د matroids تيوري. Kruskal د الګوریتم ته اشاره کوي لکه ستونزې.

لږ تر لږه جسد وزن موندل

کتل الګوریتم جوړ او د یو د مطلوبو چوکاټ شمېرنې. د دا ستونزه په لاندې ډول دي. دان موازي څنډو او کړۍ_ګانې پرته ګراف undirected، او د څنډو د ټولګه ده W د وزن دنده، چې د هر څنډه e شمېر سازي ورکول - د وزن د ضلع - W (e). د د د سفلی د اکثريت د هر فرعي وزن کې د خپل څنډو د وزن مجموعه ده. د اړتیا د یوه کوچنۍ وزن د اسکلټ پيدا کړي.

Description

Kruskal د الګوریتم کار کوي. لومړی، د لومړنۍ ګراف ټولو څنډو کې د وزن د ترتيبلو ډول ترتيب شوي دي. په پیل کې، نه په چوکاټ کې هر ضلع نه لري خو ټولې څوکې شامل دي. د د جسد، چې د ده د يو پروت ځنګله د لا جوړ برخه د الګوریتم بل ګام وروسته، د یو څنډه ده زياته کړه. دا پخپل سر دی غوره نه. چی د ګراف ټول څنډو، نه په چوکاټ پورې اړوند، سور او زرغون په نامه شي. د هر سور څنډو سر کې د جوړولو د ځنګل د اتصال لاندې ورته جز دي، او د شنه چنګکونه - توپير لري. له همدې امله، که تاسو ته د سره څنډه کړئ، هلته د یوې دورې له دی، او که د شنه - په توګه دا ګام وروسته تر لاسه لرګي سره وصل برخې به له يوه څخه کمه وي. په همدې ډول، په پایله جوړول کولای شي د سور څنډه نه نه کړئ، خو له کوم شنه څنډه زياته کړه کولای شي چې د ځنګل ترلاسه کړي. او زیاتوي سره لږ تر لږه د وزن يو شنه څنډه. په پايله کې د لږ تر لږه د وزن د یو چوکاټ.

د پلي

د اوسني د ځنګله اف دا د اتصال په ډګر کې د څوکې د سیټ وېشي کښلی (د هغوی د اتحاديې د فورمو F، او دوی دي disjoint). په د سره د څوکو د دواړو څنډو دوی په یوه ټوټه دروغ. برخه (x) - د دنده چې د هر هغه څوکه چې x د نوم يوه برخه د راګرځي، دا پورې x. Unite (x، y) - يوه طرزالعمل چې د يوه نوي وېش جوړوي، د x او y برخو او ټول په نورو برخو کې د ګډو شامل دي. راځئ n - د څنډو شمیره. دا ټول مفاهیمو په Kruskal د الګوریتم شامل دي. تطبیق:

1. د N-مه د ترتيبلو ډول وزن د 1st څخه د ګراف د ټولو څنډو بندوبست وکړي. (AI، دوه - زه له څوکه څنډه شمېر).

2. د i = 1 څخه تر N نه.

3. x: = برخه (AI).

4. y: = برخه (دوه).

5. که x مساوي y بيا Unite (x، y) نه کوي، سره په څنډه F زه شمير شامل دي.

صحيح

راځئ چې د T - خپل سري چوکاټ - د اصلي ګراف چوکاټ د Kruskal الګوریتم او S د په کارولو سره جوړ شوي دي. موږ باید ثابته کړي چې د W (T) څخه W (ص) زیات نه دی.

راځئ چې د M - د دانجن S، P اکثريت - د دانجن ماتو د T. که S مساوي T نه وي، نو هلته ده یوه چوکاټ ضلع et T، نه س س et پورې adjoin د دوران، دا ت ج په نوم له هر څنډه es لرې، پورې S. موږ يو نوی چوکاټ تر لاسه کړي، ځکه چې د څنډو او د څوکو یو شان وي. د خپل وزن په پرتله W (ص)، ځکه چې W (et) نه په يو قدرت Kruskal الګوریتم W (es) زیات نه دی. دا عمليات (عوض T S پر سفلی ضلع) به تر هغه په توګه T. لاسه د هر ورپسې ترلاسه چوکاټ وزن تکرار شي د پخواني وزن، چې implies څخه زياته نه ده چې W (T) څخه W (ص) زیات نه دی.

د Kruskal د الګوریتم ځواکمنتیا پر matroids د Rado-Edmonds theorem څخه په لاندې ډول.

کاریال مثالونه Kruskal الګوریتم

سره د غوټو د A، B، C، D، E او سفلی (A، B)، (A، E)، (B، C)، (ب، e) دان ګراف، (c، d)، (c، e) ، (d، e). د څنډو وزن په جدول او په انځور کې ښودل شوي دي. په پیل کې، د ساختماني ځنګل F د ګراف د ټولې څوکې لري او نه کوم ضلع لري. الګوریتم Kruskal لومړي ځل لپاره د ضلع ضلع (A، E) کړئ، ځکه د وزن د ټیټ درلود، او د څوکې د A او E په مختلفو برخو څخه دي د چارتراشو اتصال F (ضلع (A، E) شين دی)، نو (C، D)، ځکه چې چې لږ تر لږه دې د ګراف په څنډو څنډه وزن، د F نه پورې، او دا شين دی، نو د همدې دلايلو له نړوالې څنډه (A، B). خو په څنډه (ب، e) د تصويب، که څه هم هغه او د لږ تر لږه د پاتې څنډو وزن، ځکه چې دا سور دی: د څوکې د B او پست ته د ځنګل د اتصال F ورته جز پورې، چې ده، که موږ په څنډه (ب، e) ته F اضافه، جوړه شوې ده دوران. بيا زياته کړه شنه څنډه (B، C) وفات شو سور دی څنډه (c، e)، او بیا d، e. په دې ډول، څنډو زياته دي نښلو (a، e)، (c، d)، (A، B)، (B، C). له 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 د الګوریتم عملي موندلي دي، د مثال په توګه، د ګازکيټ مخابراتو، سړکونو کې په هر هېواد کې د نوي کور ملکیتونو د سيمې، په توګه او همدارنګه د نورو قضیو اخستل دي.