Matemáticas - Teoría de grafos

 grafo sin triángulos es un grafo no dirigido en el que no existen tres vértices que formen un triángulo de aristas. Grafos sin triángulos pueden ser equivalentemente definidos como grafos con número de clique <= 2, grafos con cintura >= 4, grafos sin ciclos de tamaño 3, o grafos localmente independientes.

Por el teorema de Turán, el grafo sin triángulos de N-vértice con el máximo número de aristas es un grafo bipartito completo en el que la cantidad de vértices en cada bipartición sea lo más similar posible.

Problema de encontrar un triángulo

El problema encontrar un triángulo consiste en determinar si un grafo tiene o no triángulos. Cuando el grafo contiene un triángulo, los algoritmos a menudo devuelven como salida tres vértices que cumplen dicha condición. Es posible comprobar si un grafo con m aristas no contiene triángulos en tiempo O(m^1.41). Otro enfoque es encontrar la traza de A³, donde A es la matriz de adyacencia del grafo. La traza es cero si y sólo si el grafo no contiene triángulos. Para grafos densos, es más eficiente utilizar este sencillo algoritmo que se basa en la multiplicación de matrices, ya que tiene un una complejidad temporal de O(n^2.373), donde n es el número de vértices. Como Imrich, Klavžar y Mulder (1999) muestran, reconocer un grafo sin triángulos es equivalente en complejidad a reconocer la grafo mediano; sin embargo, los mejores algoritmos para la detección de la mediana de un grafo usan la detección de triángulos, no viceversa. El árbol de toma de decisión o la complejidad de la consulta del problema, donde las consultas son a un oráculo que almacena la matriz de adyacencia del grafo, es T(n²). Sin embargo, para los algoritmo cuánticos, la mejor cota es O(n), pero el mejor algoritmo hasta el momento, presentado por Belovs (2011) tiene cota O(n^1.29).

Número de Independencia y Teoría de Ramsey

Un conjunto independiente de vn vértices en un grafo sin triángulos de n vértices es fácil de encontrar: o bien hay un vértice con mayor que vn vecinos (en cuyo caso los vecinos son un conjunto independiente ) o todos los vértices tienen menos de vn vecinos (en cuyo caso cualquier conjunto independiente maximal debe tener al menos vn vértices).¹ Esta cota se pueden mejorar ligeramente: en cada grafo sin triángulos existe un conjunto independiente de ${\displaystyle \Omega ({\sqrt {n\log n}})}$ vértices, y en algunos grafos sin triángulos cada conjunto independiente tiene ${\displaystyle O({\sqrt {n\log n}})}$ vértices. Una forma de generar grafos sin triángulos en el que todos los conjuntos independientes son pequeños es el proceso de eliminación de triángulos ² en el que se genera un grafo sin triángulos maximal añadiendo iterativamente aristas elegidas al azar que no completen un triángulo. Con probabilidad muy alta, este proceso produce un grafo con el número de independencia ${\displaystyle O({\sqrt {n\log n}})}$. También es posible encontrar unGrafo regular con las mismas propiedades.

Estos resultados pueden interpretarse así mismo dando límites asintóticos a los números de Ramsey R(3,t) de la forma ${\displaystyle \Theta ({\tfrac {t^{2}}{\log t}})}$: si las aristas de un grafo completo con ${\displaystyle \Omega ({\tfrac {t^{2}}{\log t}})}$ vértices son coloreados de rojo o azul, entonces o bien el grafo rojo contiene un triángulo o, si no contiene triángulos, entonces debe tener un conjunto independiente de tamaño t correspondiente a un clique del mismo tamaño en el grafo azul.

Coloración de grafos sin triángulos

Mucha de la investigación sobre grafos sin triángulos ha sido sobre coloración de grafos. Cada Grafo bipartito (es decir, cada grafo 2-coloreable) no contiene triángulos, y el teorema de Grötzsch establece que todo grafo planar sin triángulos es 3-coloreable.³ Sin embargo, los grafos sin triángulos no planares pueden requerir muchos más que tres colores.

Mycielski (1955) definió una construcción, ahora llamado grafo de Mycielskian, , para la formación de un nuevo grafo sin triángulos a partir de otro grafo sin triángulos. Si un grafo tiene número cromático k, su Mycielskiano tiene número cromático k + 1, por lo que esta construcción puede ser utilizada para demostrar que una cantidad arbitraria de colores puede ser necesaria para colorear grafos sin triángulos no planares. En particular el grafo de Grötzsch, un grafo de 11 vértice formado por la aplicación repetida de la construcción de Mycielski, es un grafo sin triángulos que no es coloreable con menos de cuatro colores, y es el grafo más pequeño que cumple esta propiedad. Gimbel &Thomassen y (2000) and Nilli (2000) mostraron que el número de colores necesarios para colorear un grafo sin triángulos de m aristas es

${\displaystyle O\left({\frac {m^{1/3}}{(\log m)^{2/3}}}\right)}$

