Grafos

GRAFOS
DEFINICIÓN:
• Un grafo G es un diagrama que consta de un conjunto de vértices (V)
y un conjunto de lados (L). Por ejemplo:
• A partir de esta figura se definen los siguientes elementos:

Grafos
• Vér$ces (nodos): Se indican por medio de un pequeño círculo y se les
asigna un número o letra. En el grafo anterior los vérFces son V = {a, b,
c, d}.
• Lados (ramas o aristas)
Son las líneas que unen un vérFce con otro y se les asigna una letra,
número o una combinación de ambos. En el grafo anterior los lados L = {1,
2, 3, 4, 5, 6}.
Lados paralelos
Son aquellas aristas que Fenen relación con un mismo par de vérFces. En
el grafo anterior los lados paralelos son: P = {2, 3}.
Grafos
• Lazo
Es aquella arista que sale de un vérFce y regresa al mismo vérFce. En
grafo anterior se Fene el lazo: A = {6}.
• Valencia de un vér$ce
Es el número de lados que salen o entran a un vérFce. En el grafo anterior
las valencias de los vérFces son:
Valencia (a) = 2 Valencia (b) = 4 Valencia (c) = 2 Valencia (d) = 3
Hay que observar cómo en el caso del vérFce d el lazo sólo se considera
una vez, entrada o salida pero no ambos.
TIPOS DE GRAFOS
• Grafos simples
Son aquellos grafos que no Fenen lazos ni lados paralelos.
En la siguiente figura se muestra un ejemplo de grafo simple.
TIPOS DE GRAFOS
Grafo completo de n vér$ces (Kn)
Es el grafo en donde cada vérFce está relacionado con todos los demás,
sin lazos ni lados paralelos. Se indica como Kn, en donde n es el número
de vérFces del grafo.
En las siguiente figura se muestran tres ejemplos de grafos completos.
• La valencia en cada uno de los vérFces de los grafos completos es (n -
1), y el número de lados está dado por la expresión
! !"#
Núm. de lados = $
en donde n es el número de vérFces del grafo.
El grafo K_5 de la siguiente figura Fene
Valencia de cada vérFce = (5 - 1) = 4

