Post on 14-Apr-2020
transcript
Deseamos interconectar entre si todos los ordenadores de un edificio
Tres problemas de conexión:
Conectar una serie de ordenadores por pares
Procurar que la distancia por cable entre dos ordenadores sea lo más parecida posible a la distancia física
Interconectar una red de ordenadores tal que entre dos ordenadores no pasemos por muchos nodos intermedios
Grafo G(V,A): consiste en un conjunto de vértices V y un conjunto A de pares no ordenados de vértices (aristas)
A={{x1,x
2},{x
1,x
3},{x
1,x
6},{x
2,x
3},{x
2,x
4},
{x3,x
4},{x
3,x
6},{x
4,x
5},{x
4,x
6},{x
5,x
6}}
x6
x5
x4
x3
x2
x1
V={x1,x
2,x
3,x
4,x
5,x
6}
{x3,x6}={x6,x3}
Tipos de grafos
Multigrafo G(V,A): admite aristas múltiples
A={{x1,x
2},{x
1,x
3},{x
1,x
6},{x
2,x
3},{x
2,x
4},
{x3,x
4},{x
3,x
6},{x
4,x
5},{x
4,x
6},{x
4,x
6},
{x4,x
6},{x
5,x
6}}
x6
x5
x4
x3
x2
x1
V={x1,x
2,x
3,x
4,x
5,x
6}
Tipos de grafos
Seudografo G(V,A): admite aristas múltiples y lazos
A={{x1,x
2},{x
1,x
3},{x
1,x
6},{x
2,x
3},{x
2,x
4},
{x3,x
4},{x
3,x
6},{x
4,x
5},{x
4,x
6},{x
4,x
6},
{x4,x
6},{x
5,x
6},{x
1,x
1},{x
1,x
1},{x
5,x
5}}
x6
x5
x4
x3
x2
x1
V={x1,x
2,x
3,x
4,x
5,x
6}
Tipos de grafos
x5
x4
x3
x2
x1
V={x1,x
2,x
3,x
4,x
5}
A={(x1,x
2),(x
1,x
3),(x
1,x
4),(x
1,x
5),(x
3,x
2),
(x4,x
3),(x
5,x
3),(x
5,x
4)}
Grafo dirigido o digrafo G(V,A): consiste en un conjunto de vértices V y un conjunto A de pares ordenados de vértices
Tipos de grafos
),(),( 3553 xxxx
Grafo ponderado G(V,A): las aristas (y/o vértices) tienen asignado un número (que se denomina peso)
V={x1,x
2,x
3,x
4,x
5,x
6,x
7}
A={{x1,x
2},{x
1,x
5},{x
1,x
6},{x
2,x
3},{x
2,x
6},
{x2,x
7},{x
3,x
6},{x
4,x
5},{x
4,x
6},{x
4,x
7},
{x5,x
6}{x
6,x
7}}
x2
4
x5
5
3
4 5
4
x6
6
2
3
x4
x3
x1
x7
1 7
3
Tipos de grafos
A={{x1,x
2},{x
1,x
3},{x
1,x
6},{x
2,x
3},{x
2,x
4},
{x3,x
4},{x
3,x
6},{x
4,x
5},{x
4,x
6},{x
5,x
6}}
x6
x5
x4
x3
x2
x1
V={x1,x
2,x
3,x
4,x
5,x
6}
La entrada (i,j) vale 1 sólo si existe la arista {xi,xj}
Listas de adyacencia
Matriz de adyacencia
Representaciones de grafos
Realización gráfica
011101
101000
110110
101011
001101
100110
Adj
x6
x3
Se trata de una matriz binaria simétrica con diagonal de 0s
A={{x1,x
2},{x
1,x
3},{x
1,x
6},{x
2,x
3},{x
2,x
4},
{x3,x
4},{x
3,x
6},{x
4,x
5},{x
4,x
6},{x
5,x
6}}
x6
x5
x4
x3
x2
x1
V={x1,x
2,x
3,x
4,x
5,x
6}
δ(x1)=3, δ(x2)=3, δ(x3)=4, δ(x4)=4, δ(x5)=2, δ(x6)=4
Lista de grados
La valencia de un vértice es el número δ(x) de aristas en él incidentes
La lista de grados de un grafo consiste en la lista de las valencias de sus vértices. Con normalidad, se toma ordenada de mayor a menor.
Lista de grados: (4,4,4,3,3,2)
x6
x5
x4
x3
x2
x1
δ(x1)=3, δ(x2)=3, δ(x3)=4, δ(x4)=4, δ(x5)=2, δ(x6)=4
Lema del apretón de manos
En todo grafo, la suma de las valencias de los vértices totaliza el doble del número de aristas
Lista de grados: (4,4,4,3,3,2)
axxxVx
v 2)()()( 1
=20: debe haber 10 aristas
12345678910
Subgrafos
Un subgrafo de un grafo G(V,A) consiste en un grafo H(W,B) conWV y B A.
El subgrafo inducido por un conjunto de vértices S consiste en el mayor subgrafo de G que tiene por vértices el conjunto S.
El subgrafo inducido por un conjunto de aristas X consiste en el subgrafo de G que conforman las aristas de X y sus extremos.
x3
x2
x1
x5
x6
F
x3
x2
x1
x5
x6
J
Algunos grafos notables
Grafos r-regulares
K4: 3-regular
Grafo 3-regular
x6x
7
x2
x3 x
8
x9
x10
x12 x
14
x13
x1
x4
x11
x5
Algunos grafos notables
Grafos bipartitos
x6
x5
x4
x3
x2
x1 x
3
x5
x6
x4
x2
x1
C6
Grafos bipartitos completos Km,n
x5
x3
x1 x
2
x4
x5
x3
x1 x
2
x4
x6
K3,2 K3,3
G
b
cd
e
f
g
hi
jx e y están conectados
(a,b,g,f,a,e,j,f,g,b,c)
Caminos G=(V,A) un grafo
x,yV dos vértices camino (de x a y)
(x = x0, x1, x2, ..., xm-1, xm = y)xi V, {xi-1,xi} A
a
k(G): conectividad ó índice de vértice conexión. Indicael menor número de vértices cuya eliminacióndesconecta el grafo (o lo convierte en trivial, en elcaso de grafos completos) . Estos vértices reciben elnombre de conjunto de vértices de corte. Un grafo Ges n-conexo si k(G)≥n.
Conexión
x6
x7
x4
x1
x3
x2
x5
af
e
g
hi
dcb
d es un vértice de corte: G -d es disconexo
k-conexión en grafos G=(V,A) un grafo conexo
G=(V,A) un grafo conexo
{g,c} conforma una pareja de corte: G - {g,c} es disconexo
a
f
e
g
hi
d
c
b
k-conexión en grafos
Se trata de un grafo 2-conexo no 3-conexo
k(G)=2
a
e
d c
b
j
f
g
h
i
G=(V,A) un grafo conexo
a
e
d c
b
j
f
g
h
i
k-conexión en grafos
Dos caminos entre dos vértices u,vV se dice que son disjuntos porvértices si los únicos vértices que tienen en común son u y v.
(a,e,c)
(a,d,b,c)
Teorema de Whitney: Un grafo es k-conexo si y sólo si todo par devértices del grafo está conectado por al menos k caminos disjuntos porvértices.
G=(V,A) un grafo conexo
a
e
d c
b
j
f
g
h
i
k-conexión en grafos
Teorema de Menger: Un grafo es k-conexo por aristas si y sólo si todopar de vértices del grafo está conectado por al menos k caminos disjuntos poraristas.
ka(G)≥3
Árbol
Un grafo T=(V,A) es un árbol si
Es conexo
No contiene ciclos
Un grafo G=(V,A) que no contiene ciclos se llama bosque.
Cada componente conexa de un bosque es un árbol.
Caracterización
Las siguientes afirmaciones son equivalentes:
1. T(V,A) es un árbol
2. Dos vértices cualesquiera de T están conectados por un
único camino.
3. T es conexo y la eliminación de cualquiera de sus aristas
produce un bosque de dos árboles.
4. T es conexo y |A| = |V|-1.
5. T es acíclico y |A| = |V|-1.
Hay dos métodos sistemáticos paraobtener árboles (bosques) recubridores:
Árboles recubridores
Consiste en recorrer el grafo a partir de un vértice, de manera que no setoma ninguna bifurcación hasta agotar el camino en curso. Llegado elcaso, se retrocede hasta la primera bifurcación, y se sigue elprocedimiento.
Búsqueda en profundidad (DFS):
Búsqueda en anchura (BFS):
Consiste en recorrer el grafo a partir de un vértice, de manera que uno seexpande lo máximo posible desde cada vértice que visita, considerandotodos los vértices adyacentes, y así sucesivamente.
Grafos planos
Una representación gráfica de un grafo en una superficie S (por ejemplo elplano) se dice que es una inmersión en S si dos aristas no se cortan enpuntos que no sean vértices del grafo.
Inmersión en el plano
Un grafo se dice que es un grafo plano si admite una inmersión en el plano.
Grafos planos
Fórmula de Euler: Si G=(V,A) es un grafo plano conexo, con c caras, a aristas y vvértices: v + c = a + 2
Tests de planaridad
Se llama subdivisión de un grafo G=(V,A) a un nuevo grafo G’ obtenido alsubdividir alguna(s) arista(s) de G, mediante la inserción de nuevo(s) vértice(s).
Teorema de Kuratowski: Un grafo es plano si, y sólo si, no contiene ningúnsubgrafo isomorfo a K5 ni a K3,3, ni a subdivisiones de ellos.
Los vértices no se pueden insertar en cruces