TEORÍA DE TÉRMINOS DE GRAFOS

De Wikipedia, la enciclopedia libre

Saltar a navegaciónSaltar a búsqueda

Graficar familias definidas por sus automorfismos
transitiva a distancia	→	distancia regular	←	fuertemente regular
↓
simétrico (arco transitivo)	←	t -transitivo, t  ≥ 2		sesgada simétrica
↓
(si está conectado) vértice y borde transitivo	→	borde transitivo y regular	→	borde transitivo
↓		↓		↓
vértice transitivo	→	regular	→	(si es bipartito) birregular
↑
Gráfico de Cayley	←	simétrico cero		asimétrico

En matemática teórica de grafos , un gráfico birregular ^[1] o un gráfico bipartito semirregular ^[2] es un gráfico bipartito $${\ displaystyle G = (U, V, E)}para el cual cada dos vértices en el mismo lado de la bipartición dada tienen el mismo grado entre sí. Si el grado de los vértices en$${\ displaystyle U} es $${\ displaystyle x} y el grado de los vértices en $${\ displaystyle V} es $${\ displaystyle y}, entonces se dice que el gráfico es $${\ displaystyle (x, y)}-birregular.

Cada gráfico bipartito completo $${\ displaystyle K_ {a, b}} es $${\ displaystyle (b, a)}-birregular. ^[3] El dodecaedro rómbico es otro ejemplo; es (3,4) -birregular. ^[4]

Conteo de vértices [ editar ]

Un $${\ displaystyle (x, y)}-grafico birregular $${\ displaystyle G = (U, V, E)} debe satisfacer la ecuación $${\ displaystyle x | U | = y | V |}. Esto se deduce de un argumento simple de doble conteo : el número de puntos finales de bordes en$${\ displaystyle U} es $${\ displaystyle x | U |}, el número de puntos finales de bordes en $${\ displaystyle V} es $${\ displaystyle y | V |}, y cada borde aporta la misma cantidad (uno) a ambos números.

Simetría [ editar ]

Cada gráfico bipartito regular también es birregular. Cada gráfico transitivo de borde (no permitir gráficos con vértices aislados ) que no sea también transitivo de vértice debe ser birregular. ^[3] En particular, cada gráfico transitivo de borde es regular o birregular.

Configuraciones [ editar ]

Los gráficos de Levi de configuraciones geométricas son birregulares; un gráfico birregular es el gráfico de Levi de una configuración (abstracta) si y solo si su circunferencia es al menos seis.

De Wikipedia, la enciclopedia libre

Saltar a navegaciónSaltar a búsqueda

No debe confundirse con el diagrama de bloques o el gráfico de barras .

Un gráfico de bloque

En la teoría de grafos , una rama de la matemática combinatoria, un gráfico de bloques o árbol de camarillas ^[1] es un tipo de gráfico no dirigido en el que cada componente biconnectado (bloque) es una camarilla .

Los gráficos de bloques a veces se llaman erróneamente árboles Husimi (después de Kôdi Husimi ), ^[2] pero ese nombre se refiere más adecuadamente 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.

Caracterización [ editar ]

Los gráficos de bloque son exactamente los gráficos para los cuales, por cada cuatro vértices u , v , x e y , las dos distancias más grandes d ( u , v ) +  d ( x , y ), d ( u , x ) +  d ( v , y ) yd ( u , y ) +  d ( v , x ) son siempre iguales. ^[2] [5]

También tienen una caracterización de gráfico prohibida como los gráficos que no tienen el gráfico de diamante o un ciclo de cuatro o más vértices como un 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 están conectados por un camino más corto único , ^[2] y los gráficos cordales en los que cada dos camarillas máximas tienen La mayoría de un vértice en común. ^[2]

Un gráfico G es un gráfico de bloque si y sólo si la intersección de cada dos conectados subconjuntos de vértices de G está vacío o conectado. Por lo tanto, los subconjuntos de vértices conectados en un gráfico de bloques conectados forman una geometría convexa , una propiedad que no es cierta para los gráficos que no son gráficos de bloques. ^[6] Debido a esta propiedad, en un gráfico de bloques conectados, cada conjunto de vértices tiene un superconjunto mínimo conectado ú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 gráficas relacionadas [ editar ]

