SLIDES - Tecnología Digital V Diseño de Algoritmos (6)

Vista previa del material en texto

INTRODUCCIóN A LA TEORíA DE GRAFOS
Tecnología Digital V: Diseño de Algoritmos
Universidad Torcuato Di Tella
Definiciones
Definición
Un grafo es un par � = (+, �) tal que ...
1. + es un conjunto finito (llamado el conjunto de vértices de �), y
2. � ⊆ {8 9 ∈ + ×+ : 8 ≠ 9} es un conjunto de aristas.
1
3
2 4
6
5
7
# En este ejemplo, + = {1, . . . , 7} y
� = {12, 13, 23, 24, 34, 36, 45, 47, 56, 57, 67}.
1
Definiciones
1
3
2 4
6
5
7
# El orden de los extremos de una arista no es importante. Nos referimos
indistintamente a la arista 34 como 43 o bien {3, 4}.
Definiciones
1. Si 8 9 ∈ �, decimos que los vértices 8 y 9 son vecinos.
2. Dado 8 ∈ + , definimos el vecindario de 8 como #(8) = { 9 ∈ + : 8 9 ∈ �}.
3. El grado de un vértice 8 ∈ + es 3(8) = |#(8)|.
2
Motivación (1/6)
Red vial I
Representamos con grafos un mapa de rutas entre un grupo de ciudades
(los vértices representan las ciudades y los cruces de caminos).
3
Motivación (2/6)
Red vial II
Cambiando la interpretación, con grafos podemos representar mapas de
ciudades (los vértices representan las esquinas!).
4
Motivación (3/6)
Red de transporte
Podemos representar una red de transporte con grafos (los vértices
representan las estaciones/paradas).
5
Motivación (4/6)
Redes sociales
Podemos representar relaciones entre usuarios de una red social (los
vértices representan los usuarios).
6
Motivación (5/6)
Conflictos de horarios
Cursos a dictar y superposiciones entre cursos (dos vértices son vecinos si
sus cursos se solapan).
7
Motivación (6/6)
Conflictos espaciales
Antenas en una red de telefonía celular (dos vértices son vecinos si sus
antenas tienen áreas de cobertura superpuestas).
8
Definiciones
1
3
2 4
6
5
7
Definiciones
# Un camino entre dos vértices 8 y 9 es una secuencia de aristas desde 8
hasta 9.
# La distancia entre dos vértices es la cantidad de aristas del camino más
corto entre ellos.
# Un grafo es conexo si existe un camino entre todo par de vértices.
9
Definiciones
1
3
2 4
6
5
7
Definiciones
# Una componente conexa es un subconjunto de vértices conexo, maximal
con esta propiedad.
# Un vértice aislado es un vértice 8 con 3(8) = 0 (que conforma una
componente conexa de tamaño 1).
1. Un grafo conexo tiene exactamente una componente conexa.
2. Si 8 y 9 están en componentes conexas distintas, decimos que hay una
distancia infinita entre ellos.
10
Representación de grafos
# Nos interesa programar algoritmos que trabajen sobre grafos. Para esto,
debemos representar adecuadamente grafos en C++ (cómo lo hacemos?).
Definición
La matriz de adyacencia de un grafo � es una matriz � = (08 9) ∈ ℝ|+ |×|+ | tal
que 08 9 = 1 si 8 9 ∈ � y 08 9 = 0 en caso contrario.
1
3
2 4
6
5
7
� =
©­­­­­­­­­«
0 1 1 0 0 0 0
1 0 1 1 0 0 0
1 1 0 1 0 1 0
0 1 1 0 1 0 1
0 0 0 1 0 1 1
0 0 1 0 1 0 1
0 0 0 1 1 1 0
ª®®®®®®®®®¬
11
Representación de grafos
c l a s s Grafo
{
publ ic :
Grafo ( i n t n ) ;
~Grafo ( ) ;
void agregarAr is ta ( i n t i , i n t j ) ;
void e l iminarAr i s t a ( i n t i , i n t j ) ;
bool e x i s t eA r i s t a ( i n t i , i n t j ) ;
p r iva te :
i n t _v e r t i c e s ;
bool∗∗ _adj ;
}
12
Representación de grafos
// Constructor
Grafo : : Grafo ( i n t n )
{
_v e r t i c e s = n ;
_adj = new bool ∗ [n ] ;
f o r ( i n t i =0 ; i <n ; ++ i )
_adj [ i ] = new bool [n ] ;
}
// Destructor
Grafo : : ~ Grafo ( )
{
fo r ( i n t i =0 ; i < _ve r t i c e s ; ++ i )
de l e t e [ ] _adj [ i ] ;
de l e t e [ ] _adj ;
}
13
Representación de grafos
// Agrega una a r i s t a
void Grafo : : agregarAr is ta ( i n t i , i n t j )
{
_adj [ i ] [ j ] = _adj [ j ] [ i ] = t rue ;
}
// Elimina una a r i s t a
void Grafo : : e l iminarAr i s t a ( i n t i , i n t j )
{
_adj [ i ] [ j ] = _adj [ j ] [ i ] = f a l s e ;
}
// Consulta por a r i s t a
bool Grafo : : e x i s t eA r i s t a ( i n t i , i n t j )
{
re turn _adj [ i ] [ j ] ;
}
14
Representación de grafos
# Ventajas de esta representación:
1. Agregar una arista: $(1).
2. Eliminar una arista: $(1).
3. Consultar si existe arista: $(1).
# Desventajas de esta representación:
1. Agregar un vértice: $(=2).
2. Eliminar un vértice: $(=2).
3. Obtener todos los vecinos de un vértice: $(=).
15
Representación de grafos
Definición.
La matriz de incidencia de un grafo � es una matriz" = (<8 9) ∈ ℝ|+ |×|� | tal
que <84 = 1 si el vértice 8 es uno de los extremos de la arista 4, y <84 = 0 en
caso contrario.
# En nuestro ejemplo, � = {12, 13, 23, 24, 34, 36, 45, 47, 56, 57, 67}.
" =
©­­­­­­­­­«
1 1 0 0 0 0 0 0 0 0 0
1 0 1 1 0 0 0 0 0 0 0
0 1 1 0 1 1 0 0 0 0 0
0 0 0 1 1 0 1 1 0 0 0
0 0 0 0 0 0 1 0 1 1 0
0 0 0 0 0 1 0 0 1 0 1
0 0 0 0 0 0 0 1 0 1 1
ª®®®®®®®®®¬
# Es una representación conveniente?
16
Representación de grafos
# Una tercera opción es por medio de listas/conjuntos de vecinos
asociados con cada vértice:
1
3
2 4
6
5
7 1 → {2, 3}
2 → {1, 3, 4}
3 → {1, 2, 4, 6}
4 → {2, 3, 5, 7}
5 → {4, 6, 7}
6 → {3, 5, 7}
7 → {4, 5, 6}
17
Representación de grafos
c l a s s Grafo
{
. . .
p r iva te :
vector < set <int > > _vecinos ;
}
// Constructor
Grafo : : Grafo ( i n t n )
{
fo r ( i n t i =0 ; i <n ; ++ i )
_vecinos . push_back ( set <int > ( ) ) ;
}
18
Representación de grafos
// Agrega una a r i s t a
void Grafo : : agregarAr is ta ( i n t i , i n t j )
{
_vecinos . a t ( i ) . i n s e r t ( j ) ;
_vecinos . a t ( j ) . i n s e r t ( i ) ;
}
// Elimina una a r i s t a
void Grafo : : e l iminarAr i s t a ( i n t i , i n t j )
{
_vecinos . a t ( i ) . e rase ( j ) ;
_vecinos . a t ( j ) . e rase ( i ) ;
}
// Consulta por a r i s t a
bool Grafo : : e x i s t eA r i s t a ( i n t i , i n t j )
{
re turn _vecinos . a t ( i ) . f ind ( j ) != _vecinos . a t ( i ) . end ( ) ;
} 19
Representación de grafos
# Ventajas de esta representación:
1. Obtener todos los vecinos de un vértice: $(1).
2. Agregar un vértice: $(=).
# Desventajas de esta representación:
1. Agregar una arista: $(log =) (depende de la implementación de set).
2. Eliminar una arista: $(log =).
3. Consultar si existe arista: $(log =).
4. Eliminar un vértice: $(=).
20
Grafos dirigidos
Definición
Un grafo dirigido (o digrafo) es un par � = (#, �) tal que ...
1. # es un conjunto finito (llamado el conjunto de nodos de �), y
2. � ⊆ {(8 , 9) ∈ + ×+ : 8 ≠ 9} es un conjunto de pares ordenados, llamados
arcos.
1
3
2 4
6
5
# A diferencia de los grafos (no dirigidos), ahora las aristas son pares
ordenados.
21
Definiciones
1
3
2 4
6
5
# Diferenciamos entre el grado de entrada y el grado de salida de cada
nodo.
1. 3−(8) = |#−(8)| = |{ 9 ∈ # : (9 , 8) ∈ �}|.
2. 3+(8) = |#+(8)| = |{ 9 ∈ # : (8 , 9) ∈ �}|.
# Un camino entre dos nodos es una secuencia de arcos entre ellos,
respetando el sentido de los arcos.
22