y que existen grafos sin triángulos que tienen números cromáticos proporcionales a esta cota. También se han obtenido varios resultados relativos a la coloración mínima en grafos sin triángulos. Andrásfai, Erdős y Sós (1974) demostraron que cualquier grafo sin triángulos de n vértice en el que cada vértice tiene más de 2n/5 vecinos debe ser bipartito Este es el mejor resultado posible de este tipo, ya que el ciclo de tamaño 5 requiere de tres colores, pero tiene exactamente 2n/5 vecinos por vértice. Motivado por este resultado, Erdős y Simonovits (1973) conjeturó que cualquier grafo sin triángulos de n vértices en el que cada vértice tiene al menos n/3 3 vecinos puede ser coloreado con sólo tres colores, sin embargo, Häggkvist (1981) refuta esta conjetura encontrando un contraejemplo en el que cada vértice del grafo Grötzsch se sustituye por un conjunto independiente de tamaño cuidadosamente elegido.Jin (1995) demostró que cualquier grafo sin triángulos de nvértices en el que cada vértice tiene más de 10n/29 vecinos debe ser 3-coloreable, este es el mejor resultado posible de este tipo, ya que el grafo de Häggkvist requiere cuatro colores y exactamente 10n/29 vecinos por vértice. Por último, Brandt y Thomassé (2006) demostraron que cualquier grafo sin triángulos de n vértice en el que cada vértice tiene más de n/3 vecinos debe ser 4-coloreable. Resultados adicionales de este tipo no son posibles, ya que Hajnal⁴ encontró ejemplos de grafos sin triángulos con número cromático arbitrariamente grande y grado mínimo (1/3 − e)n para cualquier e > 0.

 isomorfismo entre dos grafos G y H es una biyección f entre los conjuntos de sus vértices ${\displaystyle f:V(G)\rightarrow V(H)}$que preserva la relación de adyacencia. Es decir, cualquier par de vértices u y v de G son adyacentes si y solo si lo son sus imágenes,f(u) y f(v), en H.

A pesar de su diferente aspecto, los dos grafos que se muestran a continuación son isomorfos:

Grafo G	Grafo H	Un isomorfismo entre G y H
		${\displaystyle f(a)=1}$ ${\displaystyle f(b)=6}$ ${\displaystyle f(c)=8}$ ${\displaystyle f(d)=3}$ ${\displaystyle f(g)=5}$ ${\displaystyle f(h)=2}$ ${\displaystyle f(i)=4}$ ${\displaystyle f(j)=7}$

Dos grafos con matrices de adyacencia respectivas A y B serán isomofos si y solo si existe una matriz permutación P tal que B = P A P^t.

La determinación de si dos grafos con el mismo número de vértices n y aristas m son isomorfos o no, se conoce como el problema del isomorfismo de grafos. Este problema admite un ataque por fuerza bruta que exigiría comprobar si las n! biyecciones posibles preservan la adyacencia, pero no se conoce un algoritmo eficiente, al menos para el caso general. En este contexto, eficiencia debe interpretarse como crecimiento del número de pasos inferior a O(eⁿ).

El problema del isomorfismo de grafos presenta una curiosidad en teoría de complejidad computacional al ser uno de los pocos problemas citados por Garey y Johnson en 1979 pertenecientes a NP de los que se desconoce si es resoluble en tiempo polinómico o si es NP-completo (actualmente está en revisión la demostración de que el problema está en P).

matriz de adyacencia es una matriz cuadrada que se utiliza como una forma de representar relaciones binarias.

Construcción de la matriz a partir de un grafo

1. Se crea una matriz cero, cuyas columnas y filas representan los nodos del grafo.
2. Por cada arista que une a dos nodos, se suma 1 al valor que hay actualmente en la ubicación correspondiente de la matriz.

   Si tal arista es un bucle y el grafo es no dirigido, entonces se suma 2 en vez de 1.

Finalmente, se obtiene una matriz que representa el número de aristas (relaciones) entre cada par de nodos (elementos).

Existe una matriz de adyacencia única para cada grafo (sin considerar las permutaciones de filas o columnas), y viceversa.

Ejemplos

La siguiente tabla muestra dos grafos y su respectiva matriz de adyacencia. Note que en el primer caso, como se trata de un grafo no dirigido, la matriz obtenida essimétrica:

Grafo no dirigido	Matriz de adyacencia
	${\displaystyle \mathbf {A} ={\begin{bmatrix}0&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\end{bmatrix}}}$
Grafo dirigido	Matriz de adyacencia
	${\displaystyle \mathbf {A} ={\begin{bmatrix}0&1&0&0&1&0&0&0\\0&0&0&0&0&0&1&0\\0&0&0&0&0&0&0&0\\0&0&1&0&0&0&1&0\\0&0&0&0&0&0&0&0\\1&1&1&0&0&0&0&0\\0&0&0&0&0&0&0&0\\0&0&0&0&0&0&1&0\\\end{bmatrix}}}$

Propiedades de la matriz de adyacencia

• Para un grafo no dirigido la matriz de adyacencia es simétrica.
• El número de caminos C_i,j(k), atravesando k aristas desde el nodo i al nodo j, viene dado por un elemento de la potencia k-ésima de la matriz de adyacencia:

${\displaystyle C_{i,j}(k)=[\mathbf {A} ^{k}]_{ij}}$

Comparación con otras representaciones

Existen otras formas de representar relaciones binarias, como por ejemplo los pares ordenados o los grafos. Cada representación tiene sus virtudes y desventajas.

En particular, la matriz de adyacencia es muy utilizada en la programación, porque su naturaleza binaria y matricial calza perfecto con la de los computadores. Sin embargo, a una persona común y corriente se le hará mucho más sencillo comprender una relación descrita mediante grafos, que mediante matrices de adyacencia.

Otra representación matricial para las relaciones binarias es la matriz de incidencia.

Aplicaciones

La relación entre un grafo y el vector y valor propio de su correspondiente matriz de adyacencia se estudian en la teoría espectral de grafos.