teoria de grafos
TRANSCRIPT
INSTITUTO TECNOLOGICO DE LA
COSTA GRANDE
INGENIERÍA EN SISTEMAS COMPUTACIONALES
MATEMÁTICAS PARA COMPUTADORA
UNIDAD III
TEORIA DE GRAFOS
YESENIA SÁNCHEZ GARCÍA
09570098
CATEDRÁTICO:
LUIS DANIEL HERRERA BARRIOS
LUNES 26 DE JULIO DE 2010
UNIDAD III TEORÍA DE GRAFOS
Ejercicios:
En un torneo, el Nieve venció a los Faisanes una vez, el Rascacielos venció al
Tuna una vez, el Nieve venció al Rascacielos dos veces, los Faisanes vencieron al
Tuna una vez y los Faisanes vencieron al Rascacielos una vez. En los ejercicios 1
al 14, use una gráfica para modelar el torneo. Los equipos son los vértices.
Describa el tipo de grafica usada (no dirigida, dirigida, simple).
1. Hay una arista entre los equipos si los equipos jugaron
v1 • •v2 SIMPLE
v3 • •v4
V1=Nieve
V2=Faisanes
V3=Rascacielos
V4=Tuna
2. Hay una arista entre los equipos para cada juego jugado
v1 • •v2 No dirigida
v3 • •v4
3. Hay una arista del equipo t, al equipo t, si t, venció a t, al menos una vez.
v1 • •v2 Dirigida
v3 • •v4
4. Hay una arista del equipo t, al equipo t, por cada victoria de t, sobre t.
v1 • •v2 Dirigida
v3>• •v4
Explique por qué ninguna gráfica en los ejercicios 5 al 7 tiene una trayectoria del
vértice a al vértice a que pasa por cada arista justo una vez.
5. Ninguna de las gráficas siguientes tiene esa trayectoria, porque en cada
grafo existe un numero par de vértices de grado impar, por lo tanto nunca
pasara por cada arista solo una vez.
6.
7.
c d
e b
a
c d
b a
i h g
f e d
c b a
C
Pruebe cada grafica en los ejercicios 8 al 10 tiene una trayectoria del vértice a
que pasa por cada arista justo una vez, encontrando la trayectoria por
inspección.
8.
{a, b, c, e, f, d, b, e, d, c, a}
9. {a, c, f, e, c, b, e, d, b, a}
10. {a, b, d, e, b, c, f, e, c, g, e, h, i, f, h, g, d, a}
e d
f
c b
a
c b
e f d
a
i h g
f e d
c b a
Para cada grafica G= (V, E) en los ejercicios 11 al 13, encuentre V, E, todas
las aristas paralelas, lazos, vértices aislados, y diga si G es una gráfica
simple. Además, diga sobre que vértices incide la arista .
11.
e1 = (v1, v2)
paralelas = (v1, v2)
Lazos = v1
No tiene vértices aislados
No es grafica simple
e1 = (v1, v2)
12.
No tiene paralelas
No tiene lazos
No tiene vértices aislados
Es una gráfica simple
e1 = (v2, v4)
e5
e4
e3
e2 e1
v4
v3 v
2
v1
v5 v
4
v3
v2
e8
e7
e3
e1
e5
e4
e2
v1
e6
13.
No tiene paralelas
No tiene lazos
V aislados = (v1, v2, v3)
Es una gráfica simple
e1= No existe
14. Dibuje k3 y k5
•
k3• •
• •
k5 • •
•
15. Encuentre una fórmula para el numero de aristas en Kn
n > 2; n x 1
16. De un ejemplo de una gráfica bipartida diferente de los ejemplos de esta
sección. Especifique los conjuntos ajenos de vértices.
V= { 1, 2, 3, 4, 5, 6, 7}
V1= { 1, 2, 3, 4}
V2= {5, 6, 7}
v1• e1
v2• e3 •v5
e5 e2
v3• •v6
e7 e4
v4• e6 •v7
v3 v
2
v1
Determine que grafica en los ejercicios 17 al 23 son bipartitas. Si la gráfica
es bipartitas, especifique los conjuntos ajenos de vértices.
17.
V = {1, 2, 3, 4, 5}
V1 = {2, 5}
V2 = {1, 3, 4}
Si es bipartita
18.
V = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
V1 = {1, 2, 3, 4}
V2 = {5, 6, 7, 8, 9, 10}
Si es bipartita
19. Figura 8.1.2
No es bipartita
20. Figura 8.1.5
e3
v2 • • • v5
e4 v4
e1 e5
v1 • e2 •v3
•v6
No es bipartita
e5
e3
e2
v5 v
4
v3
v2 v
1
e1
e4
e9
e8
e7
e6
e5
e4
e3
v10
v
9
v8 v
7 v
6 v
5
v4
v3 v
2 v
1
e1
e2
21. Ejercicio 11
No es bipartita.
22. Ejercicio 12
No es bipartita
23. Ejercicio 13
No es bipartita
e5
e4
e3
e2 e1
v4
v3 v
2
v1
v5 v
4
v3
v2
e8
e7
e3
e1
e5
e4
e2
v1
e6
v3 v
2
v1