En la teoría de grafos , una rama de las matemáticas combinatorias, un gráfico de bloques o un árbol de clique [1] es un tipo de gráfico no dirigido en el que cada componente biconectado (bloque) es un clique .
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 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 se pueden caracterizar como los gráficos de intersección de los bloques de gráficos arbitrarios no dirigidos. [4]
Caracterización
Bloque gráficos son exactamente los gráficos para las que, por cada cuatro vértices u , v , x , y y , el más grande de dos de las tres distancias delta ( 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 gráfica prohibida 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 los gráficos cordales sin diamantes. [5] También son los gráficos ptolemaicos ( gráficos hereditarios de distancia cordal ) en los que cada dos nodos a una distancia de dos entre sí están conectados por una ruta más corta única , [2] y los gráficos cordales en los que cada dos camarillas máximas tienen en la mayoría de un vértice en común. [2]
Un gráfico G es un gráfico de bloques si y solo si la intersección de cada dos subconjuntos conectados de vértices de G está vacía o conectada. Por lo tanto, los subconjuntos conectados de vértices en un gráfico de bloques conectados forman una geometría convexa , una propiedad que no es cierta para ningún gráfico que no sea un gráfico de bloques. [6] Debido a esta propiedad, en un gráfico de bloques conectados, 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 los gráficos en los que hay una ruta inducida única que conecta cada par de vértices. [1]
Clases de grafos relacionados
Los gráficos de bloques son cordales , hereditarios a distancia y geodésicos . Los gráficos de distancia-hereditarios son los 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 una boxicidad como máximo dos. [7]
Las gráficas de bloque son ejemplos de gráficas pseudomedianas : por cada tres vértices, existe un vértice único que pertenece a las rutas más cortas entre los tres vértices, o existe un triángulo único cuyas aristas se encuentran en estas tres rutas más cortas. [7]
Los gráficos de líneas de los árboles son exactamente los gráficos de bloques en los que cada vértice de corte incide como máximo en dos bloques, o de forma equivalente, los gráficos de bloques sin garras . Los gráficos de líneas 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 polinomial 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 subgráfico 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 de 4/9, la más conocida para el problema del subgráfico plano máximo. [9]
Bloquear gráficos de gráficos no dirigidos
Si G es un 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 biconectado 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 bloque es el gráfico B ( G ) para algunos gráfica G . [4] Si G es un árbol, entonces B ( G ) coincide con el gráfico de líneas de G .
El gráfico 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]
Referencias
- ^ a b Vušković, Kristina (2010), "Gráficos sin agujeros pares: una encuesta" (PDF) , Análisis aplicable y matemáticas discretas , 4 (2): 219-240, doi : 10.2298 / AADM100812027V.
- ^ a b c d Howorka, Edward (1979), "Sobre las propiedades métricas de ciertos gráficos de clique", Journal of Combinatorial Theory, Serie B , 27 (1): 67-74, doi : 10.1016 / 0095-8956 (79) 90069-8.
- ^ Ver, por ejemplo, MR0659742 , una revisión de 1983 de Robert E. Jamison de otro artículo que se refiere a los gráficos de bloques como árboles Husimi; Jamison atribuye el error a un error en un libro de Mehdi Behzad y Gary Chartrand .
- ^ a b c Harary, Frank (1963), "A characterization of block-graphs", Canadian Mathematical Bulletin , 6 (1): 1–6, doi : 10.4153 / cmb-1963-001-x , hdl : 10338.dmlcz / 101399.
- ^ a b Bandelt, Hans-Jürgen; Mulder, Henry Martyn (1986), "Gráficos hereditarios a distancia", Journal of Combinatorial Theory, Serie B , 41 (2): 182-208, doi : 10.1016 / 0095-8956 (86) 90043-2.
- ^ Edelman, Paul H .; Jamison, Robert E. (1985), "La teoría de las geometrías convexas", Geometriae Dedicata , 19 (3): 247-270, doi : 10.1007 / BF00149365 , S2CID 123491343.
- ^ a b Bloques de gráficos , sistema de información sobre inclusiones de clases de gráficos.
- ^ Erdős, Paul ; Saks, Michael ; Sós, Vera T. (1986), "Árboles inducidos máximos en gráficos" (PDF) , Journal of Combinatorial Theory, Serie B , 41 (1): 61-79, doi : 10.1016 / 0095-8956 (86) 90028-6.
- ^ Călinescu, Gruia; Fernandes, Cristina G; Finkler, Ulrich; Karloff, Howard (2002), "A Better Approximation Algorithm for Finding Planar Subgraphs", Journal of Algorithms , 2, 27 (2): 269-302, doi : 10.1006 / jagm.1997.0920 , S2CID 8329680