Buenas, hoy en clase de prácticas con MaGraDa hemos hecho actividades y tambén hemos visto un un poco más el método de Warshall para hallar la matriz de accesibilidad a partir de la matriz de adyacencia.

Esta será por tanto la última entrada que haga en el blog de matemáticas, ha sido un placer

Sesión correspondiente al día (21/12/2010).

Grafo ponderado

Definición y ejemplos

1- Un grafo simple G = (V, A) (grafo simple dirigido, respectivamente) diremos que es un grafo ponderado si tiene asociado una función W: A -> R llamada función de ponderación.

La imagen de cada arista (arco, respectivamente) determinada por los vértices v_i y v_j la llamaremos peso de la arista (arco) y lo denotaremos por w_ij.

2- Sea G = (V, A) un grafo ponderado finito tal que V = {v1, …, vn}. Llamaremos matriz de peso del grafo G a la siguiente matriz de orden n x n

3- En un grafo ponderado llamamos peso de un camino a la suma de los pesos de las aristas (arcos respectivamente) que lo forman.

4- En un grafo ponderado llamamos camino más corto entre dos vértices dados al camino de peso mínimo entre dichos vértices.

5- En un grafo ponderado llamaremos camino más largo o camino crítico entre dos vértices al camino de peso máximo entre dichos vértices.

Como siempre la teoría está muy bien para quien la entienda, aquí va un ejemplo que espero que os ayude más:

EJEMPLO

Caminos  más cortos

Supondremos  que los pesos asociados a los arcos son todos no negativos y que el grafo es dirigido. Supondremos además que los vértices del grafo están numeradores de 1 a n, de forma que w_ij representa el peso del arco (i, j) y que el vértice 1 es el origen del camino. Además u_j denotará el peso del camino más corto de 1 a j.

Dicho de otra forma, vamos a suponer que el peso es siempre positivo y que el grafo es dirigido, además numeraremos los vértices del grafo de 1 a n.

Además debemos saber que cada sección a su vez es el camino más corto que se puede considerar. Esto viene demostrado por el siguiente teorema.

Teorema

Sea 1, …., k, …..,j un camino más corto entre los vértices 1 y j de un grafo ponderado G. Entonces las secciones de este camino 1, …., k y k, …., j son los caminos más cortos entre los vértices respectivos.

Tenemos pues que si tenemos un camino de 1 a 3 pasando por 2, podemos considerar que el camino de 1 a 2 y el camino de 2 a 3 son los caminos más cortos también de las respectivas secciones.

Corolario

Supongamos que en un grafo ponderado tenemos un camino más corto entre los vértices 1 y j. Sea k el vértice inmediatamente anterior a j en ese camino. Entonces la sección de este camino desde 1 a k es el camino más corto entre estos dos vértices. Además se cumple que:

u_j = u_k + w_kj

Con esto y las ecuaciones de Bellman podemos calcular el camino más corto:

Ecuaciones de Bellman

Grafos acíclicos. Método del camino crítico o camino más largo

Un grafo dirigido no tiene circuitos si y sólo si existe una numeración de los vértices para la que se cumple que si (i, j) es un arco del grafo entonces i < j.
Con esta numeración, las ecuaciones de Bellman pueden ser reemplazadas por:

Algoritmo de numeración

Antes de lanzarnos a realizar un problema debemos aprender a numerar los vértices ya que como puse más arriba, es una condición necesaria. Para ordenarlos podemos seguir el siguiente algoritmo de ordenación:

Etapa 1. Inicializar i<-i, V⁽¹⁾= V

Etapa 2. Tomar v E V⁽ⁱ⁾ tal que de(v)=0 en G[Vi].

Etapa 3. Numerar el vértice V como vértice 2

-Hacer V⁽ⁱ⁺¹⁾ = V⁽¹⁾ – {V}

-Hacer i<-i+1

Etapa 4. Si V⁽ⁱ⁾ = ø

Algoritmo de Pert

También es interesante comentar la utilizadad del algoritmo de Pert:

