Tasorakenne - Level structure

Kun matemaattinen alikentän graafiteoria tason rakenne , joka suuntaamattoman graafin on osio , että pisteiden alaryhmiin, joilla on sama etäisyys tietystä juuri kärki.

Määritelmä ja rakenne

Annetaan liitetty kaavio G = ( V , E ), jossa V joukko pisteiden ja E joukko reunat , ja jossa on juuri piste r , taso rakenne on osio pisteiden alaryhmiin L _i kutsutaan tasoa, joka koostuu kärjet i: n etäisyydellä r: stä . Vastaavasti tämä joukko voidaan määritellä asettamalla L ₀  = { r } ja määrittelemällä sitten i  > 0: lle L _i olevan joukko pisteitä, jotka ovat naapureita pisteille L _{i  - 1,} mutta eivät itse ole missään aikaisemmassa taso.

Kaavion tasorakenne voidaan laskea leveyden ensimmäisen haun muunnoksella :

algorithm level-BFS(G, r):
    Q ← {r}
    for ℓ from 0 to ∞:
        process(Q, ℓ)  // the set Q holds all vertices at level ℓ
        mark all vertices in Q as discovered
        Q' ← {}
        for u in Q:
            for each edge (u, v):
                if v is not yet marked:
                    add v to Q'
        if Q' is empty:
            return
        Q ← Q'

Ominaisuudet

Tasorakenteessa G: n kullakin reunalla on joko molemmat päätepisteet samalla tasolla tai sen kaksi päätepistettä ovat peräkkäisillä tasoilla.

Sovellukset

Kaavion osiota sen tasorakenteeseen voidaan käyttää heuristina kaavion asetteluongelmille, kuten kaavion kaistanleveys . Cuthill-McKee algoritmi on paranneltu tämän ajatuksen perusteella ylimääräinen lajittelu- vaihe kunkin tason.

Tasorakenteita käytetään myös harvojen matriisien algoritmeissa ja tasomaisista kuvaajista erotinten rakentamiseksi .

Viitteet