% %"#
Núm. de lados = $
= 10
• Complemento de un grafo (G ')
Es el grafo que le falta al grafo G, de forma que entre ambos forman un
grafo completo de n vérFces. Este grafo no Fene lazos ni ramas paralelas
En la siguiente figura se muestra un ejemplo de grafo G junto con su
complemento G’:
Grafo Bipar$to
• Es el grafo que está compuesto por dos conjuntos de vérFces, A = {a1, a2, ...,
an} y B = {b1, b2,…,bm} en donde los elementos del conjunto A se relacionan
con los del conjunto B, pero entre los vérFces de un mismo conjunto no
existe arista que los una.
• Sean los conjuntos de vérFces A = {1, 2, 3, 4} y B = {5, 6, 7}, con los cuales se
forman los siguientes grafos:
Estos dos grafos son biparFdos, ya

que los elementos del conjunto A
están relacionados con los del
conjunto B, pero entre los
elementos de un mismo conjunto
no hay relación alguna.
Una forma muy sencilla de saber si un grafo es biparFdo es aplicar el hecho de
que nunca Fene un ciclo de longitud impar, además de que debe de cumplir
con la caracterísFca mencionada anteriormente.
• Grafo bipar$do completo (Kn,m)
Es el grafo que está compuesto por dos conjuntos de vérFces, uno de ellos A =
{a1, a2, a3,..., an} y otro B = {b1,b2,..., bm}, y en el que cada vérFce de A está
unido con todos los vérFces de B, pero entre los vérFces de un mismo
conjunto no existe arista que los una. El grafo biparFdo completo se indica
como K(n_m)
En la siguiente figura se muestran dos grafos biparFdos completos:
En el caso de K(4,2) se Fene que A {1,2,3,4} y B={a,b}, mientras que en K(2,3)
se Fene que A = {a, b} y B = {1, 2, 3}.
• Representación matricial:
• El uso de matrices para representar sistemas de ecuaciones, relaciones o
grafos permite una rápida y clara manipulación de la información, así como
el determinar algunas propiedades de los grafos que de otra manera serían
más dibciles de obtener. Además de esto se Fene que en la computadoras es
más fácil el manejo de matrices, ya que se pueden tratar como arregles o
listas doblemente ligadas.
• A conFnuación se describen las representaciones matriciales de los grafos.
• Matriz de adyacencia (M a)
• Es una matriz cuadrada en la cual los vérFces del grafo se indican como filas
y como columnas: el orden de los vérFces es el mismo que guardan las filas y
las columnas de la matriz. Se coloca un 1 como elemento de la matriz
cuando existe una relación entre uno y otro vérFce, o bien un cero cuando
no exista relación alguna.
Algo que se puede observar en la matriz de adyacencia es que no se pueden
representar en ella los lados paralelos, como ocurre con el par de aristas que unen los
nodos b y d. En esta matriz también la mayoría de las aristas están repeFdas, como
ocurre con la arista que une a los vérFces b y c que Fene un 1 en la línea b columna c,
pero que también Fene un 1 en la fila c columna b. Por úlFmo, los lazos, a diferencia
de las aristas normales solamente se representan una sola vez. Se puede concluir que
la matriz de adyacencia es buena para llevar a cabo operaciones con relaciones, pero
que no permite registrar en ella toda la información del grafo.
• Algo que se puede observar en la matriz de adyacencia es que no se pueden
representar en ella los lados paralelos, como ocurre con el par de aristas que
unen los nodos b y d. En esta matriz también la mayoría de las aristas están
repeFdas, como ocurre con la arista que une a los vérFces b y c que Fene un
1 en la línea b columna c, pero que también Fene un 1 en la fila c columna b.
Por úlFmo, los lazos, a diferencia de las aristas normales solamente se
representan una sola vez. Se puede concluir que la matriz de adyacencia es
buena para llevar a cabo operaciones con relaciones, pero que no permite
registrar en ella toda la información del grafo.
• Matriz de incidencia (M¡)
En esta matriz se colocan los vérFces del grafo como filas y las aristas como
columnas.
Considérese el siguiente grafo junto con su matriz de incidencia
correspondiente:
En esta matriz sí es posible representar lados paralelos, como ocurre con r_1
r_2, r_5 y r_6. Al sumar los elementos de cada una de las filas se obFene la
valencia de los vérFces, y al sumar las columnas es posible disFnguir cuando se
trata de un lazo ya que su suma es 1, como ocurre con r_3 y r_8. Cuando no se
trata de lazos, el resultado de la suma es 2.
• Caminos y circuitos
En un grafo se puede recorrer la información de diferentes maneras, lo cual
implica seguir disFntas rutas para llegar de un nodo del grafo a otro. A
conFnuación se definen varios conceptos relacionados con el recorrido de un
grafo, y en el ejemplo se ilustran éstos.
Camino
Es una sucesión de lados que van de un vérFce x a un vérFce w (dicho; lados se
pueden repeFr)
Circuito (ciclo)
Es un camino del vérFce w al vérFce w, esto es, un camino que regresa si mismo
vérFce de donde salió.
Circuito simple de longitud n
Es aquel camino del vérFce x vérFce w que solamente Fene un ciclo en
la ruta que sigue.
• Camino simple de longitud n
Es una sucesión de lados que van de un vérFce x a un vérFce w, en donde los
lados que componen dicho camino son disFntos e iguales a n. Esto significa que
no se puede pasar dos veces por una misma arista.
Con relación al grafo
se Fenen los recorridos que muestra la tabla con sus correspondientes

caracterísFcas.
• Grafo conexo
Es aquél en el que para cualquier par de vérFces w, x, disFntos entre sí, exíste
un trayecto para ir de w a x.
Aquí se muestra un grafo conexo y uno no conexo:
• En el grafo conexo (conectado) siempre existe un camino para ir de un vérFce a
otro, sin embargo en el grafo no conexo existen vérFces que no están conectados y,
por lo tanto, no se puede acceder a ellos. Así, en el. grafo no conexo del ejemplo no
se puede tener un camino para ir del vérFce b al e.
Camino de Euler
Es aquel camino que recorre todos los vérFces pasando por todas las ramas
solamente una vez.
Considérese el siguiente grafo:
Un camino de Euler es {a, b, e, d, c, f, g, d, h, h, i, g}

o bien {g, i, h, h, d, g, f, c, d, e, b, a).
• Una caracterísFca importante de los grafos que Fenen camino de Euler es que
siempre comienza y termina en vérFces que Fenen valencia impar, por esta
razón es imposible que en el grafo del ejemplo un camino de Euler pueda
comenzar en el vérFce f. Por otro lado, si un grafo Fene más de dos vérFces
con valencia impar, entonces no puede tener un camino de Euler ya que es
requisito que tenga dos y solamente dos vérFces de valencia impar.

Grafos

Cargado por

Copyright:

Formatos disponibles

Grafos

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Grafos

Cargado por

Copyright:

Formatos disponibles

GRAFOS

• A partir de esta figura se definen los siguientes elementos:

Valencia de cada vérFce = (5 - 1) = 4

Estos dos grafos son biparFdos, ya

se Fenen los recorridos que muestra la tabla con sus correspondientes

Un camino de Euler es {a, b, e, d, c, f, g, d, h, h, i, g}

También podría gustarte