TechCodeview

Tässä artikkelissa keskustelemme virittävästä puusta ja vähimmäisvirittävästä puusta. Mutta ennen kuin siirryt suoraan kohti virittävää puuta, katsotaanpa ensin lyhyt kuvaus kaaviosta ja sen tyypeistä.

Kaavio

Graafi voidaan määritellä ryhmäksi pisteitä ja reunoja, jotka yhdistävät nämä kärjet. Kaavioiden tyypit on annettu seuraavasti -

Suuntaamaton kaavio:Suuntaamaton graafi on graafi, jonka kaikki reunat eivät osoita mihinkään tiettyyn suuntaan, ts. ne eivät ole yksisuuntaisia; ne ovat kaksisuuntaisia. Se voidaan myös määritellä graafiksi, jossa on joukko V-pisteitä ja joukko E-reunoja, ja jokainen reuna yhdistää kaksi erilaista kärkeä.Yhdistetty kaavio:Yhdistetty graafi on graafi, jossa polku on aina olemassa kärjestä mihin tahansa toiseen kärkeen. Graafi on yhdistetty, jos voimme saavuttaa minkä tahansa kärjen mistä tahansa toisesta kärjestä seuraamalla reunoja kumpaankin suuntaan.Suunnattu kaavio:Suunnatut graafit tunnetaan myös digrafeina. Graafi on suunnattu graafi (tai digraafi), jos kaikki graafin pisteiden tai solmujen välissä olevat reunat ovat suunnattuja tai niillä on määrätty suunta.

Siirrytään nyt puun ylittävään aiheeseen.

Mikä on ylittävä puu?

Virtaava puu voidaan määritellä suuntaamattoman yhdistetyn graafin osagraafiksi. Se sisältää kaikki kärjet sekä mahdollisimman vähän reunoja. Jos jokin kärkipiste puuttuu, se ei ole virittävä puu. Virittävä puu on graafin osajoukko, jossa ei ole jaksoja, eikä sitä myöskään voi irrottaa.

Virittävä puu koostuu (n-1) reunasta, missä 'n' on kärkien (tai solmujen) lukumäärä. Virittävän puun reunoilla voi olla painoja tai ei niitä. Kaikilla mahdollisilla annetusta graafista G luoduilla virittävillä puilla olisi sama määrä pisteitä, mutta virittävän puun reunojen määrä olisi yhtä suuri kuin annetun graafin kärkien lukumäärä miinus 1.

Täydellinen suuntaamaton graafi voi olla n^n-2 ylittäviä puita missä n on graafin kärkien lukumäärä. Oletetaan, jos n = 5 , suurin mahdollinen virittävän puiden lukumäärä olisi 5^5-2= 125.

Virittävän puun sovellukset

Pohjimmiltaan virittävän puun avulla löydetään minimipolku graafin kaikkien solmujen yhdistämiseksi. Jotkut virittävän puun yleisistä sovelluksista on lueteltu seuraavasti -

• Ryhmäanalyysi
• Siviiliverkoston suunnittelu
• Tietokoneverkon reititysprotokolla

Ymmärretään nyt virittävä puu esimerkin avulla.

Esimerkki virittävästä puusta

Oletetaan, että kaavio on -

Kuten edellä on käsitelty, virittävän puu sisältää saman määrän pisteitä kuin graafi, edellä olevan graafin kärkien lukumäärä on 5; siksi virittävä puu sisältää 5 kärkeä. Virtaavan puun reunat ovat yhtä suuria kuin graafin kärkien lukumäärä miinus 1. Virittävässä puussa on siis 4 reunaa.

Jotkut yllä olevasta kaaviosta luoduista mahdollisista virittävistä puista on esitetty seuraavasti -

Virittävän puun ominaisuudet

Jotkut virittävän puun ominaisuuksista on annettu seuraavasti -

• Yhdistetyssä graafissa G voi olla useampi kuin yksi virittävä puu.
• Virittävässä puussa ei ole syklejä tai silmukkaa.
• Ylivoimainen puu on minimaalisesti kytketty, joten yhden reunan poistaminen puusta katkaisee graafin yhteyden.
• Ylivoimainen puu on maksimaalisesti asyklinen, joten yhden reunan lisääminen puuhun luo silmukan.
• Maksimi voi olla n^n-2 kokonaisesta kaaviosta luotavien virittävien puiden lukumäärä.
• Ylittävällä puulla on n-1 reunat, missä 'n' on solmujen lukumäärä.
• Jos graafi on täydellinen graafi, niin virittävä puu voidaan muodostaa poistamalla maksimireunat (e-n+1), missä 'e' on reunojen lukumäärä ja 'n' on kärkien lukumäärä.

Virittävä puu on siis yhdistetyn graafin G osajoukko, eikä irrallisen graafin virittävä puu ole olemassa.

Vähintään ulottuva puu

Vähimmäisvirittävä puu voidaan määritellä virittäväksi puuksi, jossa reunan painojen summa on pienin. Virittävän puun paino on virittävän puun reunoihin annettujen painojen summa. Reaalimaailmassa tätä painoa voidaan pitää etäisyydenä, liikennekuormituksena, ruuhkana tai minkä tahansa satunnaisena arvona.

Esimerkki minimivirittävästä puusta

Ymmärretään esimerkin avulla pienin virittävä puu.

Yllä olevan graafin reunojen summa on 16. Nyt jotkin yllä olevasta kaaviosta luoduista mahdollisista virittävistä puista ovat -

Joten, pienin virittävä puu, joka valitaan yllä olevista virittävistä puista annetulle painotetulle kaaviolle on -

Vähimmäisen virittävän puun sovellukset

Vähimmäisvirittävän puun sovellukset on annettu seuraavasti -

• Vähimmäisvirittävän puun avulla voidaan suunnitella vesijohtoverkkoja, tietoliikenneverkkoja ja sähköverkkoja.
• Sitä voidaan käyttää polkujen etsimiseen kartalta.

Algoritmit minimivirittävälle puulle

Pienin virittävä puu voidaan löytää painotetusta graafista käyttämällä alla olevia algoritmeja -

• Primin algoritmi
• Kruskalin algoritmi

Katsotaanpa lyhyt kuvaus molemmista yllä luetelluista algoritmeista.

Primin algoritmi - Se on ahne algoritmi, joka alkaa tyhjästä virittävästä puusta. Sitä käytetään etsimään kaaviosta pienin virittävä puu. Tämä algoritmi löytää reunojen osajoukon, joka sisältää graafin jokaisen kärjen siten, että reunojen painojen summa voidaan minimoida.

kuinka ladata musiikkia

Saat lisätietoja primin algoritmista napsauttamalla alla olevaa linkkiä - https://www.javatpoint.com/prim-algorithm

Kruskalin algoritmi - Tätä algoritmia käytetään myös yhdistetyn painotetun graafin minimivirittävän puun löytämiseen. Kruskalin algoritmi noudattaa myös ahneutta, joka löytää optimaalisen ratkaisun joka vaiheessa sen sijaan, että keskittyisi globaaliin optimiin.

Saat lisätietoja primin algoritmista napsauttamalla alla olevaa linkkiä - https://www.javatpoint.com/kruskal-algoritm

Eli siinä kaikki artikkelista. Toivottavasti artikkeli on hyödyllinen ja informatiivinen sinulle. Täällä olemme keskustelleet virittävästä puusta ja vähimmäisvirittävän puusta sekä niiden ominaisuuksista, esimerkeistä ja sovelluksista.