&raÍQs·

·
'L. a teoría de grafos es 1m~i disciplina anrigúa con muchas aplicaciones modernas. Sus ideas
_-. · , básiéas Iasintrodujoe}gi:án matén1ático suizo LeQnhard E:uler en ~-1 ~iglo xvm. Euler utilizó
.. ~ - Jos grafos pa~a resolver e! famoso P!"Obl~~na de- lq~ puentes de Komgsberg, que estudiare-
. rµós en esie c¡ipílulo. ., -- >·. _ _ - - _,. :., ,. .
• _ Los.grafos fo emplean para resolver prob]em_~s de div,ersas- áreás.'Pueden utilizarse, por ejem-
-pJo, pi;tra determinar si sé 1:iuede, o .rio impiem.erJ.tar tiÍí cirtüito $Óbre_una placa de una sola capa.
: · ' Podi n19s diferenciar_dos c~mput;stos qqíQli~os que teug~ri l;:l misma fórmula molecular, pero dis-
~- :·- t,ínfa ·estnicrúrit pór medjó de gráfos. Ta111 biep se pueden usar los grafos para estudjar la estrnctu-
• "'"ni <;le'la Red d~,Iq_teniet Podemos deterrrµnar si•dos_ordenadores-; é.5fáQ conectados ono por un en-
., lace empleand(l_mofl~-l9tde" ~fofos p~a re9es inforrnáticas/ Podén1os utilizar grafos ponderados
- _(esto es;\grafos a cad.a uh~ de euyas aristas -se les asigna \p1 peso) para resolver pr~>blernas como el
,• -de hallar el camino ~f~ :corto entre dos ciú'dades en uná re<f de tmnsp9rles. También se pueden uti-
, _'lizm· los-grafos _gara progra!11a:r e,xámenes Ypara asignar canal.y$ a lq.s ~mí~orás_de tekvisión.

Intiód~ccion"_a-los grafos
,-.. h •

J,;s grafos son estrn~ti.lras discretas que constan de vért;ices yue aristáS que conectan entre sí es~s
"'.éitices. Hay varios tipos distintos de grafos, que sé djfefoncian eritre sí por él tipo yel número de
"aristas que pueden cónectar·cada par de vértices. Los problernás que se püeden resolver con téc-
nicas de la teoría de grafos aearecenen prácticamente cuáÍqllier disc;;íplina. Veremos ejemplos de
cómo utilizar,lós. grafos"comoi1JQdek>s en diversas áreas. Por ejemplo, veremos cómo se usan los
gr~tfos pai:a Íepresentar 111 competición de especies distintas en un mismo nicho ecológico, cómo
.cmpleaí· grafqs para rcpresenta:r;.,q1,1ién influye sobre quién fo una organi.zacjór1 y cómo usar grafos
. para repre~~ntar los.resultados. d~un torneo deportivo. Más, adelante veremos cómo t;ttilizar los grac
ue
,. Íós para resolver-otro:s muchos-tipos de _problemas1 como el calciilar el número de cornbina-
,ciones diférentes de :vuelo¡; entre dos ciudades de un_aJeq aérea, eJ d~ d~tcnrunar si es posible o no
recorrer todas.lascall~s de·una ciudad sin pasar dos veces por lamiima calle y el de hallar el nú- ,
mero ele cólores que:_se necesitan para colorear las regioÍ:uW de uri mapa.
><! .., • . ~' ~ ,,

' - ~· ~ .. ,

" .
TIPOS pE· GRAFOS_
~ >- ' , ' - . . .
, _Vaipos ~ preseót_a r iós dÍferente.s tipos ele grafos rhostrand:o:ti iorína en gue se puede mi Iizar
cada uilo de ellos para1t¡_odelar una redjnfonuática. Su¡Jongaiuos que una red consta de orde-
n~dores y ae~1í~eas telefónic:a:s que conectan esos ordenadóres: Podemos representar cada or-
CÍenadoJ mediante un punto y cada' línea telefónica mcdiánte un segmel)to, tal y como se mues-
tra ~n la Figul'a l. . . - · -- . ,
a
En la_red de la Fig1,1ra l hay lo ~iuno una línea tf lefqnica entre cada dos ordenadores, cada
Ürieá opera en ambas ,direcciones, y ningún ordenador tiene una linea teléfónica que lo conecte
· cÓúsigo mismo. Por tanto; esta red se puede modelar usando un grafo simple, que consta de vér-
tices que representan a fos ordenadores y de aristas no dirigidas qu~ representan a las líneas te-
lefónicas. Cada arista conecta dos vértices djstintos y no hay-dos aristas que conecten un mismo
-par de vértic.es.

503
504 .\1atemfüica discreta y sus aplicaciones

De1roi1
~ N ueva York
San Francisco ---------5tic~
•\ ~ D - - - -
enver Washington

Los Ángeles

Figura l. Una red informá!ica.

DEFINICIÓN 1 Un grafo simple G = (V, E).consta de V, _un cpojuñfo·no' vacío .de vérticr;;s, y de E, un conjunto
de pares no
.
ordenados
)
de.
eiementos distintos de
.
V" A
.
estos pares'_.se les Jlama
,' .
aristas..

Cuando hay mucho tráfico de información, puede haber líneas' telefónicas múltiples entre los or-
denadores de la red, como se muestra en la Figura 2. Los grafos simples no bastan para modelar
esta situación. En lugar de grafos simples, emplearemos multigrafos, que constan de vértices y de
aristas no dirigidas entre esos vértices, pero admitiendo la existencia de aristas múltiples entre pa-
res de vértices. Todo grafo simple es un multigrafo. Sin embargo, no todos los multigrafos son gra-
fos simples, puesto que en un multigrafo puede haber dos o más aristas conectando un mismo par
de vé1tices.
No podemos usar simplemente un par de vértices para especificar la arista de un grafo si hay
aristas múltiples. Esto hace que la definición formal de multigrafo sea un poco más complicada.

DEFINICIÓN 2 Un multip,rafo G = (V, E) consta de un conjunto V éle vértices. un coajunto Ede aristas y una
é
ftínciónf de E en {fu, vl l ,ú , v E V, u .. v). Se dice que ~as aristas e 1 y 2 son arisías múltiples
oparatel.'is.sif(f1J= f(e 2). · · ·

El lector debería observar que las aristas múltiples en un multigrafo están asociadas a un mis-
mo par de vértices. No obstante, diremos que l u, v I es una arista del grafo G = (V, E) si hay al
menos una arista e con.f(e):::; {u., v). No haremos distinciones entre la arista e y el conjunto ( u,
v) asociado a no ser que la identidad de alguna de las arislas múltiples en concreto sea impor-
tante.
Una red informática puede contener una línea telefónica que conecte un ordenador consigo
mismo (a efectos de diagnóstico, quizá), como se ilustra en la Figura 3. No podemos usar rnulti-
grafos para representar estas redes, ya que no se admiten bucles (esto es, aristas que conectan un
vértice consigo mismo) en un multigrafo. En lugar ele multigrafos, utilizaremos pseudografos, que
son más generales que los muJtigrafos, ya que una arista de un pseudografo puede conectar un vér-
tice consigo mismo.
A fin de definir f~rma lmeme los pseudografos, necesitamos asociar éllistas a conjuntos que
co tengan un solo vértice. •

0 Los Ángeles

Figura 2. Una red informática con líneas múltiples.

 Grafos 505

Lo~ Ángeles

.Figura J. Una red infom1ática con líneas de diagnóstico.

DEFI 'ICIÓ 3 Un pseudografo G = (V, E) consta de un conjunto V de vértices, un conjunio E de aristas y

