1_1_a Conceptos básicos

DEFINICIONES
FUNDAMENTALES
 ¿Qué es un grafo?

◎ Un grafo, es una estructura matemática que permite modelar problemas de la

vida cotidiana, mediante una representación formada por nodos o vértices y
aristas que representan las relaciones o vínculos entre ellos.
 ¿Para que sirven?

◎ Cartografía (coloreado de mapas)

◎ Determinación de tiempos ene el desarrollo de proyectos
◎ Urbanistas (Modelado de rutas, Representación de un mapa)
◎ Programación de horarios (exámenes, eventos, servicios públicos)
◎ Redes de computadora
◎ Circuitos electrónicos
◎ Relaciones de una base de datos
◎ Valoraciones de influencia
◎ Grafos de conocimiento
 Partes de un grafo
◎ Vértice o nodo: Se dibujan con un pequeño circulo y se les asigna un número o
letra.
◎ Aristas (ramas o lados): Son líneas que unen un vértice con otro y se les asigna una
letra, número o combinación de ambos.
◎ Orejas (Bucles o lazos): Arista que incide en un mismo vértice.
◎ Aristas adyacentes: dos aristas son adyacentes si tienen un vértice en común.

◎ Aristas paralelas: dos o aristas que son incidentes con dos vértices iguales.

◎ Vértices adyacentes: son adyacentes si comparten la misma arista.

◎ Arista incidente: Es la arista que incide en los dos vértices que conforman una
arista se llaman puntos finales ("endpoints", en inglés). También se dice que los
vértices u y v son extremos de la arista e.
◎ Orden de un grafo: se define por el número o cantidad de vértices que tenga un
grafo. |V|

◎ Tamaño de un grafo: es el número de aristas. |E|

Un grafo de orden p, y tamaño q lo denotaremos por (p, q)-grafo

Orden p=4
Tamaño q=5

(4,5)-grafo
◎ Distancia: entre los vértices u y v en el grafo, que se escribe d(u, v), es la
longitud de la ruta más corta entre u y v.

◎ Diámetro de G: lo cual se escribe diám(G), es la distancia máxima entre dos

puntos cualesquiera en grafo.

d(A, F) = 2
y
A
diám(G) = 3
 Vértice aislado es un vértice que no es punto
final ni inicial de ninguna arista, de grado 0.

Vértice pendiente o colgante o que es una hoja

es aquel grafo que contiene sólo una arista, si solo
si, tiene grado 1.
Camino es una secuencia de arcos en que el extremo final
de cada arco coincide con el extremo inicial del siguiente en
la secuencia.

Ciclo es un camino simple y cerrado.

 Grafo dirigido G

◎ Consiste en un conjunto de vértices V y un conjunto de arcos A.

Los vértices se denominan nodos o puntos. Los arcos pueden
llamarse arcos dirigidos o líneas dirigidas. Un arco es un par
ordenado de vértices (v, w); v es la cola y w es la cabeza del arco.
El arco (v, w) se expresa a menudo como v → w y se representa
como:
v w

◎ El final de la línea termina en flecha a este vértice se llama punto

inicial y el final, en el vértice llamado cola. Se dice que el arco v →
w va de v a w, y que w es adyacente a v.
Tipos de grafos
1. Grafo simple no dirigido

Un grafo G=(V,E) consta de V, un conjunto no vacío de vértices

V y de E, un conjunto de pares no ordenados de elementos
distintos de V. A estos pares se les llamas aristas.
Ejemplo de grafo simple no dirigido

Los grafos son una herramienta importante, y muy útil, empleada en el área
de las computadoras, principalmente para modelar las redes. Una red es
construida con líneas telefónicas y, por supuesto, por computadoras. En la
siguiente imagen se muestra la ubicación de cada computadora como un
punto y cada línea telefónica con un arco no dirigido. Cada arista conecta
dos vértices distintos y no hay dos aristas que conecten un mismo par de
vértices:
2. Grafo simple dirigido

Un grafo G=(V,E) consta de V, un conjunto no vacío de vértices

