Šajā rakstā mēs apspriedīsim aptverošo koku un minimālo stiepuma koku. Bet pirms virzīties tieši uz aptverošo koku, vispirms apskatīsim īsu grafika un tā veidu aprakstu.

Grafiks

Grafu var definēt kā virsotņu un malu grupu, lai savienotu šīs virsotnes. Grafiku veidi ir norādīti šādi:

Nevirzīts grafiks:Nevirzītais grafs ir grafs, kurā visas malas nenorāda uz kādu konkrētu virzienu, t.i., tās nav vienvirziena; tie ir divvirzienu. To var definēt arī kā grafiku ar V virsotņu kopu un E malu kopu, katrai malai savienojot divas dažādas virsotnes.Savienotais grafiks:Savienots grafs ir grafs, kurā vienmēr pastāv ceļš no virsotnes uz jebkuru citu virsotni. Grafs ir savienots, ja mēs varam sasniegt jebkuru virsotni no jebkuras citas virsotnes, sekojot malām jebkurā virzienā.Novirzīts grafiks:Virzītos grafikus sauc arī par digrāfiem. Grafs ir virzīts grafs (vai digrāfs), ja visas malas, kas atrodas starp jebkurām grafa virsotnēm vai mezgliem, ir vērstas vai tām ir noteikts virziens.

Tagad pāriesim uz tēmu, kas aptver koku.

Kas ir aptverošs koks?

Aptverošo koku var definēt kā nevirzīta savienota grafa apakšgrafu. Tas ietver visas virsotnes kopā ar mazāko iespējamo malu skaitu. Ja kāda virsotne tiek izlaista, tā nav aptverošs koks. Aptverošais koks ir diagrammas apakškopa, kurai nav ciklu, un to arī nevar atvienot.

Aptverošais koks sastāv no (n-1) malām, kur 'n' ir virsotņu (vai mezglu) skaits. Aptverošā koka malām var būt vai nebūt piešķirts svars. Visiem iespējamajiem aptverošajiem kokiem, kas izveidoti no dotā grafa G, būtu vienāds virsotņu skaits, bet šķautņu skaits aptverošajā kokā būtu vienāds ar virsotņu skaitu dotajā grafā mīnus 1.

Pilnīgam nevirzītam grafikam var būt n^n-2 aptverošo koku skaits kur n ir virsotņu skaits grafikā. Pieņemsim, ja n = 5 , maksimālais iespējamais aptverošo koku skaits būtu 5^5-2= 125.

Aptverošā koka pielietojumi

Būtībā aptverošo koku izmanto, lai atrastu minimālo ceļu, lai savienotu visus grafikas mezglus. Daži no izplatītākajiem aptverošā koka pielietojumiem ir uzskaitīti šādi:

• Klasteru analīze
• Civilo tīklu plānošana
• Datortīkla maršrutēšanas protokols

Tagad sapratīsim aptverošo koku, izmantojot piemēru.

Izvērsta koka piemērs

Pieņemsim, ka grafiks ir -

Kā minēts iepriekš, aptverošais koks satur tādu pašu virsotņu skaitu kā grafs, virsotņu skaits iepriekš minētajā grafikā ir 5; tāpēc aptverošajā kokā būs 5 virsotnes. Laiduma koka šķautnes būs vienādas ar virsotņu skaitu grafā mīnus 1. Tātad, aptverošajā kokā būs 4 malas.

Daži no iespējamiem aptverošajiem kokiem, kas tiks izveidoti no iepriekš minētā grafika, ir norādīti šādi:

Virziena koka īpašības

Dažas aptverošā koka īpašības ir norādītas šādi:

• Savienota grafika G var būt vairāk nekā viens aptverošais koks.
• Aptverošajam kokam nav neviena cikla vai cilpas.
• Aptverošs koks ir minimāli savienots, tāpēc, noņemot vienu malu no koka, grafs tiks atvienots.
• Aptverošs koks ir maksimāli aciklisks, tāpēc, pievienojot kokam vienu malu, tiks izveidota cilpa.
• Var būt maksimums n^n-2 aptverošo koku skaits, ko var izveidot no pilna grafika.
• Ir aptverošs koks n-1 malas, kur “n” ir mezglu skaits.
• Ja grafs ir pilns grafs, tad aptverošo koku var konstruēt, noņemot maksimālās (e-n+1) malas, kur 'e' ir šķautņu skaits un 'n' ir virsotņu skaits.

Tātad, aptverošais koks ir savienotā grafika G apakškopa, un nav atvienota grafika aptverošā koka.

Minimālais platuma koks

Minimālo stiepuma koku var definēt kā stiepuma koku, kurā malas svaru summa ir minimāla. Aptverošā koka svars ir to svaru summa, kas piešķirti stiepjošā koka malām. Reālajā pasaulē šo svaru var uzskatīt par attālumu, satiksmes slodzi, sastrēgumiem vai jebkuru nejaušu vērtību.

Minimālā stiepuma koka piemērs

Ar piemēra palīdzību sapratīsim minimālo aptverošo koku.

Iepriekš minētā grafika malu summa ir 16. Tagad daži no iespējamiem aptverošajiem kokiem, kas izveidoti no iepriekš minētā grafika, ir:

Tātad minimālais aptverošais koks, kas tiek izvēlēts no iepriekš minētajiem aptverošajiem kokiem dotajā svērtajā diagrammā, ir -

Minimālā stiepuma koka pielietojumi

Minimālā stiepuma koka pielietojumi ir norādīti šādi:

• Minimālo laiduma koku var izmantot ūdensapgādes tīklu, telekomunikāciju tīklu un elektrotīklu projektēšanai.
• To var izmantot, lai kartē atrastu ceļus.

Algoritmi minimālajam aptverošajam kokam

Minimālo aptverošo koku var atrast no svērtā grafika, izmantojot tālāk norādītos algoritmus.

• Prima algoritms
• Kruskala algoritms

Apskatīsim abu iepriekš uzskaitīto algoritmu īsu aprakstu.

Prima algoritms - Tas ir mantkārīgs algoritms, kas sākas ar tukšu aptverošu koku. To izmanto, lai no grafika atrastu minimālo aptverošo koku. Šis algoritms atrod malu apakškopu, kas ietver katru grafa virsotni tā, lai malu svaru summu varētu samazināt līdz minimumam.

diskrētais matemātikas noliegums

Lai uzzinātu vairāk par prim algoritmu, varat noklikšķināt uz tālāk esošās saites - https://www.javatpoint.com/prim-algorithm

Kruskal algoritms - Šis algoritms tiek izmantots arī, lai atrastu savienotā svērtā grafika minimālo aptverošo koku. Kruskal algoritms arī seko mantkārīgai pieejai, kas katrā posmā atrod optimālu risinājumu, nevis koncentrējas uz globālo optimālo.

Lai uzzinātu vairāk par prim algoritmu, varat noklikšķināt uz tālāk esošās saites - https://www.javatpoint.com/kruskal-algorithm

Tātad, tas viss par rakstu. Cerams, ka raksts jums būs noderīgs un informatīvs. Šeit mēs esam apsprieduši aptverošo koku un minimālo aptverošo koku, kā arī to īpašības, piemērus un lietojumus.