mercadotecnia

Unidad 5.- Grafos y árboles

GRAFOS.
INTRODUCCIÓN
El “gráfico” tiene varios sentidos en matemáticas. Hemos usado el término “gráfica” en el sentido de
una relación o de una función.
En muchas partes de la ciencia de las computadoras y de la informática aparecen los grafos,
especialmente los grafos de árbol, y los grafos dirigidos. Los diagramas de flujo, por ejemplo, son
grafos dirigidos.GRAFOS Y MULTIGRADOS.
Un grafo consta de dos cosas:
Un conjunto N cuyos elementos se llaman nodos, puntos o vértices.
Un conjunto S de parejas no ordenadas de nodos diferentes, llamadas
segmentos, aristas o arcos.
Denotaremos un grafo por G =(N, S) cuando queremos destacar las dos partes de G.
Los nodos u y v se llaman adyacentes si hay un segmento {u, v}
Representaremos de una maneranatural los grafos por diagramas en el plano. O sea, cada nodo v de
N se representa por un punto (o pequeño círculo) y cada segmento s = {v1, v2} se representa por una
curva que conecta sus terminales v1 y v2.
EJEMPLO.
La figura 1.1 representa el G con cuatro vértices, A, B, C y D, y cinco segmentos s1 = {A, B},
s2 = {B, C}, s3 = {C, D}, s4 = {A, C}, s5 = {B, D}. Usualmente denotamos un grafodibujando su
diagrama en lugar de hacer una lista explicita de sus nodos y segmentos.
La figura 1.2 no es un grafo sino un multigrafo. La razón es que s4 y s5 son segmentos múltiples, o
sea segmentos que conectan las mismas terminales, y s6 es un lazo, o sea, un segmento cuyas
terminales son el mismo nodo. La definición de grafo no permite ni segmentos múltiples o
multisegmentos, ni lazos. Enotras palabras, podemos definir un grafo como un multigrafo sin
multisegmentos ni lazos.
s6
A

D

s1

A

s4

s2

s1

D

s3

s3
s5
s4

B

s2

C

B

C

s5
Figura 1.1
Ing. Miguel Ángel Durán Jacobo

Figura 1.2
1

Unidad 5.- Grafos y árboles

Lazo

s1

A
s2

D
s3

Segmento,
arco, arista

s4
B

C
s5

Nodo,
punto,
vértice

Segmentomúltiple o
multisegmento

Figura 1.3

GRADO DE UN NODO
Si v es una terminal de un segmento s, decimos que s es incidente en v. El grado de v, escrito
gr(v), es igual al numero de segmentos que inciden en v. (Un nodo de grado cero, o sea un nodo que
no pertenece a ningún segmento, se llama nodo aislado)
Teorema 1.- La suma de los grados de los nodos de un grafo es igual al doble del número
desegmentos.
EJEMPLO
Observemos que en la figura 1.1 se tienen por cada vértice, los grados siguientes:
gr(A) = 2, gr(B) = 3, gr(C) = 3, gr(D) = 2
La suma de los grados es 10, que, como dice el Teorema 1, es el doble de segmentos. Se dice que
un nodo es par o impar según que su grado sea par o impar. Así A y D son nodos pares, mientras
que B y C son nodos impares.
Ahora veamos que en la figura1.2 se tienen por cada vértice, los grados siguientes:
gr(A) = 2, gr(B) = 3, gr(C) = 3, gr(D) = 4
Como podremos notar el grado de D no es 2, sino 4, ya que el lazo se cuenta 2 veces para el grado
de su nodo. Y la suma de los grados del nodo es 12, y una vez más se comprueba el Teorema 1,
donde el grado total corresponde al doble de sus segmentos.
Ing. Miguel Ángel Durán Jacobo

2Unidad 5.- Grafos y árboles

VALENCIA
La valencia es la suma de los grados de los nodos.
De la figura 1.1

De la figura 1.2

A
2
B
3
C
3
D
2
Val 10

A
B
C
D
Val

2
3
3
4
12

Tipo de grafos.

Grafos simples:
Se dice que es grafo simple cuando no hay más de una arista entre un par de nodos (no más de de una
arista dirigida en el caso de gráficas dirigidas).
Ejemplosa

Ing. Miguel Ángel Durán Jacobo

3

Unidad 5.- Grafos y árboles

Grafos bipartitos:
Se dice que es un grafo bipartito G cuando un conjunto de nodos N se puede particionar en dos
subconjuntos P y Q tales que, cada segmento de G, conecta un nodo de P con un nodo Q.
Ejemplos:

P

Q

P

Q

P

Q

Un grafo bipartito completo, es cuando cada nodo de P está conectado con...