Partición gráfica
En matemáticas, una partición de gráfico es la reducción de un gráfico a un gráfico más pequeño mediante la partición de su conjunto de nodos en grupos mutuamente excluyentes. Los bordes del gráfico original que se cruzan entre los grupos producirán bordes en el gráfico particionado. Si el número de aristas resultantes es pequeño en comparación con el gráfico original, entonces el gráfico con particiones puede ser más adecuado para el análisis y la resolución de problemas que el original. Encontrar una partición que simplifique el análisis de gráficos es un problema difícil, pero tiene aplicaciones en computación científica, diseño de circuitos VLSI y programación de tareas en computadoras multiprocesador, entre otras. [1]Recientemente, el problema de la partición de grafos ha cobrado importancia debido a su aplicación para la agrupación y detección de clicas en redes sociales, patológicas y biológicas. Para una encuesta sobre tendencias recientes en métodos y aplicaciones computacionales, ver Buluc et al. (2013) . [2] Dos ejemplos comunes de partición de gráficos son los problemas de corte mínimo y corte máximo .
Por lo general, los problemas de partición de gráficos caen dentro de la categoría de problemas NP-difíciles . Las soluciones a estos problemas generalmente se derivan utilizando heurísticas y algoritmos de aproximación. [3] Sin embargo, se puede demostrar que la partición de gráficos uniforme o un problema de partición de gráficos equilibrado es NP-completo para aproximarse dentro de cualquier factor finito. [1] Incluso para clases de gráficos especiales como árboles y cuadrículas, no existen algoritmos de aproximación razonables, [4] a menos que P=NP . Las grillas son un caso particularmente interesante ya que modelan las gráficas resultantes del Modelo de Elementos Finitos (FEM)simulaciones Cuando no solo se aproxima el número de aristas entre los componentes, sino también los tamaños de los componentes, se puede demostrar que no existen algoritmos completamente polinómicos razonables para estos gráficos. [4]
Considere un gráfico G = ( V , E ), donde V denota el conjunto de n vértices y E el conjunto de aristas. Para un problema de partición balanceada ( k , v ), el objetivo es dividir G en k componentes de tamaño máximo v · ( n / k ), mientras se minimiza la capacidad de los bordes entre componentes separados. [1] Además, dado G y un entero k > 1, dividir V en k partes (subconjuntos) V1 , V 2 , ..., V k tales que las partes son disjuntas y tienen el mismo tamaño, y se minimiza el número de aristas con extremos en diferentes partes. Dichos problemas de partición se han discutido en la literatura como aproximación bicriterio o enfoques de aumento de recursos. Una extensión común son las hipergrafías , donde una arista puede conectar más de dos vértices. Un hiperborde no se corta si todos los vértices están en una partición y, de lo contrario, se corta exactamente una vez, sin importar cuántos vértices haya en cada lado. Este uso es común en la automatización del diseño electrónico .
Para un problema específico de partición balanceada ( k , 1 + ε ), buscamos encontrar una partición de costo mínimo de G en k componentes con cada componente conteniendo un máximo de (1 + ε )·( n / k ) nodos. Comparamos el costo de este algoritmo de aproximación con el costo de un corte ( k ,1 ), donde cada uno de los k componentes debe tener el mismo tamaño de ( n / k ) nodos cada uno, siendo así un problema más restringido. Por lo tanto,
