Niveaustructuur - Level structure

In de wiskundige deelgebied van grafentheorie een niveaustructuur een ongerichte graaf is een partitie van de hoekpunten in deelverzamelingen die dezelfde zijn afstand van een gegeven wortel hoekpunt.

Definitie en constructie

Gegeven een verbonden graaf G = ( V , E ) met V de set hoekpunten en E de set randen , en met een wortelpunt r , de niveaustructuur is een verdeling van de hoekpunten in subsets L _i genaamd niveaus, bestaande uit de hoekpunten op afstand i van r . Op equivalente wijze kan deze set worden gedefinieerd door L ₀  = { r } in te stellen, en vervolgens, voor i  > 0, L _i te definiëren als de set hoekpunten die buren zijn aan hoekpunten in L _{i  - 1,} maar zelf niet in eerdere niveau.

De niveaustructuur van een grafiek kan worden berekend door een variant van breedte-eerst zoeken :

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'

Eigendommen

In een niveaustructuur heeft elke rand van G ofwel zijn beide eindpunten binnen hetzelfde niveau, of zijn de twee eindpunten op opeenvolgende niveaus.

Toepassingen

De verdeling van een grafiek in zijn niveaustructuur kan worden gebruikt als een heuristiek voor problemen met de grafieklay-out, zoals de bandbreedte van de grafiek . Het Cuthill-McKee-algoritme is een verfijning van dit idee, gebaseerd op een extra sorteerstap binnen elk niveau.

Niveaustructuren worden ook gebruikt in algoritmen voor spaarzame matrices en voor het construeren van scheidingstekens van vlakke grafieken .

Referenties