Estrutura de nível - Level structure

No subcampo matemático da teoria dos grafos, uma estrutura de nível de um grafo não direcionado é uma partição dos vértices em subconjuntos que têm a mesma distância de um determinado vértice raiz.

Definição e construção

Dado um grafo conectado G = ( V , E ) com V o conjunto de vértices e E o conjunto de arestas , e com um vértice raiz r , a estrutura de nível é uma partição dos vértices em subconjuntos L _i chamados níveis, consistindo nos vértices à distância i de r . Equivalentemente, este conjunto pode ser definido configurando L ₀  = { r }, e então, para i  > 0, definindo L _i como o conjunto de vértices que são vizinhos dos vértices em L _{i  - 1,} mas não são eles próprios em nenhum anterior nível.

A estrutura de nível de um gráfico pode ser calculada por uma variante da pesquisa em amplitude :

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'

Propriedades

Em uma estrutura de nível, cada aresta de G tem seus dois pontos de extremidade dentro do mesmo nível ou seus dois pontos de extremidade estão em níveis consecutivos.

Formulários

A partição de um gráfico em sua estrutura de nível pode ser usada como heurística para problemas de layout de gráfico, como largura de banda de gráfico . O algoritmo Cuthill-McKee é um refinamento dessa ideia, com base em uma etapa de classificação adicional dentro de cada nível.

Estruturas de nível também são usadas em algoritmos para matrizes esparsas e para construir separadores de gráficos planares .

Referências