En teoría de grafos , una rama de las matemáticas combinatorias, un grafo de bloques o árbol de camarillas [1] es un tipo de grafo no dirigido en el que cada componente biconectado (bloque) es una camarilla .
Los gráficos de bloques a veces se denominan erróneamente árboles de Husimi (en honor a Kôdi Husimi ), [2] pero ese nombre se refiere más apropiadamente a los gráficos de cactus , gráficos en los que cada componente biconectado no trivial es un ciclo. [3]
Los gráficos de bloques pueden caracterizarse como los gráficos de intersección de los bloques de gráficos arbitrarios no dirigidos. [4]
Los gráficos de bloques son exactamente los gráficos para los cuales, para cada cuatro vértices u , v , x e y , las dos mayores de las tres distancias d ( u , v ) + d ( x , y ) , d ( u , x ) + d ( v , y ) y d ( u , y ) + d ( v , x ) son siempre iguales. [2] [5]
También tienen una caracterización de grafo prohibido como los grafos que no tienen el grafo de diamante o un ciclo de cuatro o más vértices como subgrafo inducido ; es decir, son los grafos cordales libres de diamante. [5] También son los grafos ptolemaicos ( grafos hereditarios de distancia cordal ) en los que cada dos nodos a distancia dos entre sí están conectados por un camino más corto único , [2] y los grafos cordales en los que cada dos camarillas máximas tienen como máximo un vértice en común. [2]
Un grafo G es un grafo de bloques si y solo si la intersección de cada dos subconjuntos conexos de vértices de G está vacía o conexa. Por lo tanto, los subconjuntos conexos de vértices en un grafo de bloques conexo forman una geometría convexa , una propiedad que no es cierta para ningún grafo que no sea un grafo de bloques. [6] Debido a esta propiedad, en un grafo de bloques conexo, cada conjunto de vértices tiene un superconjunto conexo mínimo único, su clausura en la geometría convexa. Los grafos de bloques conexos son exactamente los grafos en los que hay un camino inducido único que conecta cada par de vértices. [1]
Los grafos de bloques son cordales , hereditarios de distancia y geodésicos . Los grafos hereditarios de distancia son los grafos en los que cada dos caminos inducidos entre los mismos dos vértices tienen la misma longitud, lo que debilita la caracterización de los grafos de bloques como aquellos que tienen como máximo un camino inducido entre cada dos vértices. Debido a que tanto los grafos cordales como los hereditarios de distancia son subclases de los grafos perfectos , los grafos de bloques son perfectos.
Cada árbol , gráfico de conglomerados o gráfico de molino de viento es un gráfico de bloques.
Cada gráfico de bloques tiene boxicidad como máximo dos. [7]
Los gráficos de bloques son ejemplos de gráficos pseudomedianos : por cada tres vértices, existe un vértice único que pertenece a los caminos más cortos entre los tres vértices, o bien existe un triángulo único cuyos bordes se encuentran en estos tres caminos más cortos. [7]
Los gráficos lineales de árboles son exactamente los gráficos de bloques en los que cada vértice cortado incide como máximo en dos bloques, o equivalentemente, los gráficos de bloques sin garras . Los gráficos lineales de árboles se han utilizado para encontrar gráficos con un número dado de aristas y vértices en los que el subgrafo inducido más grande que es un árbol es lo más pequeño posible. [8]
Los grafos de bloques en los que cada bloque tiene un tamaño máximo de tres son un tipo especial de grafo de cactus , un cactus triangular. El cactus triangular más grande en cualquier grafo se puede encontrar en tiempo polinomial utilizando un algoritmo para el problema de paridad matroide . Dado que los grafos de cactus triangulares son grafos planares , el cactus triangular más grande se puede utilizar como una aproximación al subgrafo planar más grande, un subproblema importante en la planarización . Como algoritmo de aproximación , este método tiene una relación de aproximación de 4/9, la más conocida para el problema del subgrafo planar máximo. [9]
Si G es cualquier grafo no dirigido, el grafo de bloques de G , denotado B ( G ), es el grafo de intersección de los bloques de G : B ( G ) tiene un vértice para cada componente biconexo de G , y dos vértices de B ( G ) son adyacentes si los dos bloques correspondientes se encuentran en un vértice de articulación. Si K 1 denota el grafo con un vértice, entonces B ( K 1 ) se define como el grafo vacío . B ( G ) es necesariamente un grafo de bloques: tiene un componente biconexo para cada vértice de articulación de G , y cada componente biconexo formado de esta manera debe ser una camarilla. A la inversa, cada grafo de bloques es el grafo B ( G ) para algún grafo G . [4] Si G es un árbol, entonces B ( G ) coincide con el grafo lineal de G .
El grafo B ( B ( G )) tiene un vértice por cada vértice de articulación de G ; dos vértices son adyacentes en B ( B ( G )) si pertenecen al mismo bloque en G . [4]