una función/ de E en ( {11, v ) 1u, v E VI. Una arista e es un bucle, o lazo, sif(e) = ¡u, u 1 =
{u} para algún u E V.

Puede que las líneas telefónicas de una red informática no operen en las dos direcciones. Por ejem-
plo, en la Figura 4, el ordenador que está en Nueva York sólo puede recibir datos de otros orde-
nadores, pero no puede enviar datos. Otras líneas telefóni cas que sí funcionan en ambas direc-
ciones se representan por medio de pares ele aristas en direcciones opuestas.
Utilizamos grafos dirigidos (que ya hemos estudiado en el Capírulo 7) para modelar redes de
este tipo. Las aristas de un grafo dirigido son pares ordenados. Se admiten los bucles, pares orde-
nados con sus dos elementos iguale-'>, pero no se admiten aristas múltiples en la misma dirección
entre dos vértices. Recordemos la definición.

DEFI NICIÓN 4 Un grafo dirigido (V, E) consta de un conjunto V de vé.1tices y de un conjunto E de aristas,
que son pares ordenados de elementos de V.

Utilizamos una flecha apuntando desde u hacia v para indicar la dirección de la arista (u , r).

Finalmente, puede haber líneas múltiples en la red informática, de modo que haya varias lí-
neas unidireccionales desde cada nodo en dfrección al ordenador de ueva York y quizá más de
una línea de vuelta a cada nodo desde Nueva York, como se muestra en la figura 5. Utilizaremos
multigrafos dirigidos, que pueden 1ener aristas dirigidas múltiples desde un vértice a un segundo
vértice (que, eventualmente, puede coincidir con el primero), para representar este tipo de redes.
Presentamos a continuación la definición formal de multigrafo dirigido.

DEFI 1ICIÓ 1 5 Un mulrigrafo dirigido G = (V, E) consta de un conjunto V de vértices, un conjunto E de aris-
tas y una función/ de E en f (u, v) 1u, v e V). Se dice que tas aristas e1 y e2 son aristas múlti-
ples sif(e 1) = f(e 2) .
1

San Francisco

Los Ángeles

Figura 4. Una red informática con líneas telefónicas unidireccionales.

506 Matemática discreta y sus aplicaciones

Los Ángeles

Figura 5. Una red infonnática con líneas unidireccionales múltiples.

El lector debería observar que las aristas dirigidas mú ltiples están asociadas a un nusmo par de vér-
tices. No obstante, diremos que (u, v) es una arista de G = (V, E) siempre que haya al menos una
arista e con f(e) = (u, v). No haremos distinciones entre la arista e y el par ordenado (u, v) a no ser
que la identidad de alguna de las aristas múltiples en par ticular sea impo1t ante.
La Tabla 1 resume la terminología que se emplea para los diferentes tipos de grafos. Utili-
zaremos Ja palabra grafo para describir grafos con aristas dirigidas o no dirigidas, con o sin bucles
y aristas múltiples. Emplearemos los términos grafo no dirigido o pseudografo para indicar gra-
fos no dirigidos que pueden tener aristas múltiples y bucles. Siempre usaremos el adjetivo dirigido
al referimos a grafos cuyas aristas estén asociadas a pares ordenados.
Debido a que el interés por la teoría de grafos es relativamente reciente, y a que tiene apli-
Knlaces
caciones en disciplinas muy diversas, en la teoría de grafos se emplean muchas tenninologías dis-
tintas. Cada vez que encuentre en sus lecturas alguno de los ténninos del párrafo anterior. el lec-
tor haría bien en cercíorarse del sentido que se le da exactamente.
. ,
:MODELOS CON GRAFOS
Los grafos se emplean en una gran variedad de modelos. Presentamos aquí unos pocos, escogidos
Enlaces de diversas áreas. Otros se irán presentando en secciones poste1iores, tanto de este capítulo como
ele los siguientes.

EJEMPLO 1 Grafos de solapamiento de nichos en Ecología Los grafos se emplean en muchos modelos que
tienen que ver con las interacciones entre especies animales distintas. Por ejemplo, la competición
Eu.laccs
entre especies en un ecosistema puede representarse mediante un grafo ele solapamiento ele ni-
chos. Cada especie se representa por un vértice. Una arista no dirigida conecta dos vértices si las
dos especies representadas por esos vértices compiten entre sí (esto es, si algunas de las fuentes de
alimento de las que se nutren son las mismas). El grafo de la Figura 6 representa el ecosistema de
un bosque. Vemos en este grafo que las ardillas y los mapaches compíten entre sí, mientras que los
cuervos y las musarañas no lo hacen. ◄

EJEMPL02 Grafos de conocidos Podemos usar modelos ele grafos para representar relaciones entre perso-
nas. Por ejemplo, podemos usar un grafo para representar el hecho de que dos personas se co-
EnlaéÍ,s nozcan. Cada pÉsona de un grupo concreto se representa mediante un vértice. Se utiliza una aris-
ta no dirigida p •~ conectar dos per_sonas cuanc!o esas dos personas se conocen. E!: la Figu~a 7 _se.
muestra un peq eno grafo de conocidos. El grafo que corresponde a toda la poblaeJOn mundial tie-
ne más de 6 mi millones de vértices y, probablemente, ¡más de un billón de aristas! Seguiremos
analizando estos grafos en la Sección 8.4. ◄

Tabla l. Terminología en teoría de grafos.

Tipos Aristas ¿Se admiten arisras múltiples ¿Se admiren bucles?

Grafo simple No dirig idas No No
Multigrafo No dirigidas Sí No
Pseudografo No dirigidat Sí Sí
Grafo dirigido ' Diri gidas No Sí
Multigrafo dirigido Dirig idas Sí Sí
 Grafos 507

Mapache a,-- - - - - - -- ----'11 Eduardo

Búho

K amlesh

Ching

Páj<1ro carpimcro
Gail
Koko
Kari S haquira

Figura 6. Un grafo de solapamiento de nichos. Figura 7. Un grafo de conocidos.

1

EJEMPLO3 Grafos de influencias Se ha observado en estudios del comportamiento de grnpos que ciertas
personas pueden influir en la forma en que piensan otras personas. Puede usarse un grafo diri-
gido, llamado grafo de influencias, para representar este comportamiento. Cada persona del gru-
po se representa por un vértice. Hay una ruista dirigida del vértice a al vértice b si la persona re-
presentada por el vértice a influye sobre la persona representada por el vé1tice b. En la Figura 8
se muestra un ejemplo de grafo de influencias para las personas de un grupo. Deborah puede in-
fluir sobre Brian, Fred y Linda, pero nadie puede influir en ella. Yvo1me y Brian se influyen mu-
tuamente. ◄

EJEMPLO 4 El grafo de Hollywood El grafo de Hollywood representa a los actores como vértices y conecta
dos vértices si los actores representados por dichos vértices han trabajado juntos en alguna película.
Según la lnternet Movie Database, en noviembre de 2001 el grafo de Hollywood tenía 574.724 vér-
tices, que representaban a actores que habían aparecido en 292.609 películas. y tenía más de 16 mi-
llones de mistas. Hablaremos ele ciertos aspectos del grafo de Hollywood en la Sección 8.4. ◄

EJEMPLO 5 Torneos de todos contra todos Un torneo en el que cada equipo se enfrenta exactamente una
vez a cada uno de los restantes se llama torneo de todos contra todos. Estos torneos se pueden re-
, ~nláce~
presentar usando grafos dirigidos en los que cada equipo se representa mediante un vértice. Nótese
que (a, b) es una arista si el equipo a vence al equipo b. En la Figura 9 se muestra un grafo de este
tipo. Vemos que el Equipo 1 ha salido invicto del torneo, a diferencia del Equipo 3, que no ha ven-
cido a ningtín otro equipo. ◄

EJEMPLO6 Grafos de colaboración Los llamados grafos de colaboración sirven para modelar la coauto-
ría de artículos académicos. En un grafo de colaboración, los vértices representan personas (res-
tringidas, quizá, a una cierta comunidad científica) y una arista conecta a dos personas si éstas han
escrito conjuntamente un artículo. Se ha estimado que el grafo de colaboración de las personas que
colaboran en artículos de investigación matemática tiene más de 337.000 vértices y 496.000
aristas. Veremos este grafo con mayor detalle en la Sección 8.4. ◄

