resert

´
Arboles

pr
eli
m
in
ar

Cap´
ıtulo 9

La de los Bernoulli de Basilea es, quiz´s, la familia m´s famosa de las Matem´ticas.
a
a
a
Nicolaus (1623-1708)

Nicolaus (1662-1716)

Jacob (1654-1705)

Johann (1667-1748)

Daniel (1700-1782)

Ve
rs
i´n
o

Nicolaus I (1687-1759) Nicolaus II (1695-1726)

Johann III (1744-1807)

Johann II (1710-1790)

Daniel II(1751-1834)

Jacob II (1759-1789)

Famosa por la cantidad de excelentes matem´ticos que “produjo” (hasta ocho, los que
a
aparecen en negrita en el esquema anterior, en tres generaciones distintas) y, tambi´n, por
e
la especial personalidad de algunos de ellos. De algunos de los m´s destacados ya hemos
a
hablado en cap´
ıtulos anteriores (Daniel, p´gina 508, y Jacob, p´gina 535). Lo que aqu´ nosa
a
ı
interesa es, precisamente, la manera en que hemos exhibido la informaci´n sobre la familia,
o
su ´rbol geneal´gico. Es un grafo, donde los v´rtices van etiquetados con los nombres de los
a
o
e
componentes de la familia, que tiene una estructura especial.
En muchas otras cuestiones utilizamos estas estructuras arb´reas
o
para representar informaci´n. La imagen que mostramos a laizo
quierda resultar´, sin duda, familiar: se trata de la descripci´n que
a
o
del contenido de un ordenador muestra el Explorador de Windows.
Aqu´ las etiquetas de los v´rtices son los nombres de los distintos
ı,
e
dispositivos. Pero de nuevo la estructura es especial: se trata de
un ´rbol. El cap´
a
ıtulo que aqu´ comienza est´ dedicado al estudio
ı
a
de estos objetos y a suaplicaci´n a diversas cuestiones: problemas
o
de optimizaci´n (secci´n 9.2), dise˜o de algoritmos (secci´n 9.3),
o
o
n
o
an´lisis de juegos (secci´n 9.4), etc.
a
o
631

´
Cap´
ıtulo 9. Arboles

632

9.1.

Definici´n y caracter´
o
ısticas

pr
eli
m
in
ar

La primera definici´n de la noci´n de ´rbol (de las varias que daremos) es la sugerida por
o
o
a
los ejemplos vistosanteriormente:
Definici´n 9.1 Un arbol es un grafo conexo y sin ciclos.
o
´

En el mismo tono bot´nico, se define un bosque como un grafo sin ciclos (si es conexo, ser´ un
a
a
´rbol; si no lo es, sus componentes conexas ser´n ´rboles). Por ejemplo, los grafos lineales
a
a a
a
Ln son ´rboles, mientras que los circulares Cn o los completos Kn no lo son en cuanto n ≥ 3.
Los bipartitoscompletos Kr,s , que son siempre conexos, s´lo son ´rboles si s = 1 ´ r = 1 (si
o
a
o
r ≥ 2 y s ≥ 2 hay al menos un ciclo de orden cuatro).
Esta primera definici´n no recoge una de las caracter´
o
ısticas fundamentales de los arboles,
´
que los hace especialmente utiles en ciertas cuestiones: son los conexos “m´s baratos” (en
´
a
cuanto al n´mero de aristas) que podemos tener. Los siguientesenunciados nos proporcionan
u
caracterizaciones alternativas que recogen esta idea:
Proposici´n 9.1 Un grafo G es un ´rbol (un conexo sin ciclos) ⇐⇒ Es conexo y tiene la
o
a
propiedad de que al eliminar una arista cualquiera del grafo, ´ste deja de ser conexo.
e

Ve
rs
i´n
o

´
Demostracion. En un sentido, supongamos que tenemos un grafo G conexo y sin ciclos.
Queremos probar quese desconecta al quitar una arista cualquiera.
Sea a una arista de G y formemos el grafo G \ {a} elimin´ndola. Si G \ {a} fuera conexo,
a
podr´
ıamos conectar en G\{a} los v´rtices de a. Pero a˜adiendo la arista a, lo que tendr´
e
n
ıamos
ser´ un ciclo en G (contradicci´n). As´ que G \ {a} es no conexo (sea cual sea la arista a de
ıa
o
ı
G que elijamos).
En el otro sentido, supongamosque G es un grafo conexo que se desconecta si quitamos
cualquier arista. Si el grafo contuviera un ciclo, siempre podr´
ıamos quitar una arista de ese
hipot´tico ciclo sin que el grafo dejara de ser conexo, lo que una contradicci´n. Luego ese tal
e
o
1.
ciclo no puede existir
Proposici´n 9.2 Un grafo G es un ´rbol (un conexo sin ciclos) ⇐⇒ No tiene ciclos y, si
o
a
a˜adimos una arista...