Graafiteoriassa puu on suuntaamaton graafi, jossa mitkä tahansa kaksi kärkeä on yhdistetty täsmälleen yhdellä polulla, tai vastaavasti yhdistetty asyklinen suuntaamaton graafi. … Polymetsä (tai suunnattu metsä tai suunnattu metsä) on suunnattu asyklinen graafi, jonka pohjana suuntaamaton graafi on metsä.
Mitä ovat suunnatut ja ohjaamattomat puut?
Suuntamaton graafi, jossa ei ole jaksoja, on metsä ja jos se on yhdistetty, sitä kutsutaan puuksi. Suunnattu graafi on metsä (tai puu), jos kun kaikki reunat muunnetaan suuntaamattomiksi reunoksi, se on suuntaamaton metsä (tai puu). Juurtunut puu on puu, jonka juureksi on merkitty yksi kärki.
Miksi puut ovat ohjaamattomia?
Lause: Suuntamaton graafi on puu, jos jokaisen kärkiparin välillä on täsmälleen yksi yksinkertainen polkuTodistus: Jos meillä on graafi T, joka on puu, niin sen täytyy olla yhdistetty ilman jaksoja. Koska T on kytketty, jokaisen kärkiparin välillä on oltava vähintään yksi yksinkertainen polku.
Mitä suunnattu puu tarkoittaa?
Suunnattu puu on asyklinen suunnattu graafi Siinä on yksi solmu, jonka inaste on 1, kun taas kaikilla muilla solmuilla on inaste 1, kuten kuvassa näkyy: Solmu, jolla on ulkoastetta 0, on kutsutaan ulkoiseksi solmuksi tai terminaalisolmuksi tai lehdeksi. Solmuja, joiden ulkoaste on suurempi tai yhtä suuri kuin yksi, kutsutaan sisäiseksi solmuksi.
Mistä tunnistat, onko suuntaamaton graafi puu?
Suoritamme suuntaamattomien graafien tapauksessa kolme vaihetta:
- Suorita DFS-tarkistus mistä tahansa solmusta varmistaaksesi, että jokaisella solmulla on täsmälleen yksi vanhempi. Jos ei, palauta.
- Tarkista, että kaikissa solmuissa on käyty. Jos DFS-tarkistus ei pystynyt vierailemaan kaikissa solmuissa, palauta.
- Muuten kaavio on puu.
