• Author / Uploaded
• Manuel Bautista Fletes

Citation preview

MATEMATICAS DISCRETAS PAGINA 336

MANUEL BAUTISTA FLETES

1. ¿Qué es una trayectoria? Línea descrita o recorrido que sigue alguien o algo al desplazarse de un punto a otro. 2. ¿Qué es una trayectoria simple? Sí una trayectoria o camino de vi a vj no tiene vértices repetidos, se llama trayectoria simple. 4. ¿Qué es un ciclo? Es un grafo que se asemeja a un polígono de n lados. Consiste en un camino cerrado en el que no se repite ningún vértice a excepción del primero que aparece dos veces como principio y fin del camino. 5. ¿Qué es un ciclo simple? Un ciclo simple es un ciclo que tiene como longitud al menos 3 y en el que el vértice inicial coincide con el vértice final. 7. Defina gráfica conexa. Una gráfica conexa es una gráfica en la que se puede ir de cualquier vértice a cualquier otro vértice por una trayectoria. A continuación se da la definición formal. 15. Defina grado de un vértice v. El grado de un vértice v, δ(v), es el número de aristas que inciden en v. (Por definición, cada ciclo sobre v contribuye con 2 al grado de v). 16. ¿Qué es un ciclo de Euler? Un ciclo euleriano pasa por todas las aristas exactamente una vez, regresando al punto de partida.

C

TS TS

C CS

TS TS 10. Seis vértices cada uno de grado 3

TS

CS

12. Cuatro vértices cada uno de grado 1 NO SE PUEDE PUESTO QUE PARA CONECTARSE SE CONVIERTEN EN GRADO 2 O MAS 14. Cuatro aristas; cuatro vértices de grados 1, 2, 3, 4

16. Gráfica simple; seis vértices con grados 1, 2, 3, 4, 5, 5

18. Gráfica simple; cinco vértices con grados 2, 2, 4, 4, 4

Encuentre el grado de cada vértice para las siguientes gráficas.

En los ejercicios 28 al 33, decida si las gráficas tienen un ciclo de Euler. Si lo tienen, muestre uno.

PAGINA 345 1. ¿Qué es un ciclo hamiltoniano?´ Un ciclo hamiltoniano pasa por todos los vértices exactamente una vez, regresando al punto de partida.

Determine si cada gráfica contiene un ciclo de Hamilton. Si así es, exhiba uno; de otra manera, dé un argumento para demostrar que no hay un ciclo de Hamilton.

PAGINA 355 1. ¿Qué es una matriz de adyacencia?

2. ¿Qué es una matriz de incidencia?

En los ejercicios 7 al 12, escriba la matriz de incidencia de cada gráfica. 7. La gráfica del ejercicio 1 8. La gráfica del ejercicio 2 9. La gráfica del ejercicio 3