Equ ipo Equipo

1 2

Equipo Equipo
Dcborah frcd Yvonne 5 4

Figura 8. Un grafo de influencias. Figura 9. Un modelo de un torneo de todos contra todos.

508 Matemática discre1a y sus aplicaciones

732-555-1001 732-555- 1001

732-555-4444 732-555-4444

732-555-9876 732-555-9876

732-555-6666 732-555-6666
(a) (b)

Figura 10. Un grafo de llamadas.

EJEMPLO 7 Grafos de llamadas Los grafos se pueden utilizar para representar las llamadas telefónicas he-
chas en una red, por ejemplo en una red telefón ica de larga distancia. En particular, puede usarse
Enlaces
un multigrafo dirigido para representar llamadas: cada vértice representa un número de teléfono y
cada arista representa una llamada. La arista que representa una llamada sale del número de telé-
fono desde el que se hace la llamada y llega al número de teléfono que la recibe.
La Figura 10(a) mues1ra un pequeño grafo de llamadas telefónicas que representa siete nú-
meros de teléfono. Este grafo muestra, por ejemplo, que se han hecho tres llamadas telefónicas
desde el 732-555-1234 al 732-555-9876 y dos en el sentido opuesto, pero que no se ha hecho lla-
mada alguna del 732-555-4444 a ninguno de los otros seis números, salvo al 732-555-001 1.
Cuando sólo nos importa si ha habido o no alguna llamada entre dos números. empleamos un gra-
fo no dirigido tal que una aiista conecta dos números de teléfono si se ha hecho alguna llamada en-
tre dichos 111ímcros. Esta versión del g rafo de llamadas se muestra en la Fig ura lO(b). ◄

Los grafos de llamadas que representan la actividad telefónica real pueden ser gigantesco .
Por ejemplo, un grafo de llamadas esrudiado en AT&T que representaba las llamadas hechas en un
período de 20 días tenía alrededor de 290 millones de vértices y 4 mi l millones de aristas. Habla-
remos más :icerca de los grafos de llamadas en la Sección 8.4.

EJEn1PLO 8 El grafo de la Red La Red de lnternet (en inglés, World Wide Weh) se puede repre entar por
medio de un gra fo dirigido en el que cada página web está representada por un vértice y en el que
una arista comienza en la página a y termina en la página h si hay un enlace en la página a que
lfolaces
conduce a la página b. Como cada segundo se crean páginas web nuevas y otras desaparecen, el
grafo de la Red se encuentra en estado de cambio perpetuo. El grafo de la Red tiene actualmente
más de mil millones de vértices y decenas de miles de millones de aristas. Hay muchas personas
estudiando las propiedades del grafo de la Red para entender mejor la naturaleza de la Red de In-
ternet. Explicaremos en el Capítulo 9 cómo utilizan los buscadores el grafo de la Red para crear ín-
dices de páginas web. ◄

s6
s, a:=0

S2 b := 1

S3 c:=a + 1

S., d:=b+a

Ss e :=d+ 1
Sh e :=c+d

s, Sz

Figura 11. Un grafo de precedencia.

 Grafos 509

EJ EMPLO 9 G rafos de precedencia y procesamiento concurrente Los programas informáticos pueden eje-
cutarse más rápidamente si ciertas sentencias se ejecutan simultáneamente. Es importante no
ejecutar sentencias 4ue rnquicran el resultado de sentencias aún no ejecutadas. La dependencia de
EnlacC'i
sentencias con respecto a sentencias previas se puede representar por medio de un grafo dirigido.
Cada sentencia se representa por un vértice. y hay una arista de un vértice a un segundo vértice si
la sentencia repre entada por el segundo vértice no puede ejecutarse hasta que la sentencia repre-
sentada por el primero se ha ejecutado. /\ este tipo <.le grafo se le llama grafo de precedencia. En
la f igura 11 se muestra un programa infonnático junto con su grafo. Por ejemplo. el grafo nos dice
que la sentencia S5 no se puede ejecutar hasta que S 1• S2 y S4 hayan sido ejecutadas. ◄

Problemas
l. Dibuja modelos de grafos, especificando el tipo de grafo 3. a h 4. a ____ b
que utiliws, para representar un sistema de rutas aéreas
en el que cada día hay cuatro vuelos de Boston a Ne-
wark. dos vuelos de Newark a Boston, tres vuelos de
Newark a Miami. dos vuelos de Miami a Newark, nn
vuelo de Newark a Detroit. dos vuelos de Detroit a Ne-
wark. tres vuelos de Newark a Washington. dos vuelos e d e d
de Washington a 1 ewark y un vuelo de Washington a s. 6. a b
Miami, de modo que
a) Hay una arista conectando cada p:ir de vértices que
representan ciudades para las que hay algún vuelo
de la una a la otra (en cualquiera de !os dos senti-
•e
d os).
b) llay una arista conectando dos ciudades por cada vue- e d
lo que opere entre la5 dos ciudades (en cualquiera de
los dos sentidos). 7. 8.
e) Hay una arista conectando dos ciudades por cada b
VL1e!o que opere entre !as dos ciudades (en cualquie- e
ra de los dos sentidos) más un bucle que representa
una excursión turística que despega y aterriza en
Miami.
a d b e
d) Hay una arista que sale de c<1da vértice asociado a e
una ciudad de la que despega algún vuelo y que llega
al vértice correl.pondiente a la ciudad en que aterriza 9.
el vuelo.
e) Hay una arista por cada vuelo, que sale del vértice
que representa a la ciudad en que se inicia el vuelo
y llega al vértice que representa a la ciudad en que
aterri7a.
2. ¿Qué tipo de gt fo se puede utilizar para representar un
sistema de auto istas entre grandes ciudades si
10. Para cada grafo no dirigido de los Problemas 3-9 que no
a) Hay una ar ta entre los vértices que representan a
sea grafo simple. halla un conjunto de aristas tal que si se
dos ciudades si hay una autopista que las conecta? elimin:rn esas aristas el grafo se convierte en simple.
b) Hay una arista entre los vértices que representan a
dos ciudades por cada autopist::i que las conecte? 11. El grafo de intersección de una colección de conjunto~
e) Hay una arisrn entre los vértices que representan a A1. /\2, •••• /\#es el grafo que tiene un vértice por cada con-
dos ciudades por cada autopis1a que las conecte y hay junto y que tiene una arista entre los vértices que repre-
un bucle en el vértice que represcnla a una ciudad si sentan a dos conjuntos si esos dos conjuntos tienen inter-
hay una autopista que rodea a la ciudad? sección no vacía. Constn1ye el grafo de intersección de las
siguientes coleccione de conjuntos:
En los Problemas 3-9, determina si el grafo que se muestra es
un grafo simple, un multigrafo (y no un grafo simple), un a) A, = 1O, 2. 4, 6, 8}. A 2 = {O, l. 2. 3, 4 J,
pseudografo (y no utl multigrafo), un grafo dirigido o un mul- A1 = { I, 3, 5, 7, 91,A, = (5, 6, 7, 8, 9) .
tigrafo dirigido (y no un grafo dirigido). A~={ 0,1,8,9)
5JO i\la1emá1ica d1~rc1a y sus aplicac1oncs

b) A 1 = 1... . -4. - 3. -2, - 1,0l, 20. Dibuja el grafo de llamadas para los números de teléfono
A, = { .... - 2. - 1. O, 1, 2, . .. }, 555-00I!,555- 1221,555- 1333, 555-8888.555-2222,555-
A~= { .... - 6, -4, - 2 . O. 2, 4. 6 .... }. 009 1 y 555- 12(X) si hubo tres llamadas del 555-001 1 ,ti
/\ = 1... , -5, - 3, - 1, 1. 3,5, ... ). 555-8888 y dos del 555-8888 al 555-001 1, dos llamadas
4
/\~= 1.. .,-6, 3.0.3,6, ... ), Jl:I 555-2222 al 555-0091, dos llamadas del 555-l221 a
e) /\ 1 = {xlx <O) cada uno de los demás números y una llamada del 555-
/\ = lxl- l <.r<O}. 1333 a cada uno de los números siguientes: 555-0011.
2
A,=lxlO< x< 1). 555- 1221 y 555- 1200.
A4 = {xj- 1 < x < l l, 21. Explica cómo se pueden utilizar dos grafos de llamadas,
A5 = {xlx> - II, uno con las llamadas hechas durante el mes de enero y el
A6 = R otro con las hechas durante el mes de febrero, para deter-
12. Utiliza el grafo de solaparnic1110 de nichos de la Figu- minar el nuevo número de teléfono de las personas que ha-
ra 6 para determinar las especies que compiten con los yan cambiado de número.
halcones. 22. a) Explica cómo se pueden utilizar los grafos para repre-
sentar los mensajes de correo electrónico en una red.
13. Construye un grafo de solapamiento de nichos para seis
b) Describe un grafo que represente los mensajes de
especies de pájaros si el zur,al compite con el petirrojo y correo electrónico enviados en una red a lo largo de
con el arrendajo, el petirrojo compite también con el sin-
una semana concreta.
sonte, el sinsonte compite también con el arrendajo y el
trepador compite con el pájaro carpintero. 23. ¿Cómo se puede utilizar un grafo que represente los men-
sajes de correo electrónico enviados en una red para en-
14. Dibuja un grafo que represente el que Tom y Patricia, contrar a per onas que hayan cambiado recientemente su
Tom y Hope, Tom y Sandy. Tom y Amy, Torn y Marika, dirección principal de correo electrónico?
Jeff y Patricia, Jcff y Mary, Patricia y Hope, Amy y Hope
y Amy y Marika se conocen. pero que ningún otro par de 24. ¿Cómo se puede utilizar un grafo que represente los men-
las personas enumeradas se conoce. sajes ele correo electrónico enviados en una red para en-
contrar listas de correo electrónico que se emplean para
IS. Podemos emplear un grafo para representar el hecho de enviar el mismo mensaje a muchas direcciones de correo
que <los persona e~tuvicran vivas al mismo iiempo. Di- electrónico distintas?
buja un grafo de este tipo que represente si cada dos ma-
25. Describe un grafo que represente matrimonios. ¿Tiene
temáticos o infonnáticos cuyai. biografías i.c incluyen en
este grafo alguna propiedad especial?
los cuatro primero capítulos <le este libro y que murieron
antes de 1900 eran o no contemporáneos (diremos que 26. ¡_Qué sentencias tienen que ejecutarse antes de ejecutar
dos personas estuvieron vivas :il mismo tiempo si hay al- S6 en el programa del Ejemplo 9? (emplea el grafo de pre-
gún año en que ambas personas estuvieron vivas). cedencia ele la rigura 11 ).