V y de E, un conjunto de pares ordenados de elementos
distintos de V. A estos pares se les llamas aristas.
 Ejemplo de un dígrafo o grafo dirigido

◎ Hay situaciones en las que nos interesa

especificar una relación (arista) tiene una
dirección concreta. Por ejemplo, el
siguiente grafo se representan los
diferentes estados de un semáforo, cuyas
aristas tienen definidas una dirección
concreta.
3. Multígrafo

G=(V,E) consta de un conjunto V de vértices, un conjunto E de

aristas y una función f de E en {(u,v,) | u,v  V, u<> v}
Se dice que las aristas e1 y e2 son aristas múltiples o paralelas si
f(e1) = f(e2). Pueden ser dirigidos y no dirigidos.

e1

u v

e2
Ejemplo de multígrafo

Un caso práctico esto se puede utilizar en la red de computadoras, en las

que puede haber muchas líneas de un solo sentido hacia el host en
Veracruz desde cualquier lugar, y tal vez de una línea de regreso a cada
computadora remota desde el host, y se representa de la siguiente forma:
4. Seudografo (es un multígrafo con bucles)

Un grafo G= (V, E) consiste en un conjunto

no vacío de vértices V y un conjunto de
pares de vértices no ordenados E llamados
aristas y una función f(e) desde e hacia el
conjunto:
{(u,v,) | u,v  V, u<> v}
Una arista a es un ciclo si f(e1)={u,u}={u}
para un u que pertenece a V , u  V
Terminología de teoría de grafos

Tipos Aristas ¿Se admiten aristas ¿Se admiten bucles?

múltiples?
Grafo simple No dirigidas No No
Multígrafo No dirigidas Si No
Pseudografo No dirigidas Si Si
Grafo dirigido Dirigidas No Si
Multígrafo dirigido Dirigidas Si No
Modelos de grafos

◎ Nicho de grafos en ecología

◎ Grafos de influencia
◎ Torneo Round – Robin
◎ Grafo de precedencia y proceso concurrente
Nicho de grafos en ecología

Estos modelos involucran la

interacción de diferentes especies de
animales. Por ejemplo, se puede
modelar la competición de varias
especies de un ecosistema. Cada
especie es representada por un
vértice, una arista no dirigida
conecta dos vértices si dos especies
compiten por la misma fuente de
Ecosistema de un bosque
comida.
Grafos de influencia

◎ En el estudio de la conducta de
los grupos, se observo que
cierta gente influye en el
pensamiento de otras. Cada
pertenece del grupo es
representada por un vértice, la
arista dirigida del vértice A al
vértice B indica que la persona A
influye sobre la persona B.
Torneo round - robin

◎ Es un torneo donde cada

equipo juega contra
otro, solo una vez, cada
equipo es representado
por un vértice, y (a,b) es
una arista si el equipo a
vence al b.
Grafo de precedencia y proceso concurrente

◎ Los programas de computadora

pueden ser ejecutados más
rápidamente, ejecutando
concurrentemente las
declaraciones, cada declaración es
representada por un vértice y hay
una arista desde un vértice a otro
si la declaración del segundo
S1 a=0 S5 e=d+1
vértice no puede ser ejecutada
S2 b=1 S6 f=c + d
antes de la del primer vértice.
S3 c= a+ 1
S4 d=b+a
Grafo de llamadas

Mapa del mundo en llamadas telefónicas

Otros más

◎ Grafos de conocidos
◎ Grafo de colaboración
◎ Grafo de red
EJERCICIO
I) Determina si el grafo que se muestra es simple, multígrafo, pseudografo, dígrafo o
un multígrafo dirigido.

1) 2) 3) 4)

II) Explica como se pueden utilizar dos grafos de llamadas, uno con las llamadas
hechas durante el mes de enero y el otro con las hechas durante el mes de febrero,
para determinar el nuevo número de teléfono de las personas que hayan cambiado
de número.
Terminología básica
Grados (valencia) de los nodos en un grafo no dirigido

