Grafos python
1
Definiciones
2
Subgrafos
3
Complemento
4
Isomorfismo
Federico Dom´ınguez
Introducci´
on Teor´ıa de Grafos
Dic. 17, 2014
1 / 19
Un grafo dirigido esta compuesto de nodos los cu´ales
estan conectados entre si por aristas.
Un grafo dirigido G sobre V est´a formado por los elementos de V ,
llamados v´ertices o nodos de G , y un subconjunto E de V ×V , conocido
como las aristas (dirigidas) o arcos de G . Si a, b ∈ V y (a, b) ∈ E ,
entonces existe una arista de a a b.
b
(a,b)
a
Federico Dom´ınguez
Introducci´
on Teor´ıa de Grafos
Dic. 17, 2014
2 / 19
Un grafo dirigido a menudo contiene aristas no dirigidas.
Si G es un grafo dirigido y a, b ∈ V , con a = b y (a, b), (b, a) ∈ E ,
entonces se usa la arista u
´nica no dirigida {a, b} ={b, a}. Se dice que a y
b son v´ertices adyacentes.
(a,b)
a
Federico Dom´ınguez
b
b
(b,a)
a
Introducci´
on Teor´ıa de Grafos
Dic. 17, 2014
3 / 19
Los nodos en un grafo dirigido son todos los elementos en
V y las aristas son todos los pares ordenados en E .
Ejemplo
Para V = {1, 2, 3, 4, 5}, el diagrama de abajo es un grafo dirigido G sobre
V con el conjunto de aristas E = {(1, 1), (1, 2),(1, 4), (3, 2)}.
(1,2)
(1,1)
1
2
(1,4)
(3,2)
4
3
5
Federico Dom´ınguez
Introducci´
on Teor´ıa de Grafos
Dic. 17, 2014
4 / 19
Sean x, y v´ertices de un grafo no dirigido G = (V , E ). Un camino x − y
en G es una sucesi´on alternada finita:
x = x0 , e1 , x1 , e2 , x2 , e3 , ..., en−1 , en , xn = y
de v´ertices y aristas de G , que comienza en el v´ertice x y termina en el
v´ertice y yque contiene las n aristas ei = {xi−1 , xi } donde 1 ≤ i ≤ n.
La longitud de un camino es n, el n´
umero de aristas que hay en el camino.
x
e1
w
e2
z
e3
t
e4
y
Si x = y , el camino es cerrado, de lo contrario es abierto.
Federico Dom´ınguez
Introducci´
on Teor´ıa de Grafos
Dic. 17, 2014
5 / 19
Tipos de caminos
Si se tiene un camino x − y en un grafo no dirigido G=(V,E).
No se repitenlas aristas ⇒ recorrido
No se repiten los v´ertices ⇒ camino simple
Recorrido cerrado ⇒ circuito
Camino simple cerrado ⇒ ciclo
Federico Dom´ınguez
Introducci´
on Teor´ıa de Grafos
Dic. 17, 2014
6 / 19
a
e1
e5
c
e3
d
Federico Dom´ınguez
b
e2
e7
e6
e4
e
Introducci´
on Teor´ıa de Grafos
Dic. 17, 2014
7 / 19
En un grafo conexo, existe un camino simple entre
cualesquiera dosv´ertices del grafo.
a
a
a
e1
e1
e5
c
d
b
e2
e3
e1
e5
c
e7
e
Federico Dom´ınguez
b
e2
c
b
e2
e3
e6
e4
e5
d
e4
e
Introducci´
on Teor´ıa de Grafos
d
e4
e
Dic. 17, 2014
8 / 19
Un grafo disconexo esta compuesto por dos o m´as
componentes (partes conexas del grafo).
El n´
umero de componentes de un grafo G se denota con κ(G ).
a
e1
e2
c
d
Federico Dom´ınguez
b
e3
e4
eIntroducci´
on Teor´ıa de Grafos
Dic. 17, 2014
9 / 19
Un grafo G = (V , E ) es un multigrafo si existen
a, b ∈ V , a = b, con dos o m´as aristas.
1
2
3
4
5
Para n ∈ Z+ , un multigrafo es un n-grafo si ninguna de las aristas del
grafo tiene una multiplicidad mayor que n.
Federico Dom´ınguez
Introducci´
on Teor´ıa de Grafos
Dic. 17, 2014
10 / 19
Introducci´on a la teor´ıa de grafos
1Definiciones
2
Subgrafos
3
Complemento
4
Isomorfismo
Federico Dom´ınguez
Introducci´
on Teor´ıa de Grafos
Dic. 17, 2014
11 / 19
Si G = (V , E ) es un grafo, entonces G1 = (V1 , E1 ) es un subgrafo de G si
V1 ⊆ V y E1 ⊆ E , donde cada arista de E1 es incidente con los v´erticese
en V1 .
G
G1
G2
a
a
e1
e5
e1
e5
c
b
e2
e3
a
e1
c
e2
b
e7
e6
e6
e
d
b
e4
e
e
FedericoDom´ınguez
Introducci´
on Teor´ıa de Grafos
Dic. 17, 2014
12 / 19
En un subgrafo recubridor, todos los v´ertices se
mantienen.
Si G = (V , E ) es un grafo, y G1 = (V1 , E1 ) es un subgrafo de G .
Entonces, si V1 = V , G1 es un subgrafo recubridor de G .
G
G1
G2
a
a
a
e1
e1
e5
e5
c
e2
e3
d
b
c
e7
e
Federico Dom´ınguez
c
e3
e6
e4
b
d
b
e3
e4
e
Introducci´
on Teor´ıa de...
Regístrate para leer el documento completo.