16. ¿Quién puede influir en Fred y a quién puede influir f-red 27. Construye un grafo de precedencia para el siguiente pro-
en el grafo de influencias del Ejemplo 3? grama:
S,: x :=O
17. Constmye un grafo de influencias para la junta directiva S, : X :=X+)
de una e111presa ~i el presidente puede influir en el director S~: y:= 2
de investigación y desarrollo, en el director de marketing y s.: z := y
en el director de operaciones; el director de investigación y S,: x := x + 2
desarrollo puede influir en el <lircctor de operaciones; el S6: y :=x + z
director de marketing puede influir en el director de ope- S7: : := 4
raciones, y nadie puede influir en el director financiero ni
tampoco ser inflo ido por é l.
2[. Describe una estructura discreta basada en un grafo que se
pueda utilizar para representar rutas aéreas y sus horarios de
18. ¿A qué otros equipos venció el Equipo 4 y qué equipo~ vuelo. (111dicación: Dota de estructura a un grafo dirigido).
vencieron al Equipo 4 en el torneo de todos contra todos
representado por el grafo de la Figura 9? 2. Describe una estructura discreta basada en un grafo que se
pueda utilizar para representar relaciones entre pares de in-
19. En un tomeo de todos contra todos, los Tigcrs vencieron a dividuos de un grupo suponiendo que cada individuo pue-
los íllue Jays, los Tigers vcm.:i.:ron a los Cardinals, los Ti- de serle simpático, antipático o indiferente a cada uno ck
gers vencieron a los Orioles, los Blue Jays vencieron a los los demás individuos y que las relaciones pueden no ser
Cardinals, los Blue Jays vencieron a los Orioles y los Car- recíprocas (Indicación: Dota de estructura a un grafo diri-
dinals vencieron n .los Orioles. Representa estos resultados gido. Trata por separado las aristas con direcciones opues-
usando un grafo dirigido. tas entre vérl ices que representen a dos individuos).
 Grafos 511

~i2 Ter1ninología en teoría de grafos

INTRODUCCIÓN
fotroclucimos en esta sección parte del vocabulario básico de la teoría de grafos. Utilizaremos este
Enlates vocabulario para re,solver muchos tipos distintos de problemas. Uno de ellos trata de detem1inar si
un grafo se puede dibujar o no en el plano de manera que sus aristas no se corten. Otro proble-
ma es el de decidir si hay alg\Jna biyección entre los vértices de dos grafos que dete1mine una
correspondencia biyectiva entre las a1istas de los grafos. También introduciremos varias familias
importantes de grafos que se usan con frecuencia en ejemplos y modelos.

TERMINOLOGÍA BÁSICA
Veamos en primer lugar Ja tenninología que describe los vértices y las aristas de los grafos no dirigidos.

DEFINICIÓN 1 Si'dic~ t}ue ·dos vértices -u y vdé nn grafo no dírigid,o G son adyacente; (o vecinos) en G si
{u, i1} es LtÍ1á arista' de G, Si e = 1u, v}, se dice qLie la arista e es incidente con los vértices u
-y v. También se ctiée que la á.ristá e coízecta u y v. Se dice que los vértices 1i y v son extremos
de lJ:l ari~ta é. -· - . ..

Para seguirle la pista a cuántas aristas son incidentes con un vértice, introducimos la siguiente de-
finición.

DEFINICIÓN 2 El gr_ado de un vértice de un grafo no dirigido es el número de ~ristas incidentes con él, ex-
ceptuandp los bucles, cada uno de los cuales contribuye con dos unidades al grado del vérti~
ce. El grado del vértice v se denota por o(v).

EJEMPLO 1 ¿Cuáles son los grados de los vértices de los grafos G y H que se muestran en la Figura l?

Solución: En G, ó(a) = 2, o(b) = 8(c) = o(j) = 4, o(d) = 1, ó(e) = 3 y ó(g) = O. En H , ó(a) = 4,

Ó(b) = ó(e) = 6, Ó(c) = 1 y ó(d) = 5. ◄

A los vértices de grado cero se les llama aislados. Claramente, un vértice aislado no es adya-
cente a ningún vértice. El vértice g del grafo G del Ejemplo 1 es un vértice aislado. Se dice que un
vértice es colgante, o que es una hoja, si, y sólo si, tiene grado uno. Por tanto, una hoja es adyacente
a exactamente un vértice distinto de ella. El vértice d del grafo G del Ejemplo l es una hoja.
¿Qué obtenemos cuando sumamos los grados de todos los vértices de un grafo G = (V, E)?
Cada_ari_sta con¡ibuye c?n_dos unidades a 1~ s_uma de los gra?os_de los vértices, ya que cada aris-
ta es 111c1dente c n dos vert1ces (posiblemente 1gu~les). Est(\s1gmfica que la suma de los grados ele·
los vértices es doble del número de aristas. Enunciamos este resultado en e l Teorema 1, al que
también se conoce como teorema de los apretones de manos, debido a la analogía entre los dos ex-
tremos que tiene cada arista y las dos manos que se estrechan cuando dos personas se saludan.

TEOREMA 1 EL T~OREMA DEJ,OS APRETONES DE MANOS Sea G = (V, E) un grafo no dirigido

con e aristas. E ntonces,
.. 2e =- ¿6(v).
,,ar Q

(Nótese que esto es cierto inch¡so cuando hay aristas múltiples y bucles en el grafo).
512 Maternáli,a discreta y sus aplicaciones

-b - - - -r - - - •d b e
(1

a f I!
•
g d

G JI

Figura 1. Los grafos no dirigidos G y //.

EJElVIPLO 2 ¿Cuántas aris tas hay en un grafo con diez vértices, cada uno de los cuales tiene grado seis?

Solurión: Como la suma de los grados de los vértices cs 6 · 10 =60, se sigue que 2e =60. Por tan-
to, e= 30. ◄

El Teorema I nos dice que la suma de los grados de los vértices de un grafo no diJigido e un
número par. Este hecho tiene muchas consecuencias, una de las cuales se da en el Teorema 2.

TEOREMA 2 Todo grafo no dirigido tiene un número par de vértices de grado impar.

/Jemostración : Sean V1 y V2 el w njunto de vértices de grado par y el conjunto de vértices de gra-

do impar, respectivamente, de un grafo no dirigido G =(V.E). Entonces.

2e = ¿ &(v) "" ¿ b(v) + ¿ b(v).

,·E:V •·EV1 ,·El'¡

Coniu o(1•) es par sir e V1• el primer sumando del término de la derecha de la última igualdad es
par. Además. la suma de los dos sumandos tic dicho 1é1111ino es par, puesto que esa suma es 2e. Por
tanto. el segundo sumando es también par. Como todos los ténninos que se suman en ese segun-
do sumando son impares. tiene que haber un número par de ellos. Por tanto. hay un número par de
vértices de grado impar. <]

La terminología para grafos dirigidos refleja el hecho de que a las aristas de un grafo dirigi-
do se les asigna un sentido.

DEFI 'ICIÓ 3 Si (u, v) es una arista del grafo dirigido G. se dice que u es adyacente a v y que ves adyaceme
desde u. Al vértice u se le llama vérííce inicial de (u, v) y a v se le llama vértice final o ter-
minal de (u, v). Los vértices ;n;cjaJ y final de un bucle coiciden.

Como las aristas de un grafo dirigido son pares ordenados, podemos refinar la definición de gra-
do de un vértice a fin de reflejar el número de aristas que tienen a ese vértice corno vértice inicial
o como vértice final.

DEFINl CIÓ1 4 En un grafo di.rígido, el grado de entrada de un vértice v, denotado por 6- (v), es el número de
aristas que tienen a v como vértice final. El grado de salida de un vértice v, denotado por
o+(v), es el número de aristas que tienen a v como vértice inicial (nótese que Uól bucle con-
tribuye con una unidad tanto al grado de entrada como al ,grado de salida del vértice corres-
pondiente).
 Grafos 513

d
•f
G

Figura 2. El grafo dirigido G.

E.J EMPlO 3 Halla los grados de cn1ra<la y de salida de cada vértice del grafo dirigido G que se muestra en la Figura 2.

Solución: Lo grados de entrada de G son: S (a)= 2, 6-(b) = 2, 6-(c) = 3. ◊-(d) = 2, 6-(e) = 3 y 6-(j)
= = =
=O.Los grados de salida son: ó+(a) 4, ó+(b) = ! , ó+(c) 2, ó+(d) 2, ó+(e) = 3 y ó+(J) O. =
◄

Como cada arista tiene un vértice inicial y un 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 coinciden. Ambas sumas
son iguales al número de ari 1as que tiene el grafo. Enunciamos este resultado como Teorema 3.

TEOREMA 3 Sea G = (V, E) un grafo dirigido. Enlonces ,

_¿Ó-(v)+ _¿ O+(v) =I EJ .
,-e; ,,a,

Hay muchas propiedades de un grafo tliJ igitlu que no dependen de la dirección de sus aristas. ·
En consecuencia. a veces conviene ignorar esas direcciones. Al grafo no dirigido que resulta de ig-
norar las direcciones de las aristas se le llama grafo no dirigido ubyacente. Un grafo dirigido y
su grafo no dirigido s11byace111e tienen el mismo número de aristas.

FAMILIAS DISTINGUIDAS DE GRAFOS SIMPLES

Introduciremos a co111inuación varias clases de grafos simples. Estos grafos se usan con frecuen-
cia como ejemplos y aparecen en muchas aplicaciones.

EJEMPLO4 Grafos completos El grafo completo de 11 vértices, que se denota por K., es el grafo simple que
contiene exactamen1e una arista entre cada par de vértices dislintos. En la Figura 3 se muesrran los
grafos K,, para 11 = 1, 2. 3, 4. 5, 6. ◄

EJEM PLO 5 Ciclos El ciclo c., n 2: 3, consta den vértices v" 1·2, .•. , v. y aristas Iv 1, 112 ), 11•2, vJ, .... 11·n 1, 1·.f
y ( v", v1) . En la f-igura 4 se mut'lran los ciclos C1, C4, C5 y C6. ◄

EJEMPLO 6 Ruedas Obtenemos la rueda n

cuando añadimos un vért ice ad icional al ciclo C,
n
parn 11 2: 3. y
conectamos este nuevo vértice c n cada uno de los n vértices de Cn mediante uné'l nueva arista. En
la Figura 5 se muestran las ruedas Wv w_P W 5 y W 6. ◄

• - -- •
K5 K6

Figura 3. Los grafos K. parn 1 ,, ns 6.

514 Matemática discreta y sus aplicaciones

e_\

Figura _S. Las ruedas W 3 , W4 , W 5 y W 6 .

EJEMPLO 7 11-Cubos EL cubo n-dimensional, o n-cubo, denotado por Q", es el grafo cuyos vértices repre-
sentan las 2" cadenas de bits de longitud n. Dos vértices son adyacentes si, y sólo si, las cadenas ele
bits a las que representan difieren exactamente en un bit. En la Figura 6 se muestran los grafos Q •
1
Q2 y Q 3• Nótese que se puede construir el (n + 1)-cubo Qn+l a partir del n-cubo Q" haciendo dos co-
p.ias de Q,,, anteponiendo un O a cada una de las etiquetas de los vértices de una de las copias de
Q,,, anteponiendo un l en la otra copia y añadiendo aristas que conecten dos vértices cuyas eti-
quetas se diferencien únicamente en el primer bit. En la Figura 6, Q3 se construye a partir de Q 2 co-
locando dos copias ele Q 2 como las caras superior e inferior de Q3, añadiendo un O al principio de
la etiqueta de cada vértice de la cara inferior y añactiendo un 1 al principio de la etiqueta de cada
vértice de la cara superior. ◄

GRAFOS BIPARTITOS
Hay ocasiones en que un grafo tiene la propiedad de que su conjunto ele vértices se puede dividir
L nlam; en dos subconjuntos disjuntos tales que cada arista conecta un vértice de uno de esos subconjun-
tos con un vértice del otro subconjunto. Por ejemplo, consideremos el grafo que representa ma-
trimonios entre las personas de un pueblo. En él, cada persona se representa mediante un vértice y
cada matrimonio se representa mediante una arista. Además, cada arista conecta un vértice del sub--
conjumo de vértices que representan a los l10111bres con un vértice del subconjunto de vértices que
representan a las mujeres del pueblo. Esto nos lleva a la Definición 5.

DEFINICIÓN 5 su
Se dié~ que 1m grafo-simple Ges bipárttto si conjünto de vértices V se puede diyidir en dos
conjuntos disjuntos V1 y V2 ta]eif que cada arista del grafo conecta un vértice de v; con.un vér-
tice de \/2 (de ~a!1era que _no haya ninguna arista que conecte entre' sí-ros
vérti.ces de V1 ni
tampoco dos verilees de V2) . _ .• · _ , , · · ·
. . . ~- .
.
.. -~. . ,
.
. .

110 111

JO 11 100 lOJ

□
•
o •1 010
011

00 01 000 001

Q¡ Q2 Q,

Figu ra 6. Los 11-cubos Q,, para n = 1, 2 y 3.

 Grafos SIS

a a

e d l' d

e 11

Figura 7. El ciclo C6 es biparti10. Figura 8. Los grafos no dirigidos G y H.

Veremos en el Ejemplo 8 que C6 es bipartito y en el Ejemplo 9 que K 3 no es bipartito.

EJEMPLO 8 C6 e bipartito, como se muestra en la Figura 7, ya que su conjunto de vértices puede dividirse en
dos conjuntos, V1 = 1v., v3, v5 ) y V2 = ( v2, v4, v6 }, y cada arista de C6 conecta un vértice de v, con
un vértice de V2 • ◄

EJEMPLO 9 K3 no es bipartito. Para verlo, nótese que si partimos el conjunto de vértices de K 3 en dos conjun-
tos disjuntos, uno de los dos conjuntos debe contener dos vértices. Si el grafo fuese bipartito, esos
dos vértices no podrían estar conectados por ninguna arista, pero en K3 cada vértice está conecta-
do con cualquier otro vértice por medio de una arista. ◄

EJEMPLO 10 ¿Son bipartitos los grafos G y H que se muestran en la Figura 8?

Solución: El grafo Ges bipartito, puesto que su conjunto de vértices es la unión de dos conjuntos
disjuntos, {a, b, d) y {c. e.f g 1. y cada arista conecta un vértice de uno de estos subconjuntos con
un vértice del otro subconjunto (nótese que para que G sea bipartito no es necesario que cada vér-
tice de {a . b, d) sea adyacen1e a nn vértir.~ rle (e, e,f, g) . Por ejemplo, by 8 no son adyacent~s).
El grafo// no es bipartito. ya que su conjunto de vértices no se puede dividir en dos sub-
conjuntos de modo que las aristas no conecten ningún par de vértices de un mismo subconjunto (el
lector debería comprobarlo considerando los vértices a, by j). ◄

Un grafo es bipa11ito si, y sólo si. se pueden colorear los vértices del grafo con dos colores de
modo que ningún par de vértices adyacentes sean del mismo color. Estudiaremos el coloreado de
grafos en la Sección 8.8. También un grafo es bipartito si, y sólo si, es imposible comenzar en un
vértice y regresar a ese mismo vértice después de recorrer un número impar de aristas distjntas. Pre-
cisaremos más estas nociones en la Sección 8.4 cuando hablemos de caminos y circuitos en grafos.

EJEMPLO 11 Grafos bipartitos completos El grafo bipartito completo K es el grafo cuyo conjunto de vér-
tices está formado por dos subconjuntos con m y II vértices, resp;ctivamenlc, y hay una arista entre
dos vértices si, y sólo si, un vértice está en el primer subconjunto y el otro vértice está en el segun-
do subconjunto. En la Figura 9 se muestra los grafos bipartitos completos K2_3 , K3_3, K3_5 y K2. 6• ◄

AA 1

K3,5

Figura 9. Algunos grafos comple10s bipartitos.

516 Ma1cmá1ica discreta y sus aplicaciones

ALGUNAS APLICACIONES DE TIPOS ESPECIAL.ES DE GRAFOS

Vamos a ver cómo se utilizan algunos tipos especiales de grnfos en modelos para la conmnicación
de datos y el procesamiento en paralelo.

EJEMPLO 12 Redes de área local Los ordenadores que hay en un nüsmo edificio, al igual que los periféricos,
como impresoras o trazadores gráficos, se pueden conectar entre sí por medio de una red de área
local. Algunas de estas redes se basan e n una 1opofogía en es1re!la, en la que tocios los dispositi-
Enláccs ·
vos están conectados a un dispositivo central de control. Puede representarse una red de área local
usando un grafo bipartito completo K 1_,,, como se muestra en la Figura lO(a). Los mensajes se en-
vían de máquina a máquina a través del dispositivo central de control.
Otras redes de área local se basan en una topología en anillo, en la que cada dispositivo seco-
necta con exactamente otros dos. Las redes ele área local con topología en anillo se representan uti-
lizando ciclos Cn, como se muestra en la Figura lü(b). Los mensajes se envían ele máquina a má-
quina siguiendo el ciclo hasta que se alcanza el dispositivo que debe recibir el mensaje.
Finalmente, algunas redes de área local emplean un híbrido de ambas topologías. Los men-
sajes se pueden enviar a lo largo del anillo o a través de un dispositivo central. Esta redundancia
hace que la red sea más fiable. Las redes de área local con este tipo ele redundancia se pueden re-
presentar por medio de ruedas Wn. como se muestra en la Figura IO(c). ◄

EJEMPLO 13 Redes de interconexión para el cálculo en paralelo Hasta hace poco, los ordenadores ejecu-
taban los programas realizando las operaciones una a una. En consecuencia, los algoritmos que re-
solvían los problemas estaban diseñados para llevar a cabo un solo paso cada vez. Este tipo de al-
goritmos son lo que se conoce como algoritmos secuenciales (casi todos los algoritmos descritos
e n este libro son secuenciales). Sin embargo, muchos problemas cuya resolución es computacio-
nalmente muy costosa, como la simulación climatológica, el tratamiento de imágenes en medici-
na y el criptoanálisis, no pueden resolverse e n un período razonable ele tiempo por medio de ope-
raciones secuenciétles, ni siquiera utilizando un superordenador. Además. hay un límite físico para
la velocidad a la que un ordenador puede realizar las operaciones básicas, de modo que siempre
habrá problemas que no se puedan resolver en un pe1íodo razonable de tiempo mediante opera-
ciones secuenciales.
El procesamiento en paralelo, que utiliza ordenadores construidos con muchos procesado-
res distintos, cada uno con su propia memoria. ayuda a superar las limitaciones de los ordenadores
secuenciales. Pueden diseñarse algoritmos en paralelo para resolver problemas con rapidez
usando un ordenador con múltiples procesadores. Estos algoritmos dividen un problema en varios
subproblemas que se pueden resolver al mismo tiempo. En un algoritmo en paralelo, la ejecución
del algo1ilmu es controlada por un único flujo de instrucciones, que envfa subproblemas a los dis-
tintos procesadores y dirige los datos de entrada y de salida efe estos subproblemas al. procesador
apropiado.
Cuando se procesa en paralelo puede que un procesador necesite como dato ele entrada la sa-
lida de otro procesador. Por tanto, estos procesadores tienen que estar interconectados. Podemos
utilizar un tipo adecuado ele grafo para representar la red de interconexión de los prijcsadorcs de
un ordenador con procesadores múltiples. A continuación, vamos a describir los ti os más fre-
cuentes de redes ele interconexión para procesadores en paralelo. El tipo de red de i te rconexión

(a) (b) (e)

Figura 10. Topologías en estreUa, en anillo e híbrida para redes de área local.
 Grafos 517

P(O. O) P(O. 1) P(O, 2) P(O. 3)

/>( 1, O) P( I. 1) P( l. 2) P(I, 3)

P(2. O) P(2, 1) P(2. 2) P(2. 3)

I'¡ P2 ~ P,, P5 p6
P(3, 0) P(3. 1) P(3, 2) P(3, 3)
• • • • • •
Figura 11. Una disposición lineal con _Figura 12. Una red de malla con
seis proces.idorcs. 16 procesadores.

que se use para implementar un algorilmo en paralelo concreto depende de las necesidades de in-
tercambio de datos c111re los procesadores, la velocidad deseada y, por supuesto, del hardware dis-
ponible.
La red de interconexión de procesadores más sencilla, pero también la más costosa, incluye
un enlace bidireccional entre cada par de procesadores. Esta red se puede representar por medio de
K., el grafo completo den vénices, donde n es el número de proce adores. Sin embargo, este tipo
de red de interconexión presenta serios problemas debido al gran número de conexiones que re-
quiere. En la práctica, el número de conexiones directas con un procesador es limitado, de modo
que si hay gran número de procesadores, cada uno de ellos no puede conectarse directamente con
todos los demás. Por ejemplo, si hay 64 procesadores, harían falt a C(64, 2) = 2.016 conexione~ y
cada procesador tendría que estar directamente conectado con otros 63.
Por otra parle, quizá la manera más senc illa de conectar entre sí n procesadores es utilizar lo
que <;e c-onoce corno una disposición lineal (en inglés. linear array). Cada procesauor P, que no
sea P 1 ni Pn está conectado con sus vecinos P;_, y P;+i mediante un enlace bidireccionaJ. P1 está co-
nectado ólo con P2 y Pn lo está sólo con P,,_ 1• En la Figura 11 se muestra la disposición lineal con
seis procesadores. La ventaja de una disposición lineal es que cada procesador tiene a lo sumo do.
conexiones directa con otros procesadores. La desventaja es que a veces hace falla empicar un
gran número de enlaces intermedios. llamados saltos, para que los procesadores compartan la in-
formación.
La red de malla o disposición bidimensional (en inglés, mesh nernwk) es una red de inter-
conexión que se emplea a menudo. En esta red, el número de procesadores es un cuadrado perfecto,
digamos n = rri2. Los n procesadores se etiquetan como P(i, j), Os i s m - 1. O s j s m - 1. El pro-
cesador P(i.J) está conectado mediante enlaces bidireccionales con sus cuatro vecinos, P(i ± I.J)
y P(i. j ± 1), a no ser que alguno de estos procesadores no esté en la malla (nó1ese que hay cuatro
procesadores, los de las esquinas de la malla. que sólo tienen dos procesadores aclyacen tcs, y otros
procesadores del borde tienen sólo tres vecinos. A veces se usa una variante de la red ele malla en la
que cada procesador tiene exactamente cuatro conexiones: véase el Problema 52 al final ele esta sec-
ción). La red de malla limita el número ele enlaces para cada procesador. La comunicación entre es-
tos procesadores requiere O(✓n) = 0 (111) enlaces intem1edioi (véase el Problema 53 aJ final de esta
sección). En la Figura 12 se muestra el grafo que represen! la red de malla con 16 procesadores.
Un tipo jmportantc de recl ele interconexión es el hipe cubo. En esta red, el número de pro-
cesadores, n = 2m. es una potencia de 2. Los n procesado s se etiquetan corno P0 • P 1, •••• 1\ 1•
Cada procesador tiene conex iones bidireccionales con otros m procesadores. El procesador P,
está conectado con los procesadores cuyo índice tiene una representación binaria que difiere de
la representación binaria de i exactamente en un b.il. La red de hipercubo logra un equilibrio en-
tre el número de conexione directas para cada procesador y el número de conexiones intenne-
dias que . e requieren para que los procesadores puedan comunicarse entre sí. Se han construido
muchos ordenadores empicando una red de hipercubo y se han ideado muchos algorilmos en pa-
ralelo que utilizan una red de hipercubo. El grafo Q . el 11-cubo. representa a la red de hipercu-
bo con n procesadores (la f igura 13 muestra una fo~ a de dibujar QJ distinia a ia que vimos en
la Figura 6).
518 Matemática discreta y sus aplicaciones

a a

" e e

Figura 13. Una red de hipercubo con ocho procesadores. Figura 14. Un subgrafo de K5'

GRAFOS DEFINIDOS A PARTIR DE OTROS

Hay ocasiones en que sólo necesitamos pat1e de un grafo para resolver un problema. Por ejemplo,
puede que sólo estemos interesados en aquella pat1e de una gran red informática que involucre los
centros informáticos de Nueva York, Denver, Detroit y Atlanta. En ese caso, podremos ignorar to-
dos los demás centros infonnáticos, así como las lír.e:is telefónicas que no conecten entre sí dos de
esos cuatro centros informáticos. En el grafo que representa la red total podemos eliminar los vér-
tices que corresponden a todos los centros informáticos, salvo los cuatro en los que estamos inte-
resados, y podemos suprimir todas las aristas que son incidentes con alguno de los vértices des-
cartados. Una vez eliminados estos vértices y aristas del grafo, sin eliminar ningún extremo de las
aristas que quedan, se obtiene un grafo más pequeño. Se dice que este grafo es un subgrafo del
grafo original.

DEFJNlCIÓN 6

EJEMPLO 14 El grafo G que se muestra en la Figura 14 es un s ubgrafo de K5 .

◄
Podemos combinar dos o más grafos ele varias furrnas. El nuevo grafo que contiene todos los
vértices y todas las aristas de estos grafos se llama unión de los grafos. Veamos una definición
más formal para la unión de dos grafos simples.

DEFINICIÓN 7 l:.a unión de.dos gráfÓs ·sjrnpJ~ G1;=, (V1, E 1) y G2 d cis, E2) es.~l grafo.simple cuyo conjunto
de vét1ices-e:- V¡ U V2 y c~1yo conj unto d~ aristas es E1 U_E 2 . t a.unión de 0 1 y G2 se denota por
Gl u ª2· . . . , . : . . . ... . "'; ., :•· ,_, . . . >

EJEMPLO 15 Halla la unión de los grafos G 1 y G 2 que se muestran en la Figura 15(a).

Solución: El conjunto de vé1tices ele la unión G 1 U G 2 es la unión de los dos conjuntos de vértices, 1
a saber, la, h. e, d, e,f) . El conjunto de aristas de la unión es la unión de los dos conjuntos de aris-
tas. La unión se muestra en la Figura 15(b).
a b e a b e
a b e