El grado de un vértice en un grafo sin dirección es el número de aristas que

inciden en él excepto en un ciclo que contribuyen en 2 al grado del vértice. El
grado de v se denota por deg(v) o 𝛿(v).
Ejemplo 1 de grado de vértices

Al vértice g del grafo G se le llama

aislado, porque no tiene aristas y a los
deg(x) = 1 se les llama pendientes,
como el vértice d.
Ejemplo 2 de grados de vértices
Grado de un grafo

El grado total de G es la suma de los grados de todos los

vértices de G. En un bucle se cuenta doble.

El grado total de este grafo es

de de 8.
Teorema del apretón de manos
 Teorema 1 handshaking

Si G = a(V, E) es un grafo no dirigido con e aristas, entonces:

2e = v  V deg (v).
Esto se aplica aun si múltiples aristas y ciclos están presentes.

Ejemplo:
Número de aristas en un grafo con 10 vértices con grado 6 cada uno.
2e = 6 + 6 + 6 + 6 + 6 + 6 + 6 + 6 + 6 + 6
2e= 60
e = 60/2 = 30
COROLARIO

El teorema 1 muestra que la  de los grados de los vértices de un grafo no

dirigido, son pares.

Ejemplo del teorema 1

Teorema 2

Un grafo no dirigido tiene dos conjuntos de vértices (V1 y V2). Si V1 y V2 son

conjuntos de vértices de grado par e impar respectivamente. El grafo no dirigido
de G(V, E):
2e =  v  V deg (v) = v  V1 deg (v) +  v  V2 deg (v)
Grado de un grafo dirigido

◎ En grafos dirigidos existen:

○ Grados de entrada o externos es el número de aristas que inciden en
v denotado por deg + (v) o extdeg(v) o 𝛿 + (𝑣)
○ Grados de salida o internos es el número de aristas que emergen en v
denotado por deg –(v) o indeg(v) o 𝛿 − (𝑣)

◎ Un ciclo contribuye en 1 en ambos grados (externo e interno)

◎ En un vértice es aislado el grado es extdeg(v) = indeg(v) =0
Ejemplo de grados internos y externos en un grafo

Grafo G
Salida entrada
Deg-(a)=4 Deg+(a) =2
Deg-(b)=2 Deg-+(b) =3
Deg-(c)=2 Deg-+(b) =3
Deg-(d)=2 Deg-+(d) =2
Deg-(e)=3 Deg-+(e) =3
Deg-(f)=0 Deg-+(f) =0
Teorema 3

Como cada arista tiene un vértice inicial y vértice final, la suma de los
grados de entrada y la suma de los grados de salida de todos los vértices
del grafo dirigido coincide.

Si G(V, E) es un grafo dirigido entonces:

 𝛿 − 𝑣 = 𝛿 + (𝑣) = |E|

 Existen muchas propiedades de los grafos dirigidos que no dependen

de su dirección, por lo que se ignoran. Al grafo dirigidos al cual se ignora
su dirección se le llama grafo no dirigido subrayado.
Ejercicio y especificar grado de vértices, del grafo y nombre de vértices
especiales

1)

3)

2)
CLASES DE
GRAFOS
SIMPLES
Los grafos completos con n vértices

◎ Se denotan por Kn y son grafos simples que contienen una arista entre
cada par de distintos vértices. El grafo Kn, para n= 1,2,3,4,5,6 son:
Ciclo

◎ El ciclo Cn donde n>= 3 consiste de n vértices v1, v2, v3, … vn y aristas

{v1}, {v2}, …{vn} , donde {v1,v2}. {v2,, v3}, …{vn-1,vn} y {vn,v1} . Los ciclos de
C3, C4, C5 y C6.
Grafos giratorios o de volante

Se obtiene el grafo giratorio Wn cuando se suma un vértice adicional al

ciclo Cn para n>=3 y conectando este nuevo vértice con los vértices Cn
con nuevas aristas. Algunos ejemplos son:
Grafos n - cubos

◎ Se denotan por Qn es un grafo que tiene vértices,