Se denomina camino más largo entre dos vértices dados, al camino de peso máximo entre dichos vértices. Un ejemplo típico de obtención de un camino más largo en un grafo dirigido, es la secuenciación de actividades, también llamada red de actividades.
Así por ejemplo, un proyecto de construcción grande se suele dividir en varias actividades menores; estas actividades están relacionadas, en el sentido de que algunas no pueden comenzar hasta que otras hayan finalizado. Por ejemplo, para la construcción de una casa son necesarios cimientos, muros, carpintería, tejados, instalación eléctrica, … Una actividad como la instalación eléctrica, no puede empezar hasta haber completado otras actividades. La realización de este tipo de proyectos hace necesaria una planificación racional de las actividades a realizar que se denomina PERT (Program Evaluation and Review Technique). Para planificar un proyecto de esta clase podemos representar cada actividad de las que se compone el proyecto por un vértice. En este caso el peso lo tomamos como el tiempo necesario para realizar una actividad, por ello vamos a hacer las actividades que más tiempo requieran y así que puedan hacerse también las que requieran menor tiempo, si lo hacemos al contrario las actividades que requieran más tiempo no podrían realizarse por completo.

Hoy hemos visto los cálculos básicos que se pueden realizar con MaGraDa. Dichos cálculos son:

• Grado: nos diŕa el grado del vértice que toquemos si nos encontramos en el modo gráfico o nos mostrará una gráfica con los grados de cada uno de los vértices si nos encontramos en el modo texto.
• Ver (aristas o arcos): para el modo texto, ya que no se ven ni aristas ni arcos, tenemos esta opción, que nos mostrará una pantalla donde pondrá las aristas (arcos) que van de un vértice a otro.
• Grafo (simple, cíclico, completo y conexo): tanto en modo texto como en modo gráfico podemos comprobar si un grafo es simple, cíclico, completo y conexo. En cualquiera de las opciones anteriores, nos indicará si lo es o no con una explicación.
• Grafo no dirigido asociado: esta opción, si estamos con un grafo dirigido nos creará un grafo con las mismas propiedades pero no dirigido, es decir, se cambian arcos por aristas.

Sesión correspondiente al día (14/12/2010).

CÁLCULO DE COMPONENTES CONEXAS