07
d e

G1
d f
" e f

(a) (b)

Figura 15. (a) Los grafos símples G 1 y G 2; (b) Su unión G 1 U G2 •

 Grafos 519

Problemas
En los Problemas 1-3, halla el número de vértices, el número I O. Para cada uno de los grafos de los Problemas 7-9, de-
de aristas y el grado de cada vértice del grafo no dirigido co- tennina la suma de los grados de entrada y la suma de
rrespondiente. ldentifica todos los vénices aislados y las hojas. los grados de salida de los vértices. Comprueba que
ambos son iguales al número de aristas que hay en el
l. b d grafo.

11. Construye el grafo no dirigido subyacente para el grafo

dirigido de la Figura 2.

a / e
•
g
12. ¡,Qué representa el grado de un vértice en el grafo de
conocidos cuyos vértices representan a todas las personas
G
del mundo? ¿Qué representan los vénices aislados y las
hojas? En un estudio se estimó que el grado promedio de
2. b un vértice ele este grafo es 1.000. ¿,Qué significa esto en
términos del modelo?

13. ¿Qué representa el grado de un vér1ice en un grafo de co-

laboración? ¿Qué representan los vértices aislados y las
hojas?
e
(' d
14. ¿Qué representa el grado de un vértice en el grafo de
3. Hollywood? ¿,Qué representan los vértices aislados y las
d hojas?
•
15. ¿,Qué represenlan el grado de entrada y el grado de salida
de un vértice en un grafo de llamadas telefónicas como el
•
f h g e
descrito en el Ejemplo 7 de la ~ecc1ón 8.1? ¿Qué repre-
senta el grado de un vértice en la versión no dirigida de
este grafo?
4. Halla la suma de los grados de los vértices para cada
grafo de los Problemas 1-3 y comprueba que coincide 16. ¿Qué representan el grado de cmrada y el grado de salida
con el doble del número de aristas del grafo. tic un vértice en el grafo de la Red descrito en el Ejem-
plo 8 de la Sección 8.1?
S. ¿,Puede existir un grafo con 15 vértices. cada uno de
ellos de grado 5? 17. ¿Qué representan el grado de entrada y el grado de salida
de un vértice en un grafo dirigido que represente un tor-
6. Para cada una de las personas que asisten a un.1fiesta se
neo de todos contra todos?
considera el número de persona\ a las que ha saludado
dándoles la mano. Demuestra que la suma de todos esos 18. Dibuja lo:. siguientes grafos
números es un número par. Se supone que nadie se da la
a) K 7 b) K 1_8
mano a sí mismo.
d) C7 e) W7
En los Problemas 7-9, determina el número de vértices y de
aristas y halla los grados de entrada y de salida de cada uno de En los Problemas 19-23. detennina si cada uno de los grafos es
los vértices del mul1 igrafo dirigido correspondiente. o no bipartito.

