![Page 1: Tipos de grafos - cs.buap.mxmtovar/doc/MatDisc/grafosParte2Simple.pdf · Complemento de un grafo (G’) 9/29/2015 13 Grafo G Grafo Complemento G’ Es el grafo que le falta al grafo](https://reader030.vdocumento.com/reader030/viewer/2022040105/5e1e5bd701252c4b7e09a407/html5/thumbnails/1.jpg)
![Page 2: Tipos de grafos - cs.buap.mxmtovar/doc/MatDisc/grafosParte2Simple.pdf · Complemento de un grafo (G’) 9/29/2015 13 Grafo G Grafo Complemento G’ Es el grafo que le falta al grafo](https://reader030.vdocumento.com/reader030/viewer/2022040105/5e1e5bd701252c4b7e09a407/html5/thumbnails/2.jpg)
Tipos de grafos
9/29/2015 2
Grafo dirigido(Dígrafo) : los arcos en el grafo tienen una dirección asociada
Grafo Ponderado: cada arco del grafo tiene asociado un peso o valor
Grafo simple: son aquellos grafos que no tienen lazos ni lados paralelos
Grafo plano: es aquel que se puede dibujar en solo plano y cuyos arcos no se cruzan entre si
![Page 3: Tipos de grafos - cs.buap.mxmtovar/doc/MatDisc/grafosParte2Simple.pdf · Complemento de un grafo (G’) 9/29/2015 13 Grafo G Grafo Complemento G’ Es el grafo que le falta al grafo](https://reader030.vdocumento.com/reader030/viewer/2022040105/5e1e5bd701252c4b7e09a407/html5/thumbnails/3.jpg)
Tipos de grafos
9/29/2015 3
Grafo completo de n vértices (Kn): es el grafo donde cada vértice esta relacionado con todos los demás, sin lazos ni lados paralelos. El grado de cada vértice es (n-1) y el número de lados es (n(n-1))/2
Grafo completo K5
Grafo Bipartito: Es el grafo que está compuesto por dos conjuntos A={a1,a2,a3,…,an} y B={b1,b2,b3,…,bm) en donde los elementos del conjunto A se relacionan con los del conjunto B, pero entre los vértices de un mismo conjunto no existe arista que los una. Un grafo bipartito nunca tiene un ciclo de longitud impar
![Page 4: Tipos de grafos - cs.buap.mxmtovar/doc/MatDisc/grafosParte2Simple.pdf · Complemento de un grafo (G’) 9/29/2015 13 Grafo G Grafo Complemento G’ Es el grafo que le falta al grafo](https://reader030.vdocumento.com/reader030/viewer/2022040105/5e1e5bd701252c4b7e09a407/html5/thumbnails/4.jpg)
Tipos de grafos
9/29/2015 4
Grafo Bipartito completo (Kn,m): Es el grafo que está compuesto por dos conjuntos de vértices, uno de ellos A={a1,a2,a3,…,an} y otro B={b1,b2,b3,…,bm), y en el que cada vértice de A está unido con todos los vértices de B, pero entre los vértices de un mismo conjunto no existe arista que los una.
Grafo Bipartito Completo K4,2
Grafo Bipartito Completo K2,3
1 2 3 4
a b
1
2
3
a
b
![Page 5: Tipos de grafos - cs.buap.mxmtovar/doc/MatDisc/grafosParte2Simple.pdf · Complemento de un grafo (G’) 9/29/2015 13 Grafo G Grafo Complemento G’ Es el grafo que le falta al grafo](https://reader030.vdocumento.com/reader030/viewer/2022040105/5e1e5bd701252c4b7e09a407/html5/thumbnails/5.jpg)
Ejemplos
![Page 6: Tipos de grafos - cs.buap.mxmtovar/doc/MatDisc/grafosParte2Simple.pdf · Complemento de un grafo (G’) 9/29/2015 13 Grafo G Grafo Complemento G’ Es el grafo que le falta al grafo](https://reader030.vdocumento.com/reader030/viewer/2022040105/5e1e5bd701252c4b7e09a407/html5/thumbnails/6.jpg)
Ejemplo: empleados y trabajo de un proyecto
![Page 7: Tipos de grafos - cs.buap.mxmtovar/doc/MatDisc/grafosParte2Simple.pdf · Complemento de un grafo (G’) 9/29/2015 13 Grafo G Grafo Complemento G’ Es el grafo que le falta al grafo](https://reader030.vdocumento.com/reader030/viewer/2022040105/5e1e5bd701252c4b7e09a407/html5/thumbnails/7.jpg)
Aplicaciones
• Redes
(a)Topología estrella
(b) Anillo
(c) Híbrido
Bipartito completo K1,n
Ciclos Cn Rueda Wn
![Page 8: Tipos de grafos - cs.buap.mxmtovar/doc/MatDisc/grafosParte2Simple.pdf · Complemento de un grafo (G’) 9/29/2015 13 Grafo G Grafo Complemento G’ Es el grafo que le falta al grafo](https://reader030.vdocumento.com/reader030/viewer/2022040105/5e1e5bd701252c4b7e09a407/html5/thumbnails/8.jpg)
Ejercicios
• Determina si los siguientes grafos son bipartitos:
![Page 9: Tipos de grafos - cs.buap.mxmtovar/doc/MatDisc/grafosParte2Simple.pdf · Complemento de un grafo (G’) 9/29/2015 13 Grafo G Grafo Complemento G’ Es el grafo que le falta al grafo](https://reader030.vdocumento.com/reader030/viewer/2022040105/5e1e5bd701252c4b7e09a407/html5/thumbnails/9.jpg)
Subgrafo de un grafo
• Un subgrafo de un grafo G=(V,E) es un grafo H=(W,F), donde w V y F E. Un subgrafo H de G es un subgrafo propio de G si H ≠ G.
K5 Subgrafo
![Page 10: Tipos de grafos - cs.buap.mxmtovar/doc/MatDisc/grafosParte2Simple.pdf · Complemento de un grafo (G’) 9/29/2015 13 Grafo G Grafo Complemento G’ Es el grafo que le falta al grafo](https://reader030.vdocumento.com/reader030/viewer/2022040105/5e1e5bd701252c4b7e09a407/html5/thumbnails/10.jpg)
Subgrafo inducido
• Sea G=(V,E) un simple grafo. El subgrafo inducido por un subconjunto W del conjunto de vértices V es el grafo (W,F), donde el conjunto de las aristas F contienen una arista en E si y sólo si ambos puntos finales de la arista están en W.
Subgrafo inducido
![Page 11: Tipos de grafos - cs.buap.mxmtovar/doc/MatDisc/grafosParte2Simple.pdf · Complemento de un grafo (G’) 9/29/2015 13 Grafo G Grafo Complemento G’ Es el grafo que le falta al grafo](https://reader030.vdocumento.com/reader030/viewer/2022040105/5e1e5bd701252c4b7e09a407/html5/thumbnails/11.jpg)
Unión de grafos
• La unión de dos simples grafos G1=(V1,E1) y G2=(V2,E2) es el grafo simple con el conjunto de vértices V1 U V2 y el conjunto de aristas E1 U E2. La unión de G1 y G2 se denota por G1 U G2.
![Page 12: Tipos de grafos - cs.buap.mxmtovar/doc/MatDisc/grafosParte2Simple.pdf · Complemento de un grafo (G’) 9/29/2015 13 Grafo G Grafo Complemento G’ Es el grafo que le falta al grafo](https://reader030.vdocumento.com/reader030/viewer/2022040105/5e1e5bd701252c4b7e09a407/html5/thumbnails/12.jpg)
Ejercicio • Encuentra la unión de cada par de
grafos
![Page 13: Tipos de grafos - cs.buap.mxmtovar/doc/MatDisc/grafosParte2Simple.pdf · Complemento de un grafo (G’) 9/29/2015 13 Grafo G Grafo Complemento G’ Es el grafo que le falta al grafo](https://reader030.vdocumento.com/reader030/viewer/2022040105/5e1e5bd701252c4b7e09a407/html5/thumbnails/13.jpg)
Complemento de un grafo (G’)
9/29/2015
13
Grafo G Grafo Complemento G’
Es el grafo que le falta al grafo G, de forma que entre ambos forman un grafo completo de n vértices. Este grafo no tiene lazos ni arcos paralelos. El complemento G’ de un grafo simple G es el grafo con los mismos vértices que G, tal que para cualquier par de vértices que son adyacentes en G’ si y sólo si no son adyacentes en G.
A
D
E
C B
F
A
D
E
C B F
![Page 14: Tipos de grafos - cs.buap.mxmtovar/doc/MatDisc/grafosParte2Simple.pdf · Complemento de un grafo (G’) 9/29/2015 13 Grafo G Grafo Complemento G’ Es el grafo que le falta al grafo](https://reader030.vdocumento.com/reader030/viewer/2022040105/5e1e5bd701252c4b7e09a407/html5/thumbnails/14.jpg)
Representación de grafos
• Se especifica los vértices adyacentes a cada vértice del grafo.
– Listas de adyacencia
Vértice Vértices adyacentes
a b, c, e
b a
c a, e, d
d c, e
e a, c, d
![Page 15: Tipos de grafos - cs.buap.mxmtovar/doc/MatDisc/grafosParte2Simple.pdf · Complemento de un grafo (G’) 9/29/2015 13 Grafo G Grafo Complemento G’ Es el grafo que le falta al grafo](https://reader030.vdocumento.com/reader030/viewer/2022040105/5e1e5bd701252c4b7e09a407/html5/thumbnails/15.jpg)
Ejercicio
• Representa el grafo dirigido al listar todos los vértices del grafo con sus vértices iniciales y terminales.
![Page 16: Tipos de grafos - cs.buap.mxmtovar/doc/MatDisc/grafosParte2Simple.pdf · Complemento de un grafo (G’) 9/29/2015 13 Grafo G Grafo Complemento G’ Es el grafo que le falta al grafo](https://reader030.vdocumento.com/reader030/viewer/2022040105/5e1e5bd701252c4b7e09a407/html5/thumbnails/16.jpg)
Solución
Vértice inicial
Vértices terminales
a b, c, e, d
b b, d,
c a, e, c
d
e b, c, d
![Page 17: Tipos de grafos - cs.buap.mxmtovar/doc/MatDisc/grafosParte2Simple.pdf · Complemento de un grafo (G’) 9/29/2015 13 Grafo G Grafo Complemento G’ Es el grafo que le falta al grafo](https://reader030.vdocumento.com/reader030/viewer/2022040105/5e1e5bd701252c4b7e09a407/html5/thumbnails/17.jpg)
Representación de grafos
• Matriz de adyacencia
![Page 18: Tipos de grafos - cs.buap.mxmtovar/doc/MatDisc/grafosParte2Simple.pdf · Complemento de un grafo (G’) 9/29/2015 13 Grafo G Grafo Complemento G’ Es el grafo que le falta al grafo](https://reader030.vdocumento.com/reader030/viewer/2022040105/5e1e5bd701252c4b7e09a407/html5/thumbnails/18.jpg)
Ejercicio
• Dibuja el grafo de la siguiente matriz de adyacencia
![Page 19: Tipos de grafos - cs.buap.mxmtovar/doc/MatDisc/grafosParte2Simple.pdf · Complemento de un grafo (G’) 9/29/2015 13 Grafo G Grafo Complemento G’ Es el grafo que le falta al grafo](https://reader030.vdocumento.com/reader030/viewer/2022040105/5e1e5bd701252c4b7e09a407/html5/thumbnails/19.jpg)
Solución
![Page 20: Tipos de grafos - cs.buap.mxmtovar/doc/MatDisc/grafosParte2Simple.pdf · Complemento de un grafo (G’) 9/29/2015 13 Grafo G Grafo Complemento G’ Es el grafo que le falta al grafo](https://reader030.vdocumento.com/reader030/viewer/2022040105/5e1e5bd701252c4b7e09a407/html5/thumbnails/20.jpg)
Ejercicio
• Encuentra la matriz de adyacencia.
![Page 21: Tipos de grafos - cs.buap.mxmtovar/doc/MatDisc/grafosParte2Simple.pdf · Complemento de un grafo (G’) 9/29/2015 13 Grafo G Grafo Complemento G’ Es el grafo que le falta al grafo](https://reader030.vdocumento.com/reader030/viewer/2022040105/5e1e5bd701252c4b7e09a407/html5/thumbnails/21.jpg)
Solución
a, b, c, d
![Page 22: Tipos de grafos - cs.buap.mxmtovar/doc/MatDisc/grafosParte2Simple.pdf · Complemento de un grafo (G’) 9/29/2015 13 Grafo G Grafo Complemento G’ Es el grafo que le falta al grafo](https://reader030.vdocumento.com/reader030/viewer/2022040105/5e1e5bd701252c4b7e09a407/html5/thumbnails/22.jpg)
Matriz de incidencia
• La matriz de incidencia con respecto a V y E es una matriz de nxm, M=[mij], donde
• Mij=1 cuando la arista ej es incidente con vi; Mij=0 de lo contrario.
![Page 23: Tipos de grafos - cs.buap.mxmtovar/doc/MatDisc/grafosParte2Simple.pdf · Complemento de un grafo (G’) 9/29/2015 13 Grafo G Grafo Complemento G’ Es el grafo que le falta al grafo](https://reader030.vdocumento.com/reader030/viewer/2022040105/5e1e5bd701252c4b7e09a407/html5/thumbnails/23.jpg)
Ejercicio
• Obtener la matriz de incidencia del siguiente grafo:
![Page 24: Tipos de grafos - cs.buap.mxmtovar/doc/MatDisc/grafosParte2Simple.pdf · Complemento de un grafo (G’) 9/29/2015 13 Grafo G Grafo Complemento G’ Es el grafo que le falta al grafo](https://reader030.vdocumento.com/reader030/viewer/2022040105/5e1e5bd701252c4b7e09a407/html5/thumbnails/24.jpg)
Solución
• Obtener la matriz de incidencia del siguiente grafo:
![Page 25: Tipos de grafos - cs.buap.mxmtovar/doc/MatDisc/grafosParte2Simple.pdf · Complemento de un grafo (G’) 9/29/2015 13 Grafo G Grafo Complemento G’ Es el grafo que le falta al grafo](https://reader030.vdocumento.com/reader030/viewer/2022040105/5e1e5bd701252c4b7e09a407/html5/thumbnails/25.jpg)
Ejercicios
• Construye la representación de lista de adyacencia, matriz de adyacencia y matriz de incidencia de los siguientes grafos: