Grafos python

Introducci´on a la teor´ıa de grafos

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...