EstructuraDeDatos2 Clase10

Estructura de Datos 2
Estructuras de datos avanzadas

Contenido







Introducción
Grafos
Transiciones
Tipos
Recorridos
Implementaciones de grafos

Introducción

Introducción


La teoría de grafos tiene un inicio preciso
Un artículo publicado en 1736 por el
matemático Suizo Leonhard Euler
(1707-1783)
◼ La idea principal en que se apoya su trabajo
surgió de un problema conocido comolos
siete puntes de Königsberg
◼



Euler desarrolló algunos de los conceptos
fundamentales de la teoría de grafos.

Introducción

Los 7 puentes de Königsberg






Durante el siglo XVIII, la ciudad de
Königsberg (en Prusia Oriental) estaba
dividida en cuatro zonas por el río Pregel.
Siete puentes comunicaban estas
regiones.
Se decía que los habitantes hacían
paseos dominicales tratando deencontrar
una forma de caminar por la ciudad
cruzando cada puentes exactamente una
vez y regresando al punto de donde se
había iniciado el paseo.

Introducción

Los 7 puentes

Introducción

El problema de Königsberg


Con el fin de determinar si existía o no
dicho circuito, Euler representó las cuatro
zonas de la ciudad y los siete puentes con
un grafo.
a

b

d

c

Introducción

La solución deKönigsberg




Euler encontró las condiciones que debía
cumplir cualquier grafo para que exista
un recorrido con las características
planteadas.
Demostró entonces que no existe el
recorrido buscado para los 7 puentes de
Königsberg.

Grafos

Grafos

Grafo dirigido


Sea V un conjunto finito no vacío, y sea
A ⊆ V x V.



El par (V, A) es un grafo dirigido (sobre V)
V es el conjunto de vértices, onodos.
◼ A es su conjunto de aristas.
◼




G = (V, A)
A es un conjunto de pares ordenados.

Grafos

Grafo no dirigido




Cuando no importa la dirección de las
aristas, la estructura G = (V, A) es un
grafo no dirigido.
A es ahora un conjunto de pares no
ordenados sobre V.

Grafos

Representación




Los vértices se representan gráficamente
con puntos
Las aristas pueden ser
Flechas (aristasdirigidas) conectando dos
vértices.
◼ Líneas (aristas no dirigidas) conectando dos
vértices.
◼

Grafos

Ejemplos y usos


Permiten representar mapas de
interrelación de datos
Carreteras
◼ Cañerías
◼ Circuitos eléctricos
◼ Diagrama de dependencia
◼ etc.
◼

Grafos

Ejemplo
G

v2

a5
a7

a9

v9

a8

a10
v3

v11

v8

v1
a6
a3

v4

a4
v6

a1
a2
v7

V10

G=(V; A)
V = { v1; v2; v3; v4; v5;
v6; v7;v8; v9; v10;
v11 }
A = { a1; a2; a3; a4; a5;
a6; a7; a8; a9; a10 }
a1 = (v8 , v10)
a2 = (v10 , v8)
a3 = (v7 , v8)
a4 = (v6 , v7)
a5 = (v9 , v9)
a6 = (v4 , v3)
a7 = (v2 , v3)
a8 = (v3 , v2)
a9 = (v2 , v1)
a10 = (v9 , v8)

Grafos

Definiciones sobre vértices


Vértice aislado
◼



Vértice ponderado
◼



sin relación (mediante aristas) con otro
vértice

A los vértices se les puede asociar un valorrepresentativo

Peso de un vértice
◼

es el valor asociado a un vértice ponderada

Grafos

Definiciones sobre aristas


Lazo
◼



Arista ponderada
◼



arista cuyo vértice origen y destino coincide.

A las aristas aristas se les puede asociar un
valor representativo de la relación que
representan

Peso de una arista
◼

es el valor asociado a una arista ponderada

Grafos

Incidencia
Incidencia (v)
◼



Incidencia de entrada (v)
◼



conjunto de aristas finalizadas / comenzadas
en v

conjunto de aristas dirigidas finalizadas en v

Incidencia de salida (v)
◼

conjunto de aristas dirigidas comenzadas en
v

Grafos

Adyacencia


Vértices adyacentes
◼



Adyacencia (v)
◼



conjunto de vértices relacionados con v.

Adyacencia de entrada (v)
◼



v y w son adyacentes si estánrelacionados

vértices iniciales de la incidencia de entrada
(v).

Adyacencia de salida (v)
◼

vértices finales de la incidencia de salida (v).

Grafos

Características de un vértice


Grado (v)
◼



Grado de Entrada (v)
◼



cantidad de ocurrencias de v en el conjunto
de aristas.

cantidad de aristas dirigidas finalizadas en v.

Grado de Salida (v)
◼

cantidad de aristas dirigidas comenzadas en...