7. 8. 19. a b 20. b e
b ll b

X
a

a d

o
d ,· e ,1 e

9. 21. b e

a d

f e
520 Matemática discreta y sus uplicac.:iones

h
3-t Sea C un grafo con v vértices y e aristas. Sea M el máxi-
mo grndo entre los vértices de G y sea m el mínimo gra-
do entre los vértice~ de C . Demuestra que
a) 2e/1· ~ m
b) 2e/v s M.
Se dice que un grafo simple es regular si todos los vértices del
e grafo tienen el mismo grado. Se dice que un grafo regular es 11-
rcgular si todos los vértices del grafo tienen grado 11.
23. b
35. ¡.Para qué valores de n son regulare:, los siguientes
('
grafo~?
(/

a ) K. b) C. e) IV. d) Q.

36. ¡,Para qué valores de m y n es regular K,,, ;,

f el 37. ¿Cuántos vértices tiene un grafo regular de grado 4 con
1O aristas?
e En los Prohlemas 38-40. haJla la unión del correspondiente
par de grafos simples (supón que dos ari~tas con los mismos
24. ¿Para qué valores de II son bipartitos los siguientes grafos? extremos son iguales)_
a) K11 b) c. e) W11 d) Q" 38. ll

25. ¿Cuántos vértices y cuántas aristas tiene cada uno <le es- b
tos grafos? f b

