GRAFOS

´
Indice general
1. T´cnicas de conteo
e
1.1. Introducci´n . . . . . . . . . . . . . . . .
o
1.1.1. Propagaci´n de virus inform´ticos
o
a
1.2. Principio de la multiplicaci´n . . . . . .
o
1.3. Principio de la suma . . . . . . . . . . .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
..

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

3
3
3
4
4

2. Notaci´n factorial
o

5

3. Coeficientes binomiales
3.1. Identidad de Simetr´ . . . . . . . . . . . . . . . . . . . . . . . . . . .
ıa

7
7

4. Coeficientes binomiales y el tri´ngulo de Pascal
a
9
4.1. Teorema de Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5.Permutaciones

11

6. Permutaciones con repetici´n
o

13

7. Combinaciones

15

8. El principio de la pichonera

17

9. Teor´ de grafos
ıa
9.1. Grado . . . . . . . . . . . . . . . . . .
9.2. Conexi´n . . . . . . . . . . . . . . . . .
o
9.3. Los puentes de Konigsberg, Multigrafos
9.4. Grafos especiales . . . . . . . . . . . .
9.5. Matrices y grafos . . . . . . . . . . . .
9.6.Grafos etiquetados . . . . . . . . . . .
1

. . . . . . .
. . . . . . .
recorribles .
. . . . . . .
. . . . . . .
. . . . . . .

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

19
20
21
23
26
28
30

´
INDICE GENERAL

2
10.Grafosplanos, coloraciones, arboles
10.1. Mapas, regiones . . . . . . . . . . . . . .
10.2. Formula de Euler . . . . . . . . . . . . .
10.3. Grafos no planos, teorema de kuratowski
10.4. Grafos coloreados . . . . . . . . . . . . .
10.5. Arboles . . . . . . . . . . . . . . . . . .
10.6. Arboles con raiz . . . . . . . . . . . . . .
10.7. Arboles con ra´ ordenados . . . . . . . .
ız

.
.
.
.
..
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

31
31
33
33
34
38
41
43

Cap´ıtulo 1
T´cnicas de conteo
e
1.1.
1.1.1.

Introducci´n
o
Propagaci´n de virus inform´ticos
o
a

A fines de los 90, un virus de computadora llamado Melissa caus´ estragos al acabar
o
con los recursos del sistema. El virus se esparci´ por un correo electr´nico que cono
o
ten´ un archivo adjunto de procesador de texto con un macro maligno. Cuando se
ıa
abr´ el documento, el macroreenviaba el mensaje junto con el archivo del documenıa
to a las primeras 50 direcciones obtenidas de la libreta de direcciones del usuario.
Cuando se recib´ estas copias y se abr´
ıan
ıan, el macro nuevo reenviaba el mensaje
por correo electr´nico y el documeno de procesador de textos y as´ sucesivamente.
o
ı
El virus caus´ problemas creando mensajes m´s r´pido de lo que pod´ enviarse. Los
o
aa
ıan
mensajes listos para enviarse se almacenaban temporalmente en un disco. Si el disco
se llenaba, el sistema pod´ caer en bloqueo permanente o incluso descomponerse.
ıa
Despu´s de que el virus enviaba el correo a las primeras 50 direcciones, cada uno de
e
esos receptores enviaba entonces el correo a 50 direcciones.
Por el principio de la multiplicaci´n, se ten´ 50 · 50 = 2500receptores m´s. Cada
o
ıan
a
uno de ellos enviaba el correo a 50 direcciones. De nuevo, por el principio de la
multiplicaci´n, ahora hab´ 50 · 50 · 50 = 125, 000 receptores adicionales. Despue´s
o
ıa
e
de m´s iteraciones, habr´ 50 · 50 · 50 · 50 = 6, 250, 000 receptores adicionales. As´
a
ıa
ı,
3

´
CAP´
ITULO 1. TECNICAS DE CONTEO

4

despu´s de s´lo cuatro iteraciones se hab´...