Diremos que una componente conexa (CC( asociada a un vértice vi es:

Conjunto de vértices a los que alcanza vi:

R(vi)

Y que alcanza a vi:

Q(vi)

CC asociada a vi: R(vi) ∩ Q(vi)

Una componente conexa asociada a un vértice “v” es un conjunto de vértices alcanzables por”v” y que a su vez pueden alcanzar a “v”.

Hay dos procedimientos o métodos para calcular las componentes conexas de un grafo:

Método 1 – Procedimiento del algoritmo

Sea G=(V, A) un grafo dirigido:

Etapa 1. Inicializar i<-1, V⁽¹⁾ = V

Etapa 2. Tomar vi E V⁽ⁱ⁾

Etapa 3. Calcular R(i) ∩ Q(vi)

-Hacer V⁽ⁱ⁺¹⁾ = V⁽ⁱ⁾ ≈ R(vi) ∩ Q(vi)

-Hacer i<-i+1

Etapa 4. Si V⁽ⁱ⁾ = ø entonces STOP

En otro caso, volvemos a la Etapa 2.

EJEMPLO

Vamos a calcular las componentes conexas del siguiente grafo, para ello necesitamos la matriz de accesibilidad y la matriz de acceso que es la traspuesta de la de accesibilidad:

Ahora sigamos el algoritmo paso a paso:

Debemos hacer dos conjuntos, R y Q.

Inicialmente  cogemos todo el conjunto de vértices que tenemos y de ahí cogemos un vértice.

Una vez hecho vamos a la matriz de accesibilidad y buscamos la fila del vértice elegido, entonces vemos columna a columna si hay un uno o un cero, si hay un uno añadimos el vértice al conjunto R. Una vez hecho debemos hacer lo mismo para el conjunto Q pero mirando en la matriz de acceso.

Hacemos i<-1, V⁽¹⁾ = V = {V1, V2, V3, V4, V5}

Tomamos un vértice de V⁽¹⁾ , Por ejemplo V2.

Primera componente conexa: R(V2) ∩ Q(V2)

R(V2) ∩ Q(V2) = {V2, V4} ∩ {V1, V2, V3, V4, V5} = {V2, V4}

V⁽²⁾ = V⁽¹⁾ ≈ R(V2) ∩ Q(V2) = {V1, V3, V5} es decir, restamos a V⁽ⁱ⁾ lo que obtenemos de realizar la intersección entre R(V2) y Q(V2).

Tomamos lo que obtenemos que hemos denominado V⁽²⁾ y elegimos un vértice de dicho conjunto, una vez hecho repetimos el procedimiento que expliqué al principio.

Tomamos un vértice de V⁽²⁾ , por ejemplo, V1.

Segunda componente conexa: R(V1) ∩ Q(V1).

R(V1) ∩ Q(v1) = {V1, V2, V3, V4, V5} ∩ {V1, V3, V5} = {V1, V3, V5}

V⁽³⁾ = V⁽²⁾ ≈ R(V1) ∩ Q(V1) = ø

Hemos obtenido el conjunto vacío, lo que nos indica que hemos terminado, por lo tanto las componentes conexas son las V⁽ⁱ⁾ que hemos obtenido:

{V2, V4}, {V1, V3, V5}

Gráficamente quedaría de la siguiente forma:

Método 2 – Multiplicación de matrices

Este método es fácil de realizar si sabemos multiplicar matrices.

El procedimiento es el siguiente:

-Hayamos la matriz de accesibilidad y la matriz de acceso.

-Multiplicamos ambas matrices término a término, es decir, R1,1 x Q1,1; R1,2 x Q1,2; etc…Esto nos dará la matriz RxQ.

Dentro de la matriz tendremos tantas filas como vértices y tendremos que ir fila a fila y columna a columna viendo si aparece un uno o un cero, si aparece un uno entonces ese vértice de la columna forma parte de una componente conexa. Es posible que aparezcan filas repetidas, esto se debe a que no tenemos por qué tener el mismo número de componentes conexas que de vértices, las filas que se repiten hacen alusión a la misma componente conexa.

RECORRIDO DE ARISTAS

Es interesante averiguar si es posible recorrer un grafo pasando por cada arista una sola vez ya que en grafos complejos no es tan fácil de ver.

Para introducir los siguientes conceptos voy a contar una historia que puso las bases de los grafos.

“Problema de los puentes de Königsberg”: Königsberg era una ciudad que estaba separada en 4 partes y conectadas dichas partes unas con otras por 7 puentes. Pero surgió una pregunta, ¿es posible salir de un punto de la ciudad y, pasando por todos los puentes una única vez, volver al mismo punto?.

Leonhard Euler lo resolvió introduciendo el concepto de grafo euleriano.

Sea G un grafo conexo y en general no simple:

1 – Llamaremos tour de G a una cadena cerrada que atraviesa cada arista de G al menos una vez.

2 – Llamaremos tour euleriano de G a un tour de G que atraviesa cada arista exactamente una vez.

3 – Llamaremos grafo euleriano a aquel en el que podemos encontrar un tour euleriano.

4 – Llamaremos camino euleriano a una cadena (simple) que atraviesa cada arista exactamente una vez.

Para ver si un grafo tiene un tour euleriano (y por lo tanto es un grafo euleriano) o si tiene un camino euleriano tenemos varios argumentos con los que descartar el tour euleriano, el camino euleriano o ambos:

-Para que el grafo pueda tener un tour euleriano, no debe tener vértices de grado impar.

-Para que el grafo pueda tener un camino euleriano, debe tener exactamente dos vértices de grado impar.

La forma de calcular un tour euleriano y un camino euleriano viene dado por el algoritmo de Fleury.

ALGORITMO DE FLEURY

Grafo no dirigido

Para calcular un tour euleriano en un grafo no dirigido partimos de vi y terminamos en vi. Vamos a ir construyendo una cadena simple de forma que no se repitan aristas y que no se elijan aristas de corte a no ser que no haya otra alternativa, estas aristas de corte son aquellas que al quitarlas, dejan vértices aislados. Cada arista que vamos eligiendo y eliminando la añadimos al tour euleriano. Terminaremos cuando hayamos llegado desde vi a vj y no queden aristas.

Para calcular un camino euleriano partimos de un vértice vi de grado impar y llegamos al otro vértice de grado impar. El proceso que seguimos de un vértice al otro es el mismo que para el tour euleriano.

Modificación para grafos dirigidos

El proceso es el mismo, para calcular el tour euleriano debemos tener cuidado y al eliminar arcos no debemos elegir un arco que al eliminarlo aumente el número de componentes conexas del grafo no dirigido asociado, a no ser que no tengamos otra alternativa.

Para calcular el camino euleriano debemos empezar por un vértice de grado impar y terminar en el otro vértice de grado impar, de la misma forma que hacíamos en el grafo no dirigido, para ver si un vértice de un grado dirigido tiene grado impar se puede hacer comprobar que:

de(p) = ds(p)-1,  de(q) = ds(q)+1

Siendo p y q los vértices inicial y final respectivamente del camino.

EJEMPLO

Teniendo el siguiente grafo no dirigido:

Como podemos ver no hay vértices de grado impar, luego puede haber un tour euleriano y no va a haber un camino euleriano.

Empezamos por el V4 por ejemplo, ya que tenemos menos riesgo de quitar una arista de corte, como estamos buscando un tour euleriano sabemos que debemos volver a este vértice al final del tour euleriano.

Quitamos la arista e3 y llegamos al vértice V3, como todo ha sido correcto pues no queda ningún vértice aislado podemos añadir la arista e3 al tour euleriano y seguir con el proceso.

Esto iremos haciéndolo vértice a vértice y arista a arista hasta llegar nuevamente a V4.

Si alguien tiene alguna duda le paso el ejercicio completo, con imágenes de todo el proceso, de todas formas el tour resultante por si alguien lo intenta y quiere ver si lo hizo bien: e3 e4 e10 e9 e7 e1 e5 e8 e6 e2.

CICLO Y CAMINO HAMILTONIANO

Un camino Hamiltoniano en un grafo G es un camino que atraviesa cada vértice del grafo exactamente una vez.

Un ciclo Hamiltoniano en un grafo G es un ciclo que atraviesa cada vértice del grafo exactamente una vez.

Un grafo es Hamiltoniano si existe un ciclo hamiltoniano.

Reglas básicas para construir caminos y ciclos hamiltonianos

Regla 1 – Si G no es conexo, no posee ciclos Hamiltonianos.

Regla 2 – Si G es un grafo con “n” vértices, entonces un camino Hamiltoniano debe tener exactamente n-1 aristas, y un ciclo Hamiltoniano n aristas.

Regla 3 – Si v es un vértice del grafo, entonces un camino Hamiltoniano debe tener al menos una arista incidente con v y como mucho dos.

Regla 4 – Si G es Hamiltoniano, entonces d_G(v) >=2, donde todos los vértices pertenecen a V.

Regla 5 – Si v perteneciente a V tiene grado 2, entonces las dos aristas incidentes con v deben aparecer en cualquier ciclo

Hamiltoniano de G.

Regla 6 – Si v perteneciente a V tiene grado mayor que 2, entonces cuando se intenta construir un ciclo Hamiltoniano, una vez que se pase por v, las aristas no utilizadas incidentes se dejan de tener en cuenta.

Regla 7 – Al construir un ciclo o camino Hamiltoniano para G, no se puede dar el caso de obtener un ciclo para un subgrafo de G a menos que contenta todos los vértices de G.

No podemos calcular si un grafo es Hamiltoniano en estos momentos, ni si tiene ciclos o caminos Hamiltonianos, lo único que podemos hacer es ver si no se cumple alguna de estas reglas y demostrar que NO lo es.

A raiz de todo lo mencionado tenemos el siguiente teorema:

Sea G un grafo dirigido bipartido con partición {X, Y}.

(1) Si G tiene un ciclo Hamiltoniano, entonces card(X) =  card(Y).

(2) Si G tiene un camino Hamiltoniano, entonces card (X) y card(Y) difieren a lo sumo en 1.

El recíproco es cierto para grafos bipartidos completos con más de 2 vértices.

Recordad la lógica de primer orden, que un grafo no sea Hamiltoniano no quiere decir que card(X) != card(Y).

Hoy Carlos ha empezado a explicar Magrada que aparentemente se ve un programa intuitivo y facil de manejar, nos a dado unas nociones básicas  de como manejarlo y en posteriores sesiones nos irá avanzando en materia

Poco más que contar acerca de lo que hemos hecho

Otro día más!!!!!!

Sesión correspondiente al dia (30/11/2010).

En esta sesión continuamos con el tema de grafos

• REPRESENTACIÓN MATRICIAL

-Matriz de adyacencia

Sea G un grafo con n vértices {v_i}. Llamamos matriz de adyacentes a la matriz de orden (nxn) (una matriz cuadrada, mismo número de filas y columnas) A=[a_i,j] tal que a_i,j es igual al número de aristas (arcos) del vértice v_i al v_j. Para los grafos no dirigidos los bucles se cuentan 2 veces.

La matriz de adyacencia define completamente el grafo.

EJEMPLO

Grafo no dirigido

Como se puede apreciar se trara de una matriz simétrica, los elementos de la diagonal inferior coinciden con los de la diagonal superior, a_i,j=a_j,i.

-Para un grafo no dirigido con matriz de adyacencia A, la suma de los elementos de la fila i (o columna i) es igual al grado del vértice vi.

Grafo dirigido

La fila representa el vértice origen y la columna el vértice destino.

-Para un grafo dirigido con matriz de adyacencia A, la suma de los elementos de la fila i es igual al grado de salida del vértice vi y la suma de los elementos de la columna j es igual al grado de entrada del vértice j.

-Sea G un grafo con matriz de adyacencia A. Entonces, el elemento (i, j) de la matriz A^r, r>= 1, es igual al número de cadenas r_i a r_j de longitud r.

-Matriz de incidencia

Sea G = {V, A} un grafo no dirigido con n vértices y m aristas siendo V = {v_i} y A  = {a_i}. Llamamos matriz de incidencia de G a la matriz de orden n x m.

Tenemos una matriz con “j” columnas que serán los arcos o aristas e “i” filas que serán los vértices, pero según sea un grafo dirigido o no dirigido tendremos una nomenclatura u otra.

–Grafo no dirigido:

M= [m_ij]/m_ij

->0 si v_i no es incidente con a_j

->1 si v_i es incidente con a_j

->2 si a_j es un bucle en v_i

Todas las columnas sumarán 2 porque una arista une 2 vértices. Es una forma de comprobar si hicimos bien la matriz incidente.

EJEMPLO

-Grafo dirigido:

B= [b_ij]/b_ij

->0 si v_i no es incidente con a_j

->1 si v_i es vértice inicial de a_j

->-1 si v_i es vértice final de a_j

->2 si a_j es un bucle en v_i

La suma de columnas de un grafo dirigido sin bucles da 0 porque tendremos un 1 por el arco saliente y un -1 por el entrante.

EJEMPLO

Propiedades de la matriz de incidencia:

• Para un grafo no dirigido, la suma de los elementos de cada fila de la matriz de incidencia es igual al grado del correspondiente vértice.
• Para un grafo no dirigido, la suma de los elementos de cada columna de la matriz de incidencia es igual a 2.
• Para un grafo dirigido sin bucles, la suma de los elementos de cada columna de la matriz de incidencia es igual a 0.

Tabla de aristas incidentes

Para un grafo no dirigido, llamaremos tabla de aristas incidentes a una tabla que lista, para cada vértice v, todas las aristas incidentes con v.

Tabla de arcos salientes

Para un grafo dirigido, llamaremos tablas de arcos salientes a una tabla que lista, para cada vértice v, todos los arcos salientes de v. Llamaremos tablas de arcos entrantes a una tabla que lista, para cada vértice v, todos los arcos entrantes en v.

• ACCESIBILIDAD Y CONECTIVIDAD

Sea  G = (V, A) un grafo dirigido.

1. Sean x_i , x_j ε V, diremos que x_j es alcanzable desde x_i o que x_i alcanza a x_j si existe un camino dirigido de x_i a x_j .

2. Sea V = {x_i}. Llamaremos matriz de accesibilidad asociada al grafo G a la matriz cuadrada de orden n definida por

R=[r_ij] /r_ij

->1 si x_i alcanza a x_j.

->0 en otro caso

3. Sea V = {x_i}. Llamaremos matriz de acceso asociado al grafo G a la matriz  cuadrada de orden n definida por

Q=[q_ij] /q_ij

->1 si x_i alcanzable desde x_j

->0 en otro caso

PROPOSICIÓN: Q =R^T

-CÁLCULO DE LA MATRIZ ACCESIBILIDAD

R(v_i) = conjunto de todos los vértices del grafo que son alcanzables desde el vértice v_i. Todos los elementos del conjunto son 1.

Luego como R(v_i) está formado por:

-el vértice v_i ={v_i}

-Г(v_i): conjunto de vértices alcanzable desde “v_i” mediante un camino dirigido de longitud 1.

-Г²(v): conjunto de vértices alcanzable desde “v_i” mediante un camino dirigido de longitud 2.

-Г^p(v): conjunto de vértices alcanzable desde “v_i” mediante un camino dirigido de longitud p, p<= n (número de vértices).

Podemos calcular R(v_i) de la siguiente forma:

R(v_i)= {v_i} U Г(v_i) U…U Г^p(v_i), p <= n.



Sesión correspondiente al día (23/11/2010).

Hoy hemos hecho el examen de PROLOG, esto quiere decir que ponemos fin a esta parte de practicas y a partir de ahora seguiremos con el software MAGRADA, pero eso será a partir de la póxima sesión.

Después del examen Carlos ha dejado tiempo para seguir con las distintas prácticas de PROLOG y ha subido al campus la última fase del juego que es totalmente opcional para aquellos que quieran hacerla y subir nota.

Cuando terminemos hayque pedir una tutoría para mostrar el programa a Carlos.

Y con esto y un bizcocho hasta mañana a las 8.

Hola vamos con más materia de matemáticas discreta que de discrena nada de nada

Sesión correspondiente al día (23/11/2010).

• Relación entre grados y aristas: teorema y grafo corolario

Teorema

1.Sea G = (V, A) un grafo, entonces:

Σ dG(v) = 2card(A)

Recordamos que:

-La cardinalidad es el número de elementos de un conjunto.

–d g (V):número de aristas incidentes con un vértice. Cada bucle cuenta por dos.

Σ ds(v) = Σ de(v) = card(A)

Corolario

El número de vértices de grado impar de un grafo es par.

• Caminos y conexión

Definiciones: Sea G un grafo no dirigido:

1. Una cadena es una sucesión finita W = v0e1v1….ekvk cuyos términos son alternativamente vértices y aristas.

2. La longitud de una cadena es el número de aristas que contiene.

3. Una cadena simple es una cadena con todas sus aristas distintas.

4. Un camino es una cadena con todos sus vértices distintos.

5. Una cadena cerrada es una cadena de longtud no nula en donde el vértice inicial y final coinciden.

6. Un ciclo es una cadena simple cerrada con todos sus vértices distintos.

Estos conceptos son los mismos para grafos dirigidos salvo que las direcciones de los arcos deben concordar con la dirección del camino o cadena.

En el caso dirigido el ciclo recibe el nombre de circuito.

7. Diremos que dos vértices u y v están conectados si existe un camino de u a v y viceversa.

8. Un grafo es conexo si todo par de vértices están conectados.

9. Un grafo dirigido es débilmente conexo si su grafo no dirigido asociado es conexo.

EJEMPLOS

·Cadena

·Longitud: la longitud del grafo anterior sería 2.

·Cadena simple: la siguiente sería una cadena simple.

Tenemos el siguiente grafo:

Vamos a ver las distintas propiedades y ver el tipo de grafo:

a) ¿Es dirigido?

Sí lo es, como vemos tiene arcos.

b) ¿Es simple?

