• Author / Uploaded
• Dchicas Detalles & Algo más

Citation preview

RUTAS COLOMBIA TEORÍA DE GRAFOS _________________________________________________________________ Universidad De Córdoba Ingeniería De Sistemas José Caro Muentes – Cejer Chica Vargas

Ingeniería de Sistemas - UNICOR 1. A partir de uno de los grafos generados en el “Taller No. 4 - Rutas Colombia” defina y aplique los siguientes conceptos. Justifique su propuesta. a) Subgrafo b) Subgrafo cobertor c) vértices-disyuntos d) aristas-disyuntos e) Supresión de vértice f) Supresión de aristas

•

Tabla de Referencia Para El Grafo 1. Montería. 2. Cerete. 3. Lorica. 4. San Antero. 5. Tolú Viejo. 6. Ciénaga De Oro. 7. Sahagún. 8. Sampues. 9. Sincelejo. 10. Mocajan. 11. p San Onofre. 12. María la Baja. 13. Cruz del Vizo. 14. Corozal. 15. Ovejas. 16. Carmen de bolívar 17. San Juancito 18. Arjona 19. Cartagena. 20. Santa Catalina. 21. Loma de Arena. 22. Luruaco. 23. Sabana Larga

24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45.

Baranoa. Piojo El Vaiven. Galapa. Soledad. Barranquilla. Tubara. Santa Verónica. Carretal Puerto Colombia. Arrollo Grande. La Boquilla. Turbana. Plato Nueva Granada. Bosconia. Mariangola. Valledupar. Ciénaga Magdalena. Palmor. Fundación. Ariguaní.

Para la solución de este punto tendremos en cuenta el siguiente grafo

pág. 2

Ingeniería de Sistemas - UNICOR

pág. 3

Ingeniería de Sistemas - UNICOR a) Sub grafo: Un grafo H es un Subgrafo de un grafo G si V(H) están incluidos en V(G) y E(H) están incluidos en E(G).

Subgrafo W1

pág. 4

Ingeniería de Sistemas - UNICOR b) Subgrafo cobertor: Un Subgrafo W de G se dice recubridor, cobertor o generador si V(H)=V(G).

Subgrafo W2

pág. 5

Ingeniería de Sistemas - UNICOR c) vértices-disyuntos: Dados un grafo G, dos subgrafos de G son de vértices disyuntos si no tienen vértices (y por lo tanto aristas) en común.

Subgrafo W3

Subgrafo W4

d) Aristas Disyuntos: Dado un grafo G de dice que dos o más subgrafos de G son de aristas disyuntas sino tienen aristas en común

Grafo W5

Grafo W6

pág. 6

Ingeniería de Sistemas - UNICOR e) Supresión de vértice: el grafo de suprecion de vertive de G se denota como G – {v}. este se obtine supriminedo de G un vertice de v y todas las aritas que incidan en el mismo.

Grafo W7

pág. 7

Ingeniería de Sistemas - UNICOR f) Supresión de aristas: si G = (V , E) con almenos una arista, entonces la suprecion de aristas de subgrafos obtenida de G se denota G - {e} donde se elimina la arista e pero no los vertices incidentes en ella.

Grafo W8

2. Tome los grafos generados en la Parte 1 y teniendo en cuenta los conceptos estudiados, realice las operaciones de listan a continuación. Justifique su propuesta. a) Unión b) Intersección c) Fusión de vértices d) Adición de una arista pág. 8

Ingeniería de Sistemas - UNICOR Solución. a) Unión: La unión de los subgrafos G, G1 y G2, es otro Subgrafo G3 = (V3, A3, f G3) de G talque V3=V1 U V2, A3 =A1 U A2 y FG3 asigna a toda arista de A3 Un par de vértices de V3.

Grafo W1

Grafo W3

pág. 9

Ingeniería de Sistemas - UNICOR

Grafo W9 = W1 U W3 b) Intersección: Sean 𝑉1 ∩ 𝑉2 ≠ 0 la intersección de los subgrafos G1 y G2, G1 ∩ G2, es otro Subgrafo G4 = (𝑉4,4, 𝑓G4) de G, tal que 𝑉4 = 𝑉1 ∩ 𝑉2, 𝐴4 = 𝐴1 ∩ 𝐴2 y FG4 asigna a toda arista de A4 un par de vértices de V4.

Grafo W4

Grafo W5

pág. 10

Ingeniería de Sistemas - UNICOR

Grafo W10 = W4 ∩ W5

c) Fusión de vértices: Un par de vértices a y b de un grafo G se dice que ha sido Fusionados, si los vértices son remplazados por un nuevo vértice, tal que toda arista incidente en a o en b, o en ambos es Incidente en el nuevo vértice.

Subgrafo W3 sin fusión.

pág. 11

Ingeniería de Sistemas - UNICOR

pág. 12

Ingeniería de Sistemas - UNICOR Grafo con Fusión

d) Adición de una arista: Sea G = (V, A, f) un grafo y 𝑢 𝑦 𝑣 dos vértices de G. El grafo G+𝑎, donde (𝑎) = 𝑢𝑣 denota el grafo cuyo conjunto de vértices es V(G) y cuyo conjunto de aristas es 𝐴(G) 𝑈 {𝑎} esta operación se llama adición de una arista a. Claramente G es un Subgrafo de G+a

Grafo W5

Grafo W5 + a pág. 13