En el subcampo matemático de la teoría de grafos, una estructura de niveles de un gráfico no dirigido es una partición de los vértices en subconjuntos que tienen la misma distancia desde un vértice raíz determinado. [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 Li llamados niveles, que consisten en vértices a la distancia i de r . De manera equivalente, este conjunto puede definirse estableciendo L 0 = { r }, y luego, para i > 0, definiendo Li como el conjunto de vértices que son vecinos de los vértices en L i − 1 pero que no lo son en ningún caso anterior. nivel. [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á marcada: añadir v a Q' si Q' está vacío: regresar Q ← Q'En una estructura de niveles, cada arista 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 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 planos . [5]