representando la cadena 2n de n bits. Dos vértices son
adyacentes si la cadena de bits que ellos representan difiere
exactamente en un bit.
Grafos
bipartitas
Grafos bipartitas

◎ Algunas veces un grafo tiene la propiedad de que su conjunto de

vértices puede ser dividido en dos conjuntos disjuntos tal que cada
arista conecta un vértice de un subgrupo a un vértice del otro.

◎ Por ejemplo considerando el grupo que represente matrimonios en

un pueblo donde cada persona es representada por un vértice y un
matrimonio representa una arista. En este grafo, cada arista conecta
un vértice en el subgrupo de vértices representando hombres y un
vértice del otro grupo representando a las mujeres.
◎ Un grafo simple G es llamado bipartita y
su conjunto de vértices V puede ser
particionado en dos grupos disjuntos no
vacíos V1, V2. Tal que cada arista en el
grafo se conecte un vértice V1 y uno en
V2, pero que no se conecten 2 aristas en
V1 o en V2.
Ejemplo bipartita

◎ G es bipartita como se muestra ya que el conjunto de vértices

puede ser particionado dentro de dos conjuntos, A1 =
{V1,V3,V5} A2={V2,V4,V6} y cada arista de G conecta un vértice
de A1 y A2.
Grafos bipartitas completos

◎ El grafo Km, n es el grafo que tiene su conjunto de vértices particionado en

dos subconjuntos de m y n vértices, si y solo si, un vértice esta en el
primer subconjunto y otro en el otro.

Un grafo bipartito completo G= (V1  V2, E) es un grafo bipartito

tal que  v1  V1,  v2  V2  e(v1,v2)  E. Es decir, un grafo
bipartito completo está formado por dos conjuntos disjuntos de
vértices y todas las posibles aristas que unen esos vértices.
El grafo completo bipartito con particiones de tamaño |V1| = m y |V2|
= n, es denotado como Km,n .
Los grafos bipartitas
completos K1,1, K1,2, K1,3,
K2,2, K2,3 K3,3 K3,5 Y
K2,6.
Ejercicios: ¿Son bipartitas?

1) 2)
Aplicaciones de Tipos de Grafos Especiales

◎ Algunos tipos de grafos especiales, son usados en modelos para

comunicación de datos y procesamiento en paralelo.

Algunas de estas redes están basadas en topología de estrella

donde todos los dispositivos están conectados a uno de control
central.
Esta topología puede
ser empleada usando
un
Grafo bipartita
completo K1, n
Topología de anillo

◎ Donde cada dispositivo esta conectado a otros dos. Esta

configuración esta modelada usando n ciclos (Cn)

Los mensajes son

enviados de dispositivo
a dispositivo hasta que
el token es recibido.
◎ Algunas LAN usan topología hibridas o mixtas, las redes
pueden utilizar una combinación de diversas topologías.
Donde los mensajes son enviados alrededor del anillo o a
través de un dispositivo central. Esta redundancia hace
que la configuración sea mas óptima como un volante Wn.
Nuevos grafos de otros

◎ En ocasiones solo se necesitan una parte de un grafo para resolver un

problema. Cuando las aristas y los vértices son removidos un
pequeño grafo es obtenido, el cual es un subgrafo del grafo original.

Un subgrafo de un grafo G=(V, E), es un grafo H=(W, F)

donde W <= V y F <= E.
Grafo unión
◎ Dos o más grafos pueden ser combinados de distintas formas. El grafo
nuevo que contiene todos los vértices y aristas es llamado grafo
unión.
◎ La unión de dos grafos simples
G1 = (V1E1) y G2 = (V2E2) es el simple grafo con un conjunto de
vértices V1  V2 y el conjunto de aristas E1  E2. La unión de 2 grafos
G1 y G2 serian:
Ejercicios

1) Un grafo con catorce aristas, tres vértices de grado 1, dos

vértices de grado 4, un vértice de grado 3 y el resto de grado 2
ha de tener exactamente trece vértices. ¿Es esto cierto?