Teoria De Grafos

Tema 5: Grafos

RafaC - Matemática Discreta - UCM 07/08

1

1. 2. 3. 4. 5. 6. 7. 8. 9.

Tipos de grafos Conceptos Básicos Representación de grafos Subgrafos. Grafos complementarios Caminos y conectividad Grafos Bipartitos Recorridos, eulerianos o hamiltonianos Isomorfismo de grafos Árboles
RafaC - Matemática Discreta - UCM 07/08 2

Indice

Tipos de Grafos






Un grafo Ges un par (V,E) donde:  V ={v1,…,vn} es un conjunto de vértices  E = {e1,…,em} es un conjunto de aristas, con cada ek ∈ {vi, vj}, con vi, vj ∈ V, vi ≠ vj Los vértices se representan como puntos y las aristas como líneas entre vértices Ejemplo:
  

G = (V,E) V = {a,b,c,d } E = {{a,b}, {b,c}, {a,c}, {a,d}, {d,b} }

RafaC - Matemática Discreta - UCM 07/08

3

Tipos de Grafos
Ejemplo: red de ordenadores

RafaC - Matemática Discreta - UCM 07/08

4

Tipos de grafos
 

Es importante recordar que un mismo grafo puede tener diferentes representaciones gráficas Ejemplo:

Dos representaciones del mismo grafo G = ({a,b,c,d,e,f},{{a,b},{a,e},{a,f}{e,f},{b,c},{c,d},{e,d},{d,f}})

RafaC - Matemática Discreta - UCM 07/08

5

Tipos de Grafos


Si el ordeninfluye en la aristas se habla de grafos dirigidos:



En este caso a las aristas se les llama arcos y se representan como pares para indicar el orden:
 

V = { a,b,c,d,e} A ={(e,a), (a,b), (b,a), (d,a), (c,d), (d,c),(b,c),(c,b) }
RafaC - Matemática Discreta - UCM 07/08 6

Tipos de Grafos


Si se permite que haya más de una arista se habla de multigrafos:

RafaC - MatemáticaDiscreta - UCM 07/08

7

Tipos de Grafos


Cuando las aristas tienen un valor numérico asociado se llama de grafos valorados:



Al valor numérico asociado se le llama coste de la arista
RafaC - Matemática Discreta - UCM 07/08 8

Tipos de Grafos


Los tipos anteriores pueden combinarse, dando lugar por ejemplo a multigrafos valorados, o grafos dirigidos valorados, etc. En el restodel tema cuando no se diga lo contrario G representará un grafo o multigrafo no dirigido



RafaC - Matemática Discreta - UCM 07/08

9

Conceptos Básicos
   

Dos vértices se dicen adyacentes si existe una arista que los une Los vértices que forman una arista son los extremos de la arista Si v es un extremo de una arista a, se dice que a es incidente con v El grado de un vérticev, gr(v) es el número de aristas incidentes en v. Si hace falta indicar el grafo en el que está v escribiremos gr(G,v)
RafaC - Matemática Discreta - UCM 07/08 10

Conceptos Básicos


Ejemplo:



gr(6)= _______

gr(1) = ________
11

RafaC - Matemática Discreta - UCM 07/08

Conceptos Básicos


Teorema (de los “apretones de manos”) Sea G=(V,A) un grafo. Entonces: ∑ gr(v) =2|A|
v∈ V





Significado: la suma de los grados de todos los vértices es igual a 2 veces el número de aristas Explicación:

RafaC - Matemática Discreta - UCM 07/08

12

Conceptos Básicos


Ejemplo:

 

gr(a)+gr(b)+gr(c)+gr(d)+gr(e)+gr(f) = 3+4+5+2+4+4 = 22 2|A| = 2 ____ = _____
RafaC - Matemática Discreta - UCM 07/08 13

Conceptos Básicos


Para cada n≥1 se llamagrafo completo de orden n, y se representa por Kn, al grafo de n vértices conectados de todas las formas posibles:



Pregunta: ¿Cuántas aristas tiene en general Kn?
RafaC - Matemática Discreta - UCM 07/08 14

Conceptos Básicos


Se llama ciclo de grado n, y se denota Cn, a G=({v1,…,vn}, {{v1, v2}, {v2, v3},…, {vn-1, vn}, {vn, v1}} )



Nota: A menudo sólo se consideran ciclospara n≥3
RafaC - Matemática Discreta - UCM 07/08

15

Representación de Grafos
 

Para representar los grafos a menudo se utiliza la llamada matriz de adyacencia Se construye imaginando que en las filas y las columnas corresponden a los vértices. Se pone un 0 para indicar que 2 vértices no son adyacentes, y un 1 para indicar que sí lo son:
1 2 3 4 5 6 Matriz de Adyacencia de G

1 2 3...