Ylittävä puu

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 19.9.2021 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Graafin virittävä puu on puu , tietyn graafin aligraafi, jolla on sama määrä pisteitä kuin alkuperäinen graafi. Epävirallisesti sanottuna virittävä puu saadaan alkuperäisestä graafista poistamalla maksimimäärä jaksoihin sisältyviä reunoja, mutta rikkomatta graafin liitettävyyttä. Virittävä puu sisältää kaikki alkuperäisen graafin kärjet ja sisältää reunan. $n$ $n-1$

Määritelmä

Virittävä puu on tietyn yhdistetyn suuntaamattoman graafin asyklinen yhdistetty osagraafi , joka sisältää kaikki sen kärjet .

Hajautuvan metsän käsite on moniselitteinen; se voi tarkoittaa jotakin seuraavista alagraafista:

mikä tahansa asyklinen aligraafi, joka sisältää kaikki graafin kärjet, mutta ei välttämättä yhdistetty;
irrotetussa graafissa aligraafi, joka koostuu virittävien puiden liitosta kullekin sen yhdistetylle komponentille .

Virtapuuta kutsutaan joskus myös virittäväksi puuksi , virittäväksi puuksi tai kuvaajarungoksi . Eri kirjoittajien sanan "ostovny" painotus on osoitettu ensimmäisessä (sanasta ostov) tai toisessa tavussa.

Ominaisuudet

Mikä tahansa kärkigraafin virittävä puu sisältää täsmälleen reunan. $n$ $n-1$
Virittävien puiden lukumäärä täydellisessä graafissa pisteissä on yhtä suuri kuin tämä lause, jota kutsutaan Cayley-kaavaksi [1] : $n$ $n^{n-2};$
Virittävien puiden lukumäärä täydellisessä kaksiosaisessa graafissa on $K_{{m,n}}$ $m^{n-1}\cdot n^{m-1}.$
Yleensä virittävien puiden lukumäärä mielivaltaisessa graafissa voidaan laskea käyttämällä ns. matriisipuulausetta .
Olkoon graafissa reuna Merkitään graafilla, joka saadaan reunan eliminoinnista ja graafilla, joka saadaan reunan supistumisesta pisteeseen. Jos reuna ei ole silmukka, seuraava relaatio on tosi, jota kutsutaan poisto-plus-kutistukseksi [2] : $\rho$ $\gamma .$ $\Gamma \backslash \rho$ $\Gamma$ ${\näyttötyyli \rho ,}$ $\Gamma /\rho$ $\Gamma$ $\rho$ $\rho$ ${\näyttötyyli \gamma ,}$ $\tau (\Gamma )=\tau (\Gamma \backslash \rho )+\tau (\Gamma /\rho ),$

jossa tarkoittaa kaavion virittävien puiden lukumäärää

\tau (\Gamma )

\gamma .

Algoritmit

Virittävä puu voidaan rakentaa lähes millä tahansa graafin läpikulkualgoritmilla, kuten syvyys ensin -haku tai leveys ensin -haku . Se koostuu kaikista reunapareista siten, että algoritmi, katsoen kärkeä , löytää viereisyysluettelostaan uuden, aiemmin löytämättömän kärjen. ${\näyttötyyli (u,v),}$ $sinä,$ $v.$

Virtavilla puilla, jotka on rakennettu kuljetettaessa graafia huipusta Dijkstran algoritmin avulla, on ominaisuus, että graafin lyhin polku mihin tahansa toiseen kärkeen on (se on myös ainoa) polku tähän kärkeen rakennetussa virittävässä puussa. $s$ $s$ $s$

On myös useita rinnakkaisia ja hajautettuja virittäviä puualgoritmeja. Käytännön esimerkkinä hajautetusta algoritmista voidaan antaa STP -protokolla .

Jos graafin kullekin reunalle on määritetty paino (pituus, hinta jne.), niin optimaalisen virittävä puun löytämiseen liittyy lukuisia algoritmeja minimivirittävän puun löytämiseksi, mikä minimoi siihen sisältyvien reunojen painojen summan. .

Ongelma virittävän puun löytämisestä, jossa kunkin kärjen aste ei ylitä jotakin ennalta määrättyä vakiota , on NP-täydellinen [3] . $k,$

Virtaavan puun valintaa ja etäreunojen lukumäärän laskemista sähköpiirien kaavioissa käytetään riippumattomien piirien lukumäärän laskemiseen sähköpiirin analyysissä piirivirtojen menetelmällä [4] .

Katso myös

Muistiinpanot

↑ Martin Aigner, Günter M. Ziegler. Todistuksia kirjasta . - Springer-Verlag, 2004. - P. 173-178 . — ISBN 978-3540404606 .
↑ Petrunin A. Kuinka monta puuta on kaaviossa // Kvant . - 2018. - Nro 9 . - S. 9-13 . - doi : 10.4213/kvant20180902 . (Venäjän kieli)
↑ Michael R. Garey, David S. Johnson. Tietokoneet ja hallitsemattomuus: opas NP-täydellisyyden teoriaan . - W. H. Freeman, 1979. - S. 206 . — ISBN 0-7167-1045-5 .
↑ Bessonov L. A. Sähkötekniikan teoreettiset perusteet. Sähköpiirit. - M . : Gardariki, 2002. - 638 s. — ISBN 5-8297-0026-3 .