Ciclos y Arboles - matematicas Discretas

INSTITUTO TECNOLOGICO DE PACHUCA


MATEMATICAS DISCRETAS II
Ing. Mario Torres Serrano.

Trabajo de Grafos y Arboles


Equipo No.1
Samuel
Daniel
Diego
ITIC´S

13/Jun/2013

TEORIA DE GRAFICAS

PREGUNTAS
1. Defina grafica no dirigida:
R=conjunto de pares no ordenados de elementos “V”
2. De un ejemplo de algo en la vida real que se pueda moldear por medio de una gráfica nodirigida.
R= para dar un ejemplo de esto
3. Defina grafica dirigida.
R= conjunto de pares ordenados con elementos “v”
4. De un ejemplo de algo en la vida real que se pueda moldear por una gráfica dirigida.
R= El recorrido que se hace en algún viaje
5. ¿Qué significa para una arista ser incidente sobre un vértice?
R= las veces que pueden tener contacto con el vértice
6. ¿Qué significa paraun vértice ser incidente sobre una arista?
R= las veces que pueden tener contacto con el arista
7. ¿Qué significa para u y w ser vértices adyacentes?
R=Que tiene un arista en común.
8. ¿Qué son aristas paralelas?
R= también son llamadas aristas múltiples. Son 2 o más aristas que son incidentes con al menos 2 vértices.
9. ¿Qué es un lazo?
R= En un grafo Es una arista que conecta al mismovértice consigo mismo
10. ¿Qué es un vértice aislado?
R= Es el que no tiene conexión con ninguno de los demás
11. ¿Qué es una gráfica simple?
R= Es un grafo dirigido o no Dirigido que tiene Bucles y que no es multígrafo
12. ¿Qué es una gráfica ponderada?
R= Asocia a un Valor o peso a cada arista en cada grupo
13. De un ejemplo de algo en la vida real que se pueda moldear por una gráficaponderada.
R= Un ejemplo seria el tiempo que se tarda en llegar a un cierto lugar tomando diferentes caminos si cada parte del camino diferentes valores en tiempo
14. defina longitud de trayectoria con una gráfica ponderada.
R= Es aquel valor que se va acumulando conforme se va avanzando por los valores de las aristas hasta llegar a un cierto punto tomando un camino específico.
15. ¿Qué es unagráfica de similitud?
R= son aquellos que se derivan de otros Grafos

Explique porque ninguna grafica en los ejercicios 5 al 7 tiene una trayectoria del vértice a al vértice que pasa por cada arista justo una vez



5.-






6.-



7.-













2.- pruebe que cada grafica en los ejercicios 8 al 10 tiene una trayectoria de vértice a al vértice a quepasa por cada arista justo una vez, encontrando la trayectoria por inspección.





8.-




9.-





10.-






3.- 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 un grafo simple, además, diga sobre que vértices incide la arista e1.

11.-





12.-13.-










4.- Determine que grafica en los ejercicios 17 al 23 son bipartitas. Si la gráfica es bipartita, especifique los conjuntos ajenos a los vértices


17.-




18.-






19.-



















21 ejercicio 11







22.- ejercicio 12





23.- ejercicio 13





24.- dibuje k 2,3 k3, 325.- dibuje k3 y k5



















TRAYECTORIAS Y CICLOS

1. ¿Qué es una trayectoria?
R= una trayectoria es una sucesión de vértices y aristas, en la que las aristas e1 indica en los vértices vv-1 y v1 para i= 1….N.
2. ¿Qué es una trayectoria simple?
R= es una trayectoria sin vértices repetidos.
3. De un ejemplo de una trayectoria que no sea simple.R=(1,2,3,1)
4. ¿Qué es un ciclo?
R= es una trayectoria de longitud diferente de 0 de V a V sin aristas repetidos.
5. ¿Qué es un ciclo simple?
R= Es un ciclo de vértice V al vértice V en donde, exepto por el vértice inicial y final que son ambos iguales a V.
6. De un ejemplo de un ciclo que no sea simple.
R= (1,2,3,1,4,5,1)
7. Defina Grafica Conexa.
R= una gráfica es conexa si dados cualquier...