En teoría de grafos , una rama de las matemáticas combinatorias, un gráfico de bloques o árbol de camarillas [1] es un tipo de gráfico no dirigido en el que cada componente biconectado (bloque) es una camarilla .
Los gráficos de bloques a veces se denominan erróneamente árboles Husimi (en honor a Kôdi Husimi ), [2] pero ese nombre se refiere más propiamente 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 gráficos de intersección de bloques de gráficos arbitrarios no dirigidos. [4]
Los gráficos de bloques son exactamente los gráficos para los cuales, por 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 gráfico prohibido como los gráficos que no tienen el gráfico de diamante o un ciclo de cuatro o más vértices como subgrafo inducido ; es decir, son las gráficas cordales sin diamantes. [5] También están los gráficos ptolemaicos ( gráficos cordales de distancia-hereditarios ) en los que cada dos nodos a una distancia de dos entre sí están conectados por un único camino más corto , [2] y los gráficos cordales en los que cada dos camarillas máximas tienen al menos la mayoría tiene un vértice en común. [2]
Un gráfico G es un gráfico de bloques si y sólo si la intersección de cada dos subconjuntos conectados de vértices de G está vacía o es conexa. Por lo tanto, los subconjuntos conectados de vértices en un gráfico de bloques conectado forman una geometría convexa , una propiedad que no es cierta para ningún gráfico que no sea gráfico de bloques. [6] Debido a esta propiedad, en un gráfico de bloques conectado, cada conjunto de vértices tiene un superconjunto conectado mínimo único, su cierre en la geometría convexa. Los gráficos de bloques conectados son exactamente aquellos gráficos en los que hay un camino inducido único que conecta cada par de vértices. [1]
Los gráficos de bloques son cordales , hereditarios por distancia y geodésicos . Los gráficos hereditarios de distancia son gráficos en los que cada dos caminos inducidos entre los mismos dos vértices tienen la misma longitud, un debilitamiento de la caracterización de los gráficos de bloques por tener como máximo un camino inducido entre cada dos vértices. Debido a que tanto los gráficos cordales como los gráficos hereditarios de distancia son subclases de los gráficos perfectos , los gráficos 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 existe un triángulo único cuyos bordes se encuentran en estos tres caminos más cortos. [7]
Los gráficos lineales de los á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 determinado 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 gráficos de bloques en los que cada bloque tiene un tamaño máximo de tres son un tipo especial de gráfico de cactus , un cactus triangular. El cactus triangular más grande en cualquier gráfico se puede encontrar en tiempo polinómico usando un algoritmo para el problema de paridad matroide . Dado que los gráficos de cactus triangulares son gráficos planos , el cactus triangular más grande se puede utilizar como una aproximación al subgrafo plano 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 4/9, la más conocida para el problema del subgrafo plano máximo. [9]
Si G es cualquier gráfico no dirigido, el gráfico de bloques de G , denotado B ( G ), es el gráfico de intersección de los bloques de G : B ( G ) tiene un vértice para cada componente biconectada 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 gráfico con un vértice, entonces B ( K 1 ) se define como el gráfico vacío . B ( G ) es necesariamente un gráfico de bloques: tiene un componente biconectado para cada vértice de articulación de G , y cada componente biconectado formado de esta manera debe ser una camarilla. Por el contrario, cada gráfico de bloques es el gráfico B ( G ) de algún gráfico G . [4] Si G es un árbol, entonces B ( G ) coincide con el gráfico 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]