Sí porque no hay ningún vértice con dos arcos de la misma dirección.

c) ¿Completo?

No es completo ya que no todos los vértices están conectados con todos.

d) ¿Bipartido?

No es bipartido pues no podemos hacer dos conjuntos en los cuales no hayan uniones entre vértices.

e) Grados

Vértice	de(v) (entrantes)	ds(v) (salientes)
V1	1	1
V2	2	3
V3	1	2
V4	1	2
V5	4	1
V6	1	1

CONEXIÓN

Conexo: un grafo es conexo si todo par de vértices está conectado.

Débilmente conexo: Cuando un grafo dirigido no es conexo se puede ver si es débilmente conexo, para ello veremos si su grafo no dirigido asociado es conexo. En el caso que lo sea se podrá decir que el grafo es débilmente conexo. El grafo asociado es el mismo grafo pero no dirigido, es decir, pierde los arcos y los sustituye por aristas.

Relación binaria: Sea G=(V,A) no dirigido. En V se define la relación binaria /R: u y v ε V, u Rv, si u y v están conectados.

R= relacionado.

R es una relación de equivalencia–> determinada partición en {V1, V2,…Vv}

A cada subgrafo de G: G[V1], G[V2]…..G[R] determinado por el conjunto de vértices de cada clase de equivalencia de la relación R se le llama componente conexa del grafo G.

