MATRISES ADYACENTES E INCIDENTE

4.2.- PRIMEROS RESULTADOS SOBRE GRAFOS

Proposición.- La suma de los grados de los vértices es igual al doble del número de aristas

Demostración

Al realizar la suma de los grados de todos los vértices, como cada arista tiene 2 extremos se cuenta exactamente 2 veces. Por tanto la suma de los grados de los vértices es igual al doble del número de aristas

Definición (matriz de adyacencia de un grafo)

Sea G un grafo de orden n. Llamaremos matriz de incidencia de G a la matriz nxn que llamaremos A = (aij) donde aij = 1 si {i,j}A y aij = 0 en otro caso.

La matriz de adyacencia siempre es simétrica porque aij = aji

Ejemplo:

Teorema.- Sea G un grafo de n vértices con n > 1 y sea A su matriz de adyacencia. Se cumple que el valor del coeficiente de la matriz es igual al número de caminos de longitud k con extremos vi y vj

Demostración

Por inducción en k

Para k = 1 es la definición de A

Supongamos que es cierto para k y vamos a verlo para k+1.

La casilla (i,j) de Ak+1 es el producto de la fila i de Ak por la columna j de A, es decir, si llamamos (a, b, c,…) a la fila i de Ak y (a’, b’, c’,…) a la columna j de A, entonces la casilla (i,j) de Ak+1 es aa’ + bb’ +……

El número de caminos de longitud k+1 de i a j que pasan en último lugar por el vértice 1 será 0 si no hay arista de 1 a j o bien coincidirá con el número de caminos de longitud k de i a 1 si existe arista de 1 a j. En resumen, como el número de caminos de i a 1 es el primer elemento de la fila i de Ak, y el primer elemento de la columna j de A vale 1 ó 0 dependiendo de si hay o no arista de 1 a j, tendremos que el número de caminos de longitud k+1 de i a j que pasan en último lugar por el vértice 1 será siempre aa’.

De manera análoga el número de caminos de longitud k+1 de i a j que pasan en último lugar por el vértice 2 será siempre bb’, y así sucesivamente.

El número total de caminos de longitud k+1 de i a j será la suma de todos los anteriores, es decir, aa’+bb’+cc’+…., es decir, el elemento (i,j) de la matriz Ak+1.

Nota.- Si existe un camino de longitud m (m  n) entre 2 vértices cualquiera, entonces existe un camino de longitud  n-1 entre esos dos vértices.

Definición.- Un grafo G se dice conexo si cada par de vértices está unido al menos por un camino.

Definición.- La relación entre vértices dada por v está relacionado con w si hay un camino que los une es de equivalencia. Las clases de equivalencia de esta relación se llaman las componentes conexas del grafo.

Nota.- Un método para comprobar si un grafo es conexo es el siguiente:

- Se halla la matriz de adyacencia y se eleva a la n-1-ésima potencia

- Se calcula la suma de las potencias de A hasta An-1

- Si todos sus elementos son  0, el grafo es conexo.

Definición.- Una arista de un grafo G se dice de separación si G es conexo pero al suprimir la arista se divide en dos componentes conexos 

	Definición.- Dados dos grafos G=(V,E) y G´=(V´,E´), se denomina isomorfismo entre G y G´ a cualquier aplicación biyectiva f:G  G’  tal que  si a, b  V, entonces {a,b}E   {f(a),f(b)}E´. 

	Es decir, es una aplicación biyectiva entre los vértices de V y los de V´ de modo que los vértices conectados siguen estándolo. En este caso, diremos que G y G´ son isomorfos.

	Si G y G’ son isomorfos son matemáticamente iguales y solo varía la apariencia, o sea, que se   mantienen las adyacencias, estructura, caminos, ciclos, nº de vértices, nº de aristas, etc.

	4.3.- GRAFOS EULERIANOS Y HAMILTONIANOS

	Grafos eulerianos

	Llamaremos camino euleriano a un camino que contiene a todas las aristas del grafo, apareciendo cada una exactamente una vez.

Un ciclo euleriano es un camino euleriano que comienza y acaba en el mismo vértice. 

	Definición.- Un grafo que admite un ciclo euleriano diremos que es un grafo euleriano.