a) K. b) Cn
d) K"' 11 e) Q,, e ('

26. ¿Cuántas aristas tiene un grafo si los grados <le su~ v.:11i-
ces son 4, 3. 3, 2, 2? Dibuja un grafo que verifique lo an- d d
terior.
39.
27. ¿Cuántas arista~ tiene un grafo si los grados de sus vérti-
ces son 5. 2. 2. 2. 2, I'! Dibuja un grafo que verifique lo
anterior.
28. ¿Existe algún grafo simple <le seis vértices con los grados
siguientes? Si es así, dibuja un grafo con esa propiedad. (' d r g
a) O. l. 2. 3. 4. 5 b) l. 2. 3. 4, S. 6
e) 2,2.2. 2, 2,2 d) 3,2, 3, 2. 3.2 40. a b /1 e
e) 3. 2. 2. 2, 2, 3 1) 1, 1, 1, 1, J, l
g) 3. 3. 3, 3, 3, 5 h) 1, 2, 3, 4, 5, 5
29. ¿Existe algún grafo simple de cinco vértices con los gra-
dos siguierncs'? Si es así, <libuja un grafo con esa propie-
da<l. f 8
a) 3. 3, 3. 3. 2 b) 1,2,3, 4, 5
e) 1, 2, 3, 4, 4 d) 3,4. 3, 4,3 4]. El grafo complementar io C de un grafo simple G tiene
e) O. J, 2, 2. 3 0 1, 1, 1.l. l los mismos vértices que C. Dos vén ices son adyacentes
en 0 si, y sólo si, no son adyacentes en G. Halla los si-
30. ¿Cuánto~ subgrafos rnn al menos un vértice tiene K~? guientes grafos.
a) K b) Km , n e) c. el) Qn
1
31. ¿Cuántos subgrafos con al menos un vértice tiene K/ 11

