Gráfico de bloques

Un gráfico de bloques ( árbol clique [1] ) es un tipo de gráfico no dirigido en el que cada componente biconectado (bloque) es un clique [2] .

Los gráficos de bloques se pueden describir mediante gráficos de intersección de bloques de gráficos no dirigidos arbitrarios [3] .

Descripción

Los gráficos de bloques son exactamente aquellos gráficos en los que por cada cuatro vértices , y las dos mayores de las tres distancias , son siempre [4] [5] [6] .

También se pueden describir en términos de subgráficos prohibidos , como gráficos que no contienen rombos o ciclos de cuatro o más longitudes como subgráfico generado . Es decir, son grafos cordales sin rombos [6] . También son grafos de Ptolomeo ( grafos heredados de la distancia cordal [7] ), en los que dos vértices cualesquiera a una distancia de dos están conectados por un solo camino más corto [4] , y grafos cordales, en los que dos cliques tienen como máximo uno vértice común [4] .

Un gráfico es un gráfico de bloques si y solo si la intersección de dos subconjuntos conectados de vértices de gráficos 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 , y ningún otro tipo de gráficos tiene esta propiedad [8] . Debido a esta propiedad, en un gráfico de bloques conexos, cualquier conjunto de vértices tiene un superconjunto conexo mínimo único, el cierre del conjunto en una geometría convexa. Los gráficos de bloques conectados son exactamente aquellos gráficos en los que hay un único camino generado que conecta dos pares de vértices cualesquiera [1] .

Clases de grafos relacionados

Los gráficos de bloques son cordales [9] y gráficos heredados de la distancia . Los gráficos heredados por distancia son gráficos en los que dos rutas secundarias entre dos vértices tienen la misma longitud, lo que es más débil que el requisito de que los gráficos de bloques tengan una ruta secundaria única entre dos vértices. Dado que tanto los gráficos cordales como los gráficos heredados de distancia son subclases de gráficos perfectos, los gráficos de bloques también son perfectos.

Cualquier árbol es un gráfico de bloques. Mills proporciona otro ejemplo de una clase de gráficos de bloques .

Cualquier gráfico de bloques tiene una rectangularidad que no exceda dos [10] [11] .

Los gráficos de bloques son un ejemplo de gráficos de pseudomedia  : para tres vértices cualesquiera, hay un solo vértice que se encuentra en los tres caminos más cortos entre estos tres vértices, o hay un solo triángulo cuyas aristas se encuentran en estos caminos más cortos. [diez]

Los gráficos de líneas de árboles son gráficos de bloques en los que cualquier vértice de corte incide como máximo en dos bloques o, de manera equivalente, gráficos de bloques sin garras . Los gráficos lineales de árboles se utilizan para encontrar gráficos con un número determinado de aristas y vértices, en los que se genera el subgrafo más grande, que es un árbol del tamaño más pequeño posible [12] .

Gráficos de bloques de gráficos no dirigidos

El gráfico de bloques para un gráfico dado (indicado por ) es el gráfico de intersección de los bloques del gráfico : tiene un vértice para cada componente biconectado del gráfico y dos vértices del gráfico son adyacentes si los dos bloques correspondientes comparten (tienen un común) bisagra (en términos de Harari, un punto de articulación) [13] . Si es un gráfico con un vértice, entonces, por definición, será un gráfico vacío. se sabe que es un bloque: tiene un componente biconectado para cada punto de articulación del gráfico , y cada componente biconectado formado de esta manera será una camarilla. Por el contrario, cualquier gráfico de bloques es un gráfico para algunos [3] . Si  es un árbol, entonces coincide con el gráfico lineal del gráfico .

El gráfico tiene un vértice para cada punto de articulación del gráfico . Dos vértices son adyacentes si pertenecen al mismo bloque en [3] .

Notas

  1. ↑ 1 2 Kristina Vuškovic. Gráficos sin agujeros pares: una encuesta // Análisis aplicable y matemáticas discretas. - 2010. - T. 4 , núm. 2 . — S. 219–240 . -doi : 10.2298 / AADM100812027V .
  2. ↑ Los gráficos de bloques a veces se denominan erróneamente árboles de Husimi, en honor al físico japonés Cody Husimi ), pero Husimi consideraba Cactus (teoría de gráficos)  : gráficos en los que cualquier componente doblemente conectado es un ciclo.
  3. ↑ 1 2 3 Frank Harary. Una caracterización de gráficos de bloques // Canadian Mathematical Bulletin. - 1963. - T. 6 , núm. 1 . — P. 1–6 . -doi : 10.4153 / cmb-1963-001-x .
  4. ↑ 1 2 3 Edward Howorka. Sobre las propiedades métricas de ciertos gráficos de camarilla // Journal of Combinatorial Theory, Serie B. - 1979. - Vol. 27 , no. 1 . — S. 67–74 . - doi : 10.1016/0095-8956(79)90069-8 .
  5. ↑ Brandstädt, Le, Spinrad, 2005 ; página 151, Teorema 10.2.6
  6. ↑ 1 2 Hans-Jürgen Bandelt, Henry Martyn Mulder. Gráficos hereditarios de distancia // Journal of Combinatorial Theory, Serie B. - 1986. - V. 41 , no. 2 . — S. 182–208 . - doi : 10.1016/0095-8956(86)90043-2 .
  7. ↑ Brandstädt, Le, Spinrad, 2005 ; página 130, Corolario 8.4.2
  8. ↑ Paul H. Edelman, Robert E. Jamison. La teoría de las geometrías convexas // Geometriae Dedicata. - 1985. - T. 19 , núm. 3 . — S. 247–270 . -doi : 10.1007/ BF00149365 .
  9. ↑ Existe la siguiente jerarquía de clases de grafos: Ptolomeo bloque estrictamente cordal cordal Brandstadt, Le, Spinrad, 2005 págs. 126, Capítulo 8.2 Otros tipos de aciclicidad; Hipergrafías de camarilla y vecindario.
  10. ↑ 1 2 Block Graphs Archivado el 21 de noviembre de 2019 en Wayback Machine , Graph Class Hierarchy Information System
  11. ↑ Brandstädt, Le, Spinrad, 2005 p. 54, Capítulo 4.5 Boxicidad, dimensión de intersección y producto escalar
  12. ↑ Paul Erdős, Michael Saks, Vera T. Sos. Árboles máximos inducidos en grafos // Journal of Combinatorial Theory, Serie B. - 1986. - V. 41 , no. 1 . — págs. 61–79 . - doi : 10.1016/0095-8956(86)90028-6 .
  13. ↑ F. Harari. Teoría de grafos. - Moscú: URSS, 2003. - ISBN 5-354-00301. Capítulo 3. Bloques, págs. 41-46

Literatura