Las posibles relaciones son:

Conexón u->v:

1-Reflexiva: uRv
2-Simétrica: uRv, vRu
3- Transitiva: uRv, vRt, uRt

Si un grafo no es conexo, se dividirá en subgrafos que sí lo sean y que a su vez estén conectados.

Se dividirá el grafo en componentes conexas que son los mayores subgrafos conexos de un grafo G.

Cada vértice del grafo sólo puede pertenecer a una componente conexa.

Por hoy ya esta bién mañana más, to-morrow un montón y a vivir que son two days….

Sesión correspondiente al día (16/11/2010).

Hoy hemos continuado con las fases 6 y 7. Carlos no ha avanzado dando conceptos de teoria ya que las practicas son más largas y ha dejado tiempo para que la gente se ponga al día.

Y ya esta todo la semana que viene más.

Hola buenas hoy me toca currar doble ya que he ido dejando esto para más tarde y me he juntado con que tengo que hacer 2 entradas hoy y mañana tenemos clase de mates osea que mañana me tocará hacer otra, bueno voy a ver de lo que me acuerdo ayudandome de los apuntes y a ver que sale, espero que bien jejeje.

Sesión correspondiente al día (16/11/2010).

En esta sesión hemos continuado el tema de los grafos.

• Tipos de grafos

