Jatkuva puu ja vähimmäispinta

Tässä opetusohjelmassa opit pintojen ulottuvuudesta ja vähimmäispinta-alasta esimerkkien ja kuvien avulla.

Ennen kuin opimme puiden ylittämisestä, meidän on ymmärrettävä kaksi kuvaajaa: suuntaamattomat ja yhdistetyt kaaviot.

Suuntaamattoman graafin on graafinen esitys, jossa reunat eivät osoita mihinkään suuntaan (ts. Reunat ovat kaksisuuntainen).

Ohjaamaton kaavio

Kytketty kaavio on graafinen esitys, jossa on aina polku kärkipiste muita kärki.

Yhdistetty kaavio

Ylittävä puu

Jatkuva puu on ohjaamattoman yhdistetyn kaavion alikaavio, joka sisältää kaikki kaavion pisteet mahdollisimman pienellä määrällä reunoja. Jos kärki puuttuu, se ei ole ulottuva puu.

Reunoille voi olla määritetty painoja tai ei.

Kokonaisesta nkaaviosta luettavien pisteiden kattavien puiden kokonaismäärä on yhtä suuri kuin .n(n-2)

Jos meillä on n = 4, suurin mahdollinen kattavien puiden määrä on yhtä suuri kuin . Siten voidaan muodostaa 16 ulottuvaa puuta täydestä kuvaajasta, jossa on 4 kärkeä.44-2 = 16

Esimerkki kattavasta puusta

Ymmärretään kattava puu alla olevilla esimerkeillä:

Olkoon alkuperäinen kaavio:

Normaali kaavio

Jotkut mahdollisista ulottuvista puista, jotka voidaan luoda yllä olevasta kaaviosta, ovat:

Ylittävä puu Ylittävä puu Ylittävä puu Ylittävä puu Ylittävä puu Ylittävä puu

Pienin ulottuva puu

Pienin ulottuva puu on ulottuva puu, jossa reunojen painon summa on mahdollisimman pieni.

Esimerkki kattavasta puusta

Ymmärretään yllä oleva määritelmä alla olevan esimerkin avulla.

Alkuperäinen kaavio on:

Painotettu kaavio

Yllä olevan kaavion mahdolliset ulottuvat puut ovat:

Pienin kattava puu - 1 Pienin ulottuva puu - 2 Pienin ulottuva puu - 3 Pienin ulottuva puu - 4

Pienin ulottuva puu edellä olevista kattavista puista on:

Pienin ulottuva puu

Pienin kaaviosta ulottuva puu löytyy seuraavista algoritmeista:

1. Primin algoritmi
2. Kruskalin algoritmi

Spanning Tree -sovellukset

• Tietokoneverkon reititysprotokolla
• Ryhmäanalyysi
• Siviiliverkoston suunnittelu

Pienin kattava puu -sovellus

• Polkujen etsiminen kartalta
• Suunnitella verkkoja, kuten tietoliikenneverkkoja, vesihuoltoverkkoja ja sähköverkkoja.