1_3_TeoGrafos

Teoría de Grafos
I.

Definiciones Básicas

Los grafos son una manera de representar relaciones binarias, y sirven como modelo
matemático para representar el mundo real.
Definición

GRAFO DIRIGIDO (DIGRAFO)

Un grafo dirigido es un conjunto V y una relación E asociada a él, esto es:
G = (V , E )
donde:
E ⊆ V ×V

Los elementos de V se llaman vértices, y los de E se llaman arcos.
Los grafos son pordefinición dirigidos, ya que el orden en que aparecen los
elementos en cada elemento de E es relevante.
Cuando se escribe (a,b) se está denotando el arco que va de a hasta b.
Definición

GRAFO NO DIRIGIDO (GRAFO)

Un grafo es no dirigido si y sólo si E es simétrica, esto es:
∀a , b ∈ E
( a , b) ∈ E ⇒ ( b , a ) ∈ E
Cuando hablamos de grafos no dirigidos, los elementos de E se llaman aristas.y sedenotan {a,b}
Cuando se considera como no dirigido un grafo que originalmente es dirigido, se
habla del grafo fundamental del grafo dirigido.
Definición

GRAFOS SIMPLES

Un grafo es simple si y sólo si E es irreflexiva, esto es:
∀a ∈ E
( a , a) ∉ E
Un elemento de E del tipo (a,a) se llama loop.
Cuando se considera un grafo, dirigido o no, sin considerar los loops que contenga, se
habla del grafosimple del grafo original.
Definición

ORDEN Y TAMAÑO DE UN GRAFO

Sea G = (V , E ) un grafo, se definen:
orden(G) = V (G )
tamaño(G) = E ( G )

Teoría de Grafos

ADYACENCIA DE NODOS

Definición

Sean G = (V , E ) un grafo. v , w ∈V son adyacentes si y sólo si:

( v , w) ∈ E

ó ( w, v ) ∈ E

ROTULADOR DE VÉRTICES (ARCOS)

Definición

Un rotulador de vértices (arcos) es una función
f : E (G ) → Dpara arcos,
g:V (G ) → D
para vértices,
donde D es algún dominio de rótulos (un valor, por ejemplo).
Estas últimas definiciones pueden parecer arbitraria, pero más adelante veremos su
utilidad.

II.

Grado de un Vértice
GRADO DE UN VÉRTICE

Teorema

Sea v ∈V un vértice de un grafo, se definen:
grafos dirigidos:
grado+(a) = {a ∈ V : (b, a ) ∈ E}
(aristas que llegan al vértice a)

grado-(a) = {a ∈ V :(a, b ) ∈ E}
+

(aristas que salen del vértice a)

-

grado(a) = grado (v) + grado (v) (todas las aristas)
grafos no dirigidos:
grado(a) = {a ∈ V : (a, b ) ∈ E}
a).1.1.2

Primer Teorema de Grafos

Sea G = (V , E ) un grafo, entonces:
grafos dirigidos:
∑ grado − (v) = ∑ grado + (v) = E
v ∈V

v ∈V

grafos no dirigidos:
∑ grado(v) = 2 ⋅ E
v ∈V

Corolario: en cualquier grafo no dirigido, hay un númeropar de vértices de grado
impar.

J. Ponce, G. Solis y L. Ulfe – Investigación de Operaciones

2

Teoría de Grafos

Teorema

GRADO MÍN (MÁX) DE UN GRAFO

Sea G = (V , E ) un grafo, se definen:

δ (G ) = min{ grado(v ): v ∈V (G )}

∆(G ) = max{ grado(v ): v ∈V (G )}

Teorema

GRAFO K-REGULAR

Un grafo G = (V , E ) es k-regular si y sólo si
grado(v) = k
∀v ∈V
Los de grado 0 (nulos de orden n), 1 y2 (ciclos de orden n) son triviales, pero los
de grado 3 o mayor (llamados cúbicos) no lo son:

III.

Subgrafos

Teorema

SUBGRAFO

Sea G = (V , E ) un grafo, entonces un subgrafo de G es un grafo G ′ = (V ′ , E ′ )
con:
V ′ ⊆ V y E ′ ⊆ E tales que ( a , b) ∈ E ′ ⇒ a , b ∈V ′

Un subgrafo no es más que una parte del grafo original. Se dice que G’ tiene la
extensión de G cuando V ′ = V , pero noteque no necesariamente E ′ = E .

Teorema

SUBGRAFO INDUCIDO

Sea G = (V , E ) un grafo, y sea V ′ ⊆ V , entonces el subgrafo inducido por V’
G ′ = (V ′ , E ′) , con E ′ = {( a , b) : a , b ∈V ′ ∧ ( a , b) ∈ E }

es:

IV.

Isomorfismo de Grafos

Teorema

ISOMORFISMO

Sean G = (V , E ) y G ′ = (V ′ , E ′) grafos. G y G’ son isomorfos si y sólo si
existe una función biyectiva:
ϕ :V → V ′ tal que ∀a ,b ∈V se tiene:
(a , b) ∈ E ⇔ (ϕ (a ), ϕ (b)) ∈ E ′
Notación: G ≈ G ′ (isomorfos)

Teorema

INVARIANTE

Sean G = (V , E ) y G ′ = (V ′, E ′ ) grafos Una invariante es toda función del tipo
η :Grafos → N
tal que:
G ≈ G ′ ⇒ η (G ) = η (G ′)
Hasta ahora se han revisado los siguientes invariantes:

J. Ponce, G. Solis y L. Ulfe – Investigación de Operaciones

3

Teoría de Grafos

V (G ) , E (G ) ,...