programacion

GRAFOS

Introducción
• Los grafos son estructuras discretas que constan de

vértices y aristas que conectan entre sí esos vértices.
• Tipos de grafos:
1. Grafo simple
2. Multígrafo
3. Pseudografo

Grafo simple
• Grafo simple que constas de vértices y

aristas no
dirigidas. Cada aristas conecta dos vértices distintos y
no hay dos aristas que conecten un mismo par de
vértices.Multígrafo
• Consta de vértices y aristas no dirigidas entre esos

vértices, pero admitiendo la existencia de aristas
múltiples entre pares de vértices.

Pseudografo
• Consta de vértices y aristas no dirigidas entre esos

vértices, admitiendo bucles (esto es aristas que conectan
vértices consigo mismo ).

Grafo simple, multígrafo y pseudografo
dirigido
• Las aristas de un grafodirigido son pares ordenados. Se

utiliza un punta de flecha para indicar la dirección de la
arista.

Terminología básica
• Se dice que dos vértices u y v de un grafo no dirigido son

adyacentes en G si {u, v} es una arista de G. si e= {u, v},
se dice que la arista e es incidente con los vértices u y v.
Se dice que u y v son extremos de la arista e.

Terminología básica
• El grado deun vértice de un grafo no dirigido es el

numero de aristas incidentes con él, exceptuando los
bucles, cada uno de los cuales contribuye con dos
unidades al grado del vértice. El grado del vértice v se
denota como δ(v).
• A los vértices de grado cero se les llama aislados. Se dice
que el vértice es colgante, o que es una hoja, si, solo si,
tiene grado uno

Terminología básica
• Si (u,v) es un arista del grafo dirigido G, se dice que u es

adyacente a v y que v es adyacente a u. Al vértice u se le
llama vértice inicial de (u, v) y a v se la llama vértice final
de o terminal de (u. v)
• En un grafo dirigido, el grado de entrada de un vértice v,
denotado por δ− 𝑣 es el numero de aristas que tienen a
v como vértice final. El grado de salida de un vértice v,
denotado porδ+ 𝑣 , es el numero de aristas que tienen v
como vértice inicial.

Grafos completos
• Grafos simples que contiene exactamente una aristas

entre cada par de vértices distintos.

Ciclos
• Consta de n vértices 𝑣1 , 𝑣2 , …, 𝑣 𝑛 y aristas {𝑣1 , 𝑣2 }, {𝑣2 ,

𝑣3 }, …, {𝑣 𝑛−1 , 𝑣 𝑛 } y {𝑣 𝑛 , 𝑣1 }.

Ruedas
• Cuando

se añade un vértice adicional al ciclo y
conectamos este nuevo vérticecon cada uno de los n
vértices mediante una nueva arista.

Grafos bipartitos
• Se dice que un grafo simple G es bipartito si su conjunto

de vértices V se puede dividir en dos conjuntos disjuntos
𝑉1 y 𝑉2 , tales que cada arista del grafo conecta a un grafo
de 𝑉1 con un vértice de 𝑉2 .

Grafos definidos a partir de otros

Representación de grafos
Matriz de adyacencia
2. Matriz deincidencia
1.

Matriz de adyacencia

• Siempre

será
una
matriz
cuadrada.

Matriz de incidencia

• 𝑉1 , …, 𝑉5 Aristas
• 𝑒1 , …, 𝑒6 Vertices

Isomorfismo de grafos
• Los grafos simples 𝐺1 = (𝑉1 , 𝐸1 ) y 𝐺1 = (𝑉2 , 𝐸2 ) son

isomorfos si hay una función biyectiva f de 𝑉1 en 𝑉2 con la
propiedad de que, para cada par de vértices u, v
pertenecientes a 𝑉1 , u y v son adyacentes a𝐺1 si, y solo
si, f(u) y f(v) son adyacentes en 𝐺2 . Se dice que esta
función f es un isomorfismo.

8.5 Caminos Eulerianos y Hamiltonianos
Definición 1

Un circuito euleriano de un grafo G es un
circuito simple que contiene a todas la arista
de G.
Un camino euleriano es un camino simple
que contiene a todas las aristas G.

Condiciones necesarias para la
existencia de circuitos ycaminos
Eulerianos
Teorema 1
Un multígrafo conexo contiene un circuito euleriano
si, y solo si, cada uno de sus vértices tiene grado
par.

Teorema 2
Un multígrafo conexo contiene un camino euleriano,
pero no un circuito euleriano si, y solo si, tiene
exactamente dos vértices de grado impar.

Caminos y Circuitos Hamiltonianos
Definición 2

Se dice un camino X0, X1, …, Xn-1, Xn...