Ppt4

´
Notaciones b´
asicas y definiciones Recorrido de Grafos Arboles
de Cobertura M´ınima

Dise˜no de Algoritmos
Clase 4: Grafos I
Carlos Contreras Bolton
Universidad Andr´
es Bello

3 de Abril de 2014

Carlos Contreras Bolton — Dise˜
no de Algoritmos

1/35

´
Notaciones b´
asicas y definiciones Recorrido de Grafos Arboles
de Cobertura M´ınima

Tabla de Contenidos
1 Notaciones b´
asicas ydefiniciones

Introducci´on
Otros conceptos importantes
Representaci´on de Grafos
2 Recorrido de Grafos

B´usqueda primero en profundidad
B´usqueda primero en anchura
´
3 Arboles
de Cobertura M´ınima
Definici´on
Algoritmo de Kruskal
Algoritmo de Prim

Carlos Contreras Bolton — Dise˜
no de Algoritmos

2/35

´
Notaciones b´
asicas y definiciones Recorrido de Grafos Arboles
de Cobertura M´ınimaIntroducci´on
A pesar de que la primera publicaci´on relacionada con la
teor´ıa de grafos se remonta a 1736 por Leonhard Euler al
problema de los puentes de K¨onigsberg, y de que varios
resultados importantes en tal teor´ıa se obtuvieron en el
siglo XIX, entre 1920 y 1930 se afianz´o, extendi´o e
intensific´o el inter´es por la teor´ıa de grafos.
El problema de los puentes de K¨onigsberg consist´ıa enencontrar un camino que recorriera los siete puentes del
r´ıo Pregel en la ciudad de K¨onigsberg, actualmente
Kaliningrado, de modo que se recorrieran todos los
puentes pasando una sola vez por cada uno de ellos.

Carlos Contreras Bolton — Dise˜
no de Algoritmos

3/35

´
Notaciones b´
asicas y definiciones Recorrido de Grafos Arboles
de Cobertura M´ınima

Introducci´on

El primer texto apareci´o en 1936escrito por K¨onig.
El t´ermino “grafo”, proviene de la expresi´on graphic
notation usada por primera vez por Frankland y
posteriormente adoptada por Alexander Crum Brown en
1884, y hac´ıa referencia a la representaci´on gr´afica de los
enlaces entre los ´atomos de una mol´ecula.
Su inter´es se debe a su aplicabilidad en muchos campos
como ciencias de la computaci´on, qu´ımica, investigaci´on
deoperaciones, ingenier´ıa el´ectrica, ling¨u´ıstica y
econom´ıa.

Carlos Contreras Bolton — Dise˜
no de Algoritmos

4/35

´
Notaciones b´
asicas y definiciones Recorrido de Grafos Arboles
de Cobertura M´ınima

Definici´on
Los grafos son estructuras discretas que constan de v´ertices y
aristas que conectan estos v´ertices. Hay diferentes tipos de
grafos que difieren en la clase y n´umero de aristasque
conectan un par de v´ertices.
´n
Definicio
Un grafo G es un par ordenado G = (V, E) formado por un
conjunto finito de v´ertices V y un conjunto E de pares no
ordenados de v´ertices distintos, es decir,
E ⊂ {{u, v}|u, v ∈ V ∧ u = v}
A los elementos de E se les denomina aristas o arcos.

Carlos Contreras Bolton — Dise˜
no de Algoritmos

5/35

´
Notaciones b´
asicas y definiciones Recorrido deGrafos Arboles
de Cobertura M´ınima

Grafo dirigido y no dirigido
´n
Definicio
Un grafo dirigido es un par ordenado (V, E) donde V es un
conjunto finito y E ⊂ (V × V ) − , siendo
= {(x, x) : x ∈ V }.

´n
Definicio
Un grafo no dirigido es un par ordenado (V, E) formado por
un conjunto finito de v´ertices V y una familia finita E de
aristas no orientadas E = {ei }i∈I donde I es un conjunto
finito y∀i ∈ I se verifica que ei = {ui , vi } con ui , vi ∈ V.
En un grafo no dirigido, dos aristas distintas pueden conectar los
mismos v´ertices, esto es, que E es una familia y no un conjunto,
pudiendo tener elementos repetidos, en otras palabras se permite
aristas del tipo {u, u} denominadas lazos o bucles.
Carlos Contreras Bolton — Dise˜
no de Algoritmos

6/35

´
Notaciones b´
asicas y definicionesRecorrido de Grafos Arboles
de Cobertura M´ınima

Grafo dirigido y no dirigido

Carlos Contreras Bolton — Dise˜
no de Algoritmos

7/35

´
Notaciones b´
asicas y definiciones Recorrido de Grafos Arboles
de Cobertura M´ınima

Orden y tama˜no de un grafo
El n´umero de v´ertices de G es |V | = n, el cual es el orden
del grado del grafo G.
El n´umero de aristas |E| = m es el tama˜no del grafo G.
Se...