32. ¿Cuántos subgrafcs con al menos un vértice tiene W~? -U. Si G es un grafo simple con 15 aristas y G tiene 13 afr,-
tas. ¿cuántos vérticc:s tit:ne G?
33. Dibuja todos los subgrafos del siguiente grafo.
43. Si el grafo simple G tiene v vértices y e aristas. ¿cuántas
11 b
aristas tiene G?
*4-1. Demuestra que si G es un grafo hipartito simple con r
vért ices y e aristas, entonces e :s; 1•2/4_
45. Demuestra que si G es un grafo simple con II vértices,
e d entonces la unión de G y Ges Kn.
 Grafos 521

*46. Describe un algoritmo para decidir si un grafo es o no bi- 51. Dibuja la red de malla para conectar en paralelo nueve
partito. proce~adores.
El recíproco de un grafo dirigido G = (V, E), que se denota G' ,
es el grafo dirigido (V, F) 1al que (11. v)e F si, y sólo si. (1•, u) E E. 52. En una variante de una red de malla, para conectar entre
sí n = m2 procesadores. el procesador P(i, j) está conec-
47. Dibuja el recíproco ele cada uno de los grafos de lo~ Pro- tado con los cuatro procesadores P((i ± ! ) mod m, j),
blemas 7-9 de la Sección 8. 1. P(i, U± 1) mod m), de modo que la~ conexiones rodean
los bordes de la malla. Dibuja esta variante de la red de
48. Demuestra que (G Y= C para todo grafo dirigido G. malla para 16 procesadore .
49. Demuestra que el graío G coincide con su propio recí- 53. Dcmue traque se puede comunicar cada par de procesa-
proco si, y sólo ~i. la relación asociada a C (véase la dores de una red de malla con 11 = m 1 procesadores utili-
Sección 7.3) es simétrica. zando 0(,/n) = O(m) saltos entre procesadores conecta-
dos directamente.
50. Extiende la definición de recíproco de un grafo dirigido a
la noción de recíproco de un multigrafo dirigido.

8.3 Representación de grafos e isomorfismo de grafos

I TRODUCCIÓN
Hay muchas maneras útiles de representar los grafos. Como veremos a lo largo de este capítulo, al
trabajar con un grafo conviene tener la posibilidad de elegir su representación más conveniente. En
esta sección veremos cómo representar grafos de vnrin~ maneras dis1in tas. .
A veces. dos grafos 1ienen exactamente la misma fonna, en el sentido de que hay una bi-
yccción entre sus conjunto de véniccs que preserva las aristas. En tal caso, decimos que los dos
grafos son isomorfos. El dc1erminar si dos grafos son isomorfos o no es un problema importante
en la teoría de grafos que estudiaremos en esta sección.

REPRRSENTACIÓ DE GRAFOS
Una forma de representar grafos sin aristas múltiples es enumerar tocias las aristas del grafo. Otra
fonna de representar grafos sin aristas múltiples es utilizar listas de adyacencia, que especifican
los vértices que son adyacentes a cada uno de los vértices del grafo.

EJEMPLO 1 Utiliza listas de adyacencia para describir el grafo simple de la Figura 1.

Sof11ció11: La Tabla I lista los vértice, que son adyacentes a cada uno de los vértices del grafo. ◄

EJEMPLO 2 Representa el grafo dirigido ele la Figura 2 enumerando lodos los vértices que son vét ices finales
de las aristas que salen ele cada uno de los vénices del grafo.

Solución: La Tabla 2 representa el grafo dirigido que se muestra en la Figura 2. ◄

MATRICES DE ADYACENCIA
Ejecutar algoritmos para grafos utilizando la representación de los grafos por medio de listas <le
ari tas. o por medio de listas de adyacencia. puede ser complicado si el grafo tiene muchas aristas.
Para simpli ficar lo cfüculo , conviene repre cotar los grafos por medio de matrices. Presentaremos 0

dos tipos de matrices que se utilizan con frecuencia para representar grafos. Uno se lYasa en la ad-
yacencia de vértices y el otro se basa en la incidencia entre vénices y aristas.