Teoria de grafos - Fundamentos basicos

República Bolivariana de Venezuela

Ministerio del Poder Popular para la Defensa

Universidad Nacional Experimental Politécnica de la Fuerza Armada Bolivariana

Núcleo Puerto Cabello – Edo. Carabobo

Teoría de grafos

Docente: Laura Alcalde                                             Bachiller: Mike Espinola

C.I: 27.754.194

Ingeniería de sistemas 5to semestre D1

 1) De un ejemplo de un grafo mixto a través de su gráfica (modelado) que posea cada una de las siguientes propiedades (5 Puntos):

a) 2 bucles (no dirigidos).

b) 2 arcos múltiples (dirigidos)

c) Al menos 4 vértices adyacentes.

d) Al menos 2 arcos adyacentes.

e) 3 vértices aislados.

Además:

f) Determine un subgrafo del grafo original construido por usted y expóngalo a

través de su gráfica (modelado).

Desarrollo:

Grafo mixto

[pic 1]

Subgrafo

[pic 2]

2) Represente cada uno de los siguientes problemas a través de la teoría de grafos. Para ello, muestre su representación:

a) Por Extensión (Conjuntos)

b) Modelado (Gráfica)

c) Matriz de adyacencia (Matriz booleana)

La tarea de geografía

Conjuntos:

G = ({V1, V2, V3, V4, V5, V6, V7, V8, V9, V10, V11, V12, V13, V14, V15, V16, V17, V18, V19, V20, V21, V22, V23, V24, V25, V26, V27, V28, V29}, {(V1,V2), (V1,V3), (V1,V4), (V1,V12), (V2,V4), (V2,V12), (V3,V4), (V3,V5), (V3,V15), (V3,V11), (V3,V6), (V4,V5), (V4,10), (V4,V9), (V4,V8), (V4,V7), (V4,V12), (V5,V10), (V6,V15), (V6,V11), (V6,V21), (V6,V25), (V7,V8), (V7,V19), (V7,V14), (V7,V12), (V8,V9), (V9,V10), (V9,V16), (V9,V19), (V10,V16), (V10,V15), (V11,V15), (V12,V14), (V12,V13), (V12,V25), (V12,V17), (V12,V22), (V12,V27), (V12,V28), (V12,V29), (V12,V26), (V13,V14), (V13,V17), (V13,V18), (V14,V19), (V14,V18), (V15,V16), (V15,V20), (V15,V21), (V16,V19), (V16,V20), (V16,V24), (V17,V18), (V17,V22), (V17,V23), (V17,V26), (V18,V19), (V18,V23), (V19,V24), (V19,V23), (V20,V21), (V20,V24), (V21,V25), (V22,V23), (V22,V26), (V23,V24), (V23,V26), (V24,V25), (V24,V26), (V25,V26), (V25,V27), (V25,V28), (V25,V29), (V26,V27), (V27,V28)})

Modelado

[pic 3]

Matriz de adyacencia

[pic 4]

La casa de campo de los tres hermanos

Modelado

En el siguiente grafico se muestran los vértices que representan las casas de los hermanos y a su vez a los medidores de agua, gas y electricidad.

[pic 5]

Conjuntos:

G = ({V1, V2, V3}, {(V1,V2), (V2,V1), (V2,V3), (V3,V2), (V3,V1), (V1,V3), (V1,V1), (V2,V2), (V3,V3)})

Matriz de adyacencia:

[pic 6]

Gira política del candidato x

En este problema los vértices representan ciudades y las aristas con ponderación representan la longitud del recorrido.

[pic 7]

El problema consiste en pasar por todos los vértices(ciudades), pero buscando un ciclo (ciclo de Hamilton) optimo que ahorre tiempo y recursos. El ciclo más óptimo sería el siguiente:

[pic 8]

Conjuntos:

G = ({V1, V2, V3, V4, V5}, {(V1,V4), (V1,V5), (V1,V3), (V2,V1), (V2,V5), (V2,V4), (V3,V2), (V3,V5), (V4,V3), (V5,V4)})

Matriz de adyacencia:

[pic 9]

...