EJERCICIO DE GRAFOS

1. Construye un grafo dígrafo D no simple con al menos 5 nodos

2. Calcula G(D).

3. Calcula un subgrafo de G(D) bipartido. Es completo? Podrías construir un grafo bipartido y completo?

No es completo.No se puede construir, faltaría la arista {v1,v4} en G(D)

3. Calcula el subgrafo generado por uno de sus vértices. Es bipartido? Es eso una propiedad general para todo subgrafo estrellado? Por qué?

Siempre será bipartido porque el subgrafo está dividido en dos grupos de vértices: del que parten las aristas y el de el resto de aristas. al ser estrellado no hay aristas entre los vértices del segundo grupo, y el primer grupo solo tiene una arista

4. Calcula la matriz de adyacencia de D y de G(D).

( 0 1 0 0 0 0 )
( 1 0 0 0 0 0 )

D = ( 0 1 0 1 0 0 )

( 0 0 0 0 1 0 )
( 0 0 0 1 0 0 )
( 0 0 0 0 1 1 )

( 0 1 0 0 0 0 )
( 1 0 1 0 0 0 )
G= ( 0 1 0 1 0 0 )
( 0 0 1 0 1 0 )
( 0 0 0 1 0 1 )
( 0 0 0 0 1 1 )

5. Calcula el mayor grafo simple asociado a G(D)

6. Es posible construir un camino simple con 6 nodos en un grafo de 5 nodos? Si lo es, construye uno para G(D). Si no, explica por qué no.

Es posible, depende del número de aristas, no de nodos, estos pueden repetirse mientras no se tome dos veces la misma arista

v1 a1 v2 a3 v3 a4 v4 a5 v5 a7 v6 a8 v6

7. Extrae un camino elemental de tamaño 3 de G(D)

v1 a1 v2 a3 v3 a4 v4

8. Extrae un camino simple no elemental y cerrado de G(D).

v1 a1 v2 a2 v1