Day: noviembre 29, 2010

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!!!