·Grafo no dirigido asociado: es un grafo dirigido a un grafo con el mismo conjunto de vértices y en el que se han ognorado las direcciones de los vértices.

·Grafo mixto: contiene tantos arcos como aristas, es decir, contiene ambas cosas.

·Grafo simple:

1-No dirigido= sin bucles y no hay dos aristas que unan el mismo par de vértices.

2-Dirigidos= sin bucles y no hay dos arcos uniendo el mismo par de vértices y con la misma dirección.

Si un grafo no es simple se llama multigrafo.

No es simple ya que tenemos un bucle y dos aristas con la misma dirección uniendo los mismos vértices.

Este sí es simple porque aunque tiene 2 aristas, son de distinta dirección.

·Grafo no dirigido completo: si hay al menos una arista (arco) uniendo cada par de vértices distintos.

Si estos grafos son simples se denominan k_n.

-k_n= grafos completos no dirigidos y simples con “n” vértices.

Ejemplo:

• Contar aristas de un grafo

Vamos vértice a vértice uniendo con los que todavía no están unidos. Al final los sumamos.

Una vez tenemos el número de vértices y de aristas  se hace lo siguiente: (vértices * aristas)/2 = aristas del grafo completo

Para los grafos k_n hacemos |A|= (n*(n-1))/2

