En el subcampo matemático de la teoría de grafos, una estructura de niveles de un grafo con raíz es una partición de los vértices en subconjuntos que tienen la misma distancia desde un vértice raíz dado. [1]
Dado un grafo conexo G = ( V , E ) con V el conjunto de vértices y E el conjunto de aristas , y con un vértice raíz r , la estructura de niveles es una partición de los vértices en subconjuntos L i llamados niveles, que consisten en los vértices a una distancia i de r . De manera equivalente, este conjunto puede definirse estableciendo L 0 = { r }, y luego, para i > 0, definiendo L i como el conjunto de vértices que son vecinos de los vértices en L i − 1 pero que no están en ningún nivel anterior. [1]
La estructura de niveles de un gráfico se puede calcular mediante una variante de búsqueda en amplitud : [2] : 176
nivel de algoritmo -BFS(G, r): Q ← {r} para ℓ de 0 a ∞: proceso(Q, ℓ) // el conjunto Q contiene todos los vértices en el nivel ℓ Marcar todos los vértices en Q como descubiertos Q' ← {} para u en Q: para cada arista (u, v): si v aún no está marcado: añadir v a Q' Si Q' está vacío: retorna Q ← Q'En una estructura de niveles, cada borde de G tiene ambos puntos finales dentro del mismo nivel, o sus dos puntos finales están en niveles consecutivos. [1]
La partición de un gráfico en su estructura de niveles se puede utilizar como una heurística para problemas de diseño de gráficos, como el ancho de banda del gráfico . [1] El algoritmo Cuthill-McKee es un refinamiento de esta idea, basado en un paso de clasificación adicional dentro de cada nivel. [3]
Las estructuras de niveles también se utilizan en algoritmos para matrices dispersas , [4] y para construir separadores de gráficos planares . [5]