Grafos

Universidad "Fermín Toro"

Vice-rectorado Académico

Escuela de Computación























Ejercicios Propuestos



















Estudiante:Asignatura:

Estructuras Discretas II

Cabudare, Junio 2012

Ejercicios Propuestos



Dado el siguiente grafo, encontrar:

[pic]







a.- Matriz de Adyacencia:

|0 |1|1 |1 |0 |0 |1 |1 |
|1 |0 |1 |0 |1 |1 |0 |1 |
|1 |1 |0 |1 |1 |1 |1 |0 |
|1 |0|1 |0 |0 |1 |1 |0 |
|0 |1 |1 |0 |0 |1 |0 |1 |
|0 |1 |1 |1 |1 |0 |1 |1 |
|1|0 |1 |1 |0 |1 |0 |1 |
|1 |1 |0 |0 |1 |1 |1 |0 |





ma (G):









|A1 |1 |1 |0 |0|0 |
|0 |0 |1 |1 |0 |1 |
|0 |0 |0 |1 |1 |0 |
|1 |0 |0 |0 |0 |1 |
|0 |1 |0 |1 |0|1 |
|0 |0 |0 |0 |1 |0 |


mc=






b.- Es simple? Explique:
Si, ya que no tiene lazos ni aristas paralelas.

c.- Encontrar una cadena no simplede no elemental de grado 5:
V2, a2, V3, a7, V5, a10, V2, a2, V3, a8, V4, a12, v6.

d.- Encontrar un ciclo simple:
V1, a5, V3, a7, V5, a10, V2, a2, V3, a8, V4, a9, V1.




e.- Demostrar si esFuertemente Conexo utilizando la matriz de accesibilidad


|0 |1 |1 |0 |1 |0 |
|0 |0 |1 |1 |0 |1 |
|0 |0 |0 |1 |1 |0 |
|1 |0 |0 |0 |0 |1 ||0 |1 |0 |1 |0 |1 |
|0 |0 |0 |0 |1 |0 |


Mc=








|0 |1 |1 |1 |1 |1 |
|1 |0 |0 |1 |1 |1 |
|1 |1 |0 |1...