grafos

Teoría de Grafos

1

Grafo no dirigido


Dados los gráficos G = (V, E) y G’ = (V’, E’)



El grafico complementario Ḡ de G es el grafico simple con el mismo conjunto de
vértices V y lados que unen vértices que no son adyacentes en G.

Ḡ = (V, Ē) donde e ∈ E ⇔ e ∈ Ē

2

Grafo no dirigido



G es llamado completo si G es simple y dos vértices distintos
cualesquiera sonadyacentes.



En notación, Kn es un grafico completo con n vértices

Denotamos G + G’ al grafico G + G’ = (V ∪ V’ , E ∪ E’)
(Tomando multiplicidades en cuenta)


3

Grafo no dirigido

4

Grafo no dirigido

Dado el grafo G= (V, E)
Un grafo G’= (V’, E’) es llamado sub-grafo de G=(V, E) si
•V’ ⊂ V
•E’ ⊂ E

5

Grafo no dirigido

Si E’ contiene todos los lados de Gabarcados por V’, G’
es llamado un sub-grafo inducido por V’
S ⊂ V es llamado estable si dos vértices cualesquiera de S
son no-adyacentes
El sub-grafo inducido por S es sin lados.
C ⊂ V es llamado clique si dos vértices cualesquiera de C
son adyacentes.
El sub-grafo inducido por C es completo







6

Grafo no dirigido

7

Grafo no dirigido

Dado el grafo G= (V, E)
Uncamino en G es una secuencia P= (v0 , e1 ,v1 ,…, ek ,vk )
donde:
•k≥ 0
•v0, v1,…, vk son vértices
•ei es un lado conectando vi-1 y vi (i=1,…, k)
Si v0, v1,… vk son todos distintos, se llama camino simple
El camino P conecta v0 y vk
8

9

Grafo no dirigido

Dado el grafo G= (V,E)
Sean P= (v0, e1 , v1 ,…, ek ,vk ) y Q= (u0, f1, u1 ,…, fl ,ul ) dos
caminos en G
El camino inverso P -1de P se obtiene de P al revertir el
orden de los elementos
P -1 = (vk , ek , vk-1 ,…, e1 ,v0)

10

Grafo no dirigido

Si vk = u0 definimos la concatenación PQ de P y Q por el
camino:
PQ = (v0, e1 , v1 ,…, ek , vk , f1 , u1 ,…, fl, ul )

El camino P es cerrado si vk = v0
El camino cerrado P es llamado circuito si v1 ,…, vk son
todos distintos así como e1 ,…, ek

11

Grafo nodirigido

Dado el grafo G= (V, E)
y P= (v0, e1, v1 ,…, ek, vk) un camino
k es llamada la longitud de P
La longitud mínima de un camino conectando u y v
es llamada la distancia entre u y v.
La distancia máxima entre todos los vértices u, v de
G es llamada el diámetro de G.

12

Grafo no dirigido

U n grafo G = (V, E) se llama conectado si para
cualesquiera dos vértices u y v hay unatrayectoria conectando u y v.
Para cualquier U ⊂ V, denotamos δ(U) = conjunto de
aristas de G conectando U y V-U
Un subconjunto F de E es llamado corte si F = δ (U)
para algunos U ⊂ V

13

Bases
Grafo no dirigido
Un grafo es llamado bosque, si no tiene circuitos
Un árbol es un bosque conectado
Un sub-grafo conectado de un árbol T es llamado un sub-árbol de T
La noción de bosque yárbol de extiende a los subconjuntos de aristas de un grafo
G= (V, E)
Un sub-conjunto F de E es llamado bosque si (V, F) es un bosque
Un sub-conjunto F de E es llamado árbol de expansión si (V, F) es un árbol

14

Grafo no dirigido

•Obtener dos caminos simples de
1a3
•Obtener un camino de 1 a 3 que
no sea simple
•Obtener una camino cerrada

15

Grafo no dirigido







Ungrafo G =(V,E ) es llamado bipartito si V se puede
dividir en dos conjuntos U y W de manera que cada arista
de G conecte U y W
Un grafo G= (V, E) se llama bipartito completo si G es
simple y V puede ser dividido en dos conjuntos U y W de
manera que E contenga todos los pares {u, w} con u ∈ U
y w ∈ W.
Si |U| = m y |W|=n entonces el grafo se denota Km,n

16

Bases
Grafo dirigido

UnGrafo Dirigido es un par G=(V, E) donde V es un
conjunto finito y E es una familia de pares ordenados de
V.
 Los elementos de V se llaman vértices, nodos o puntos.
Denotamos n=|V|


Los elementos de E se llaman arcos o aristas dirigidas.
Denotamos m=|E|




El arco (u ,v) se denota uv
17

Grafo dirigido



Dado un grafo dirigido G = (V,E) y (u,v) un arco de E


...