Ejemplo: 

	1)




	2) Si un grafo es isomorfo a un solo ciclo, siempre tiene ciclo euleriano


	Proposición.- Si un grafo está formado por dos subgrafos eulerianos unidos al menos por un vértice y sin aristas en común, entonces es euleriano

	Demostración
	Empezamos por uno de los vértices en común, v. Partiendo de él podemos recorrer el primer subgrafo con un ciclo euleriano, volviendo al vértice de partida.
	Ahora recorremos el segundo subgrafo con su ciclo euleriano. La unión de estos dos ciclos vuelve a ser un ciclo que recorre todas las aristas exactamente una vez, por tanto es un ciclo euleriano de todo el grafo.

	Nota.-  Lo mismo ocurre con una unión finita en las condiciones anteriores

	Teorema.- Un grafo conexo G=(V,A) es euleriano  todo vértice tiene grado par.

	Demostración:
	““ (por inducción en |A|=m)
	El menor número posible de aristas es 3. En este caso el grafo es un triángulo que es euleriano.
	Suponemos que el teorema es cierto para grados en las mismas condiciones y con menos de m aristas. Tenemos un grafo G con todos los vértices de grado par, dado que G es conexo  v  V, gr(v) > 0. Empiezo por un vértice v cualquiera y voy recorriendo el grafo mientras pueda, con la condición de no repetir nunca arista.
	Si llego a un vértice w que no sea el del principio, puede pasar que no haya pasado antes por él o que no sea la primera vez que pase por w.
	En el primer caso, la única arista elegida es la que haya usado ahora para llegar a w
	En el segundo caso, cada vez que haya pasado antes por w habré escogido dos aristas (una para llegar y otra para salir) y, finalmente, habré escogido una más para llegar esta última vez a w.
	En cualquiera de los dos casos, he cogido un número impar de aristas en w. Como w tiene grado par, tiene que haber alguna que no haya cogido todavía. En consecuencia, puedo seguir recorriendo el grafo.
	Como el número de aristas es finito, llegará un momento en que tenga que pararme, es decir, llegará un momento en que al llegar a un vértice no pueda seguir porque ya haya elegido todas las aristas que había en ese vértice. Por lo que hemos dicho antes, en ese momento debo estar de vuelta en el vértice v y hemos construido un ciclo.
	Consideremos el subgrafo formado por el ciclo anterior que es claramente euleriano.
	Si ese subgrafo tiene todas las aristas del grafo, el grafo original coincide con el subgrafo, por lo que G es euleriano.
	En otro caso, consideremos el subgrafo formado por las aristas que no hayamos elegido. Este subgrafo tiene un número menor de aristas que G. Además, el grado de los vértices ha de seguir siendo par. En efecto, el grado de los vértices será el grado original (que era par), menos las aristas que hayamos quitado. Pero, como lo que hemos quitado es un ciclo, el número de aristas que quitamos en cada vértice es un número par (igual a dos veces el número de ocasiones en que el ciclo pase por ese vértice). En consecuencia, el grado de cada vértices es ahora par - par = par. Descomponiendo en componentes conexas, tendremos ahora una unión disjunta  de grafos que, por el principio de inducción, deben de ser eulerianos.
	Ahora bien, la unión de estos grafos es G que era conexo, así que deben tener vértices en común. Pero ya vimos que la unión de grafos eulerianos sin aristas en común y unidos por vértices es euleriano.

“” Como todas las aristas están una vez y sólo una en el ciclo, el grado de un vértice es el número de aristas del ciclo que pasan por él. Si recorremos el ciclo, cada vez que pasamos por un vértice tendremos dos aristas (una de llegada y otra de salida). Por tanto el grado de cada vértice será dos veces el número de ocasiones que pase por él el ciclo euleriano. En consecuencia el grado es par 

	Proposición.- Un grafo conexo tiene un camino abierto euleriano  tiene exactamente dos vértices de grado impar.

Demostración 

	“” Añadimos un nuevo vértice junto con dos aristas que lo unan a los dos vértices que tenían grado impar. Ahora estos vértices, al haberles añadido una arista a cada uno, tienen grado par y el nuevo vértice tiene grado 2, por tanto, todos los vértices son de grado par. Por el teorema anterior, tendremos un ciclo euleriano. Si en dicho ciclo quitamos ahora el vértice y las dos aristas que habíamos añadido, obtendremos un camino abierto que contiene exactamente una vez a cada arista de nuestro grafo original.
	“” La demostración es similar a la del teorema de Euler.


	Algoritmo de Fleury
	Si G es un grafo euleriano siempre es posible seguir la siguiente construcción de un circuito euleriano. Se empieza por un vértice arbitrario y se recorren las aristas arbitrariamente sometida a dos condiciones:

1) Se borran las aristas a medida que son atravesadas 2) Solo se recorre una arista de separación si no queda otra alternativa 

	DELGADO MENDIVL,HIGUERA FRAYRE,VILLASEÑOR HERNANDEZ

Google