Los gráficos de bloques son cordales y de distancia hereditaria . Los gráficos hereditarios de distancia son los gráficos en los que cada dos rutas inducidas entre los mismos dos vértices tienen la misma longitud, lo que debilita la caracterización de las gráficas de bloques que tienen como máximo una ruta inducida 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 grupo o gráfico de molino de viento es un gráfico de bloque.

Cada gráfico de bloque 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 de líneas de los árboles son exactamente los gráficos de bloques en los que cada vértice de corte incide en, como máximo, dos bloques, o de manera equivalente, los gráficos de bloques sin garras . Se han usado gráficos lineales de árboles para encontrar gráficos con un número dado de aristas y vértices en los que la subgrafía inducida más grande que es un árbol es lo más pequeña 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 usar 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 por el problema de subgrafía plana máxima. ^[9]

Gráficos de bloques de gráficos no dirigidos [ editar ]

Si G es cualquier gráfico no dirigido, el gráfico de bloque 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 biconnectado 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 ₁ denota el gráfico con un vértice, entonces B ( K ₁ ) se define como el gráfico vacío . B ( G) es necesariamente un gráfico de bloques: tiene un componente biconnectado para cada vértice de articulación de G , y cada componente biconnectado 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 para cada vértice de articulación de G ; dos vértices son adyacentes en B ( B ( G )) si pertenecen al mismo bloque en G .

No debe confundirse con la incrustación de libros .

Un libro triangular

En teoría de grafos , un gráfico de libro (a menudo escrito$${\ displaystyle B_ {p}} ) puede ser cualquiera de varios tipos de gráficos formados por múltiples ciclos que comparten una arista.

Variaciones [ editar ]

Un tipo, que puede llamarse un libro cuadrilátero , consiste en p cuadriláteros que comparten un borde común (conocido como "columna vertebral" o "base" del libro). Es decir, es un producto cartesiano de una estrella y un solo filo. ^[1] [2] El gráfico de libro de 7 páginas de este tipo proporciona un ejemplo de un gráfico sin etiquetado armonioso . ^[2]

Un segundo tipo, que podría llamarse un libro triangular , es el gráfico tripartito completo K _1,1, p . Es un gráfico que consta de$${\ displaystyle p} triángulos que comparten un borde común. ^[3] Un libro de este tipo es un gráfico dividido . Este gráfico también se ha denominado$${\ displaystyle K_ {e} (2, p)}. ^{[4] Los} libros triangulares forman uno de los bloques de construcción clave de los gráficos de líneas perfectas . ^[5]

El término "libro-gráfico" se ha empleado para otros usos. Barioli ^{[6] lo} usó para referirse a un gráfico compuesto por un número de subgrafías arbitrarias que tienen dos vértices en común. (Barioli no escribió$${\ displaystyle B_ {p}} por su libro-gráfico.)

Dentro de gráficos más grandes [ editar ]

Dado un gráfico $${\ displaystyle G}, uno puede escribir $${\ displaystyle bk (G)} para el libro más grande (del tipo considerado) contenido dentro de $${\ displaystyle G}.

Teoremas sobre libros [ editar ]

Denote el número de Ramsey de dos libros triangulares por$${\ displaystyle r (B_ {p}, \ B_ {q}).} Este es el número más pequeño. $${\ displaystyle r} tal que por cada $${\ displaystyle r}gráfico de vértices, o bien el gráfico contiene $${\ displaystyle B_ {p}}como un subgrafo, o su gráfico complementario contiene$${\ displaystyle B_ {q}} como un subgrafo.

• Si $${\ displaystyle 1 \ leq p \ leq q}, luego $${\ displaystyle r (B_ {p}, \ B_ {q}) = 2q + 3}. ^[7]
• Existe una constante $${\ displaystyle c = o (1)} tal que $${\ displaystyle r (B_ {p}, \ B_ {q}) = 2q + 3} cuando $${\ displaystyle q \ geq cp}.
• Si $${\ displaystyle p \ leq q / 6 + o (q)}y $${\ displaystyle q}es grande, el número de Ramsey está dado por$${\ displaystyle 2q + 3}.
• Dejar $${\ displaystyle C} ser una constante, y $${\ displaystyle k = Cn}. Entonces cada gráfico en$${\ displaystyle n} vértices y $${\ displaystyle m} bordes contiene un (triangular) $${\ displaystyle B_ {k}}.