• Determinar el número crómatico de un grafo, grafos bipartidos y grafo k_m,n

Se parte el grafo en dos formando un grafo bipartido.

·Grafo bipartido: fromado por dos conjuntos de vértices {V1, V2}

-Los vértices de ambos conjuntos han de estar conectados entre sí pero los de V1 no lo estarán entre ellos y tampoco lo estarán los de V2.

-La unión de ambos dará el conjunto completo.

-Su intersección dará el conjunto vacío.

Ejemplo:

V1={x, t}

V2={z, y}

En este grafo es sencillo distinguir los dos grupos de vértices pero en un grafo más complejo no es tan sencillo. En estos casos debemos seguir el siguiente procedimiento:

1-Elegimos un vértice cualquiera.

2-Ponemos una etiquieta a ese vértice y una distinta para los vértices conectados a él, esta etiquieta es distinta al vértice elegido pero común para los vértices conectados a él.

Ejemplo:

En este caso hemos empezado etiquetando el vértice “2″ con un 2 y los vértices adyacentes con un “1″, después el vértice que no es adyacente lo hemos vuelto a etiquetar con un “2″ y sus adyacentes con un “1″.

Una vez hecho esto tendremos un conjunto formado por los vértices con la etiquieta “1″ y otro formado por la etiquieta “2″.

V1={0, 1, 3, 4, 6, 7}

V2={2, 5}

Ahora se sabe cuántos colores son necesarios para pintar este grafo. Con dos colores será suficiente ya que la única condición para pintarlos es que no hayan dos grafos adyacentes pintados iguales y gracias a esta distinción de conjuntos se puede cumplir dicha condición.

Para los grafos dirigidos se hará con su grafo asociado (para comprobar si es bipartido).

También se puede tener grafos bipartidos completos si cada vértice de V1 está unido con vada vértice de V2.

·k_m,n: grafo no dirigido bipartido completo y simple con card(V1)=m, card(V2)=n.

Subgrafo y grafo generador

·Subgrafo: si tenemos un grafo G= (V, A) y un grafo H=(V’, A’). H es subgrafo de G si el número de vértices y aristas de H es menor o igual al de G.

Ejemplo:

También sería un  subgrafo un único vértice (sin aristas) o el propio grafo. Si se cumple que el número de vértices del subgrafo es menor o igual al número de vértices del grafo original y que el número de aristas del subgrafo es menor o igual que el número de aristas del grafo original, entonces se trata de un subgrafo.

·Grafo generador: un subgrafo es generador si V(G)=V(H).

Todo grafo tiene un subgrafo generador simple.

Si el grafo G tiene el mismo número de vértices que el grafo H, entonces H es un subgrafo generador simple, siempre respetando el número de aristas para que sea un subgrafo, es decir, que el número de aristas de H sea menor o igual que el número de aristas de G.

H1 es un subgrafo ya que cumple todo lo comentado y además es generador porque tiene el mismo número de vértices que G1. También es simple.

• Grado de un vértice de un grafo no dirigido y de un grafo dirigido

·Grado de un vértice de un grafo no dirigido:

d_G(v): número de aristas incidentes con él (número de aristas que lo tienen como extremo). Cada bucle se cuenta dos veces.

Γ(v): conjunto de vértices adyacentes a V.

·Grado de un vértice de un grafo dirigido: Se cuentan arcos de entrada y salida y el grado total es la suma de ambos.

Y hasta aqui vimos ahora voy con lo de la siguiente semana!!!