apuntes grafos

GRAFOS

F. Javier Soria de Diego

Departamento de Matematica Aplicada y AnalisisFacultad de MatematicasUniversidad de Barcelona

Gran Vıa, 58508007 Barcelona

Correo electronico: [email protected]

11 de julio de 2012

Estos no son los apuntes ((oficiales)) de la asignatura... son mis apuntes, pero puedes usarlos sincompromiso alguno. Ni todo lo que esta aquı se vera durante el curso, ni todo lo que se expliqueen clase ha de estar necesariamente aquı. . .

Cualquier error, errata, pifia o similar que encuentres, te agradecerıa que me lo comunicases a micorreo (¡gracias de antemano!).

Indice general

1. Introduccion 1

1.1. Temario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2. Ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.3. Clasificacion del tipo de problemas mas comunes . . . . . . . . . . . . . . . . . . . . 3

1.4. Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2. Representacion matricial 15

2.1. Matrices de adyacencia y de incidencia . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.2. Grupo de automorfismos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.3. Polinomio caracterıstico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3. Arboles expansivos y camino optimo 19

3.1. Grafos ponderados y camino optimo . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.2. Algoritmo de Dijkstra (1959) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.3. Numero de arboles expansivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3.3.1. Grafos contraıdos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3.3.2. Formula de Cayley . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

4. Problema de la interconexion 25

4.1. Arbol expansivo optimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

4.2. Algoritmo de Kruskal (1956) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

5. Grafos de Euler 29

i

5.1. Tour de Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

5.2. Problema del Cartero o del Explorador . . . . . . . . . . . . . . . . . . . . . . . . . . 32

6. Grafos de Hamilton 35

6.1. Tour de Hamilton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

6.2. Problema del Viajante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

6.2.1. Primera cota inferior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

6.2.2. Segunda cota inferior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

6.2.3. Cota superior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

7. Emparejamientos y Problemas de Asignacion 47

7.1. Emparejamientos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

7.2. Problema de la Asignacion de Personal. Metodo Hungaro . . . . . . . . . . . . . . . 52

8. Coloracion de Mapas y Grafos Planos 57

8.1. Numero cromatico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

8.2. Grafos planos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

8.3. Coloracion de mapas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

9. Ejercicios 69

10. Apendice 91

10.1. Notaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

10.2. Problemas abiertos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

Bibliografıa 95

Capıtulo 1

Introduccion

1.1. Temario

El objetivo principal de este curso consiste en el estudio de los conceptos y propiedades basicas enla Teorıa de Grafos, juntamente con una amplia gama de aplicaciones. A su vez, se pone enfasis enlos algoritmos eficientes para la resolucion de problemas, ası como su implementacion mediante eluso de ordenadores.

En particular, trataremos aspectos relevantes relacionados con los siguientes apartados:

1. Introduccion. Introduccion a los conceptos basicos de la teorıa de grafos y de la complejidadde los algoritmos. El Problema de los Puentes de Konigsberg. Grafos isomorfos, matrices deincidencia y de adyacencia. Teorema de Euler. El Problema del Camino mas Corto: algoritmode Dijkstra.

2. Arboles y Conexion. Los arboles son uno de los tipos de grafos mas frecuentes en lamodelizacion matematica y la computacion. Caminos y geodesicas. Arboles expansivos. ElProblema de la Interconexion: algoritmo de Kruskal.

3. Caminos de Euler. Grafos eulerianos. El Problema del Cartero: algoritmo de Fleury.

4. Caminos de Hamilton. Grafos hamiltonianos. El Problema del Viajante: estimacion decotas.

5. Emparejamientos. Grafos bipartitos. El Problema de la Asignacion de Personal: metodoHungaro. Teorema de Berge. Teorema del Matrimonio.

6. Grafos Planos y Coloracion. El Problema de los Cuatro Colores. Numero cromatico.Numero de corte. Mapas. Problema del Almacenamiento: Conjetura de Hajos. Teorema deKuratowski. Teorema de la Caracterıstica de Euler. Teorema de los Seis Colores.

7. Implementacion. Estructuras de datos y algoritmos de grafos.

1

CAPITULO 1. INTRODUCCION

1.2. Ejemplos

Red de metro: calculo de la ((mejor)) ruta entre dos estaciones.

Moleculas de los compuestos alcanos: CnH2n+2. ¿Cuantos compuestos isomeros (mismo nume-ro de atomos de carbono e hidrogeno) existen?

ue

ee e e

e

e

e

eeu u

Metano: C1H4 Etano: C2H6

Numero maximo de casas que se pueden conectar a la red de agua, luz y gas, sin que las lıneasse crucen.

t t td d

Agua Luz Gas

C1 C2

¿Se pueden conectar mas casas?

El Problema de los Puentes de Konigsberg. ¿Se pueden cruzar los siete puentes una sola vezy volver al punto de partida?

A D

C

B

¿Cuando puede un cartero partir de la oficina de correos, recorrer todas las calles de su rutauna sola vez y volver a la oficina?

¿Cuando puede un vendedor visitar todos los establecimientos que tiene asignados, una solavez, y volver al lugar de partida? ¿Cual es la ruta mas corta?

¿Cuantos colores se necesitan para pintar un mapa?

2

1.3. CLASIFICACION DEL TIPO DE PROBLEMAS MAS COMUNES

1.3. Clasificacion del tipo de problemas mas comunes

1. Existencia: Problema de los Puentes de Konigsberg.

2. Construccion: Ruta del cartero. Se emplean metodos algorıtmicos.

3. Enumeracion: ¿Cuantas soluciones hay?

4. Optimizacion: ¿Cual es la mejor solucion?

Aunque los enunciados de los problemas que se presentan en la Teorıa de Grafos pueden parecerelementales, existen casos en los que no se conoce todavıa la solucion:

¿Para que grafos tiene solucion el Problema del Viajante? Si por ejemplo analizaramos todaslas rutas posibles que unen las 50 provincias de Espana, con una velocidad de calculo de unbillon de billones de billones por segundo (1036 casos/sg), tardarıamos del orden de 10.000millones de veces la edad del Universos (unos 15.000 millones de anos) en determinar la rutamas corta.

¿Cual es el menor numero de intersecciones que hemos de hacer para unir entre sı 13 puntos delplano? Por ejemplo, si consideramos 1, 2, 3 o 4 puntos, podemos conseguirlo sin interseccionalguna. Para 5 puntos se ha de hacer al menos una interseccion y 6 puntos requieren 3. Losvalores para 7, 8, 9, 10, 11 y 12 puntos son, respectivamente, 9, 18, 36, 60, 100 y 150. Para13 puntos o mas el problema no se ha resuelto todavıa.

u u

u u

u u

Se necesitan al menos 3 cruces para unir 6 puntos

1.4. Grafos

Definicion 1.4.1 Un grafo G = (V,E) es un conjunto de elementos V = V (G), llamados verti-ces, y un conjunto de aristas E = E(G) que unen dos vertices. Si dos o mas aristas unen el

3


mismo par de vertices se denominan aristas multiples. Si una arista une un vertice consigo mis-mo se denomina lazo. Un grafo sin aristas multiples ni lazos se denomina simple. Un digrafo, ografo dirigido, es un grafo en el que las aristas tienen una direccion: van de un punto a otro. Dosvertices son adyacentes si estan unidos por una arista (en este caso se dice que los vertices sonincidentes con la arista, y recıprocamente). Si e ∈ E(G) es incidente en los vertices a, b ∈ V (G),escribiremos e = ab.

Ejemplo 1.4.2 Grafo con 4 vertices y 5 aristas: V = {a, b, c, d}, E = {1, 2, 3, 4, 5}.

u u

u

u��

d b c

a

3

15

2

4

No es un grafo simple: 4 y 5 son aristas multiples y 2 es un lazo. d no es adyacente a ningun otrovertice. Los vertices incidentes con la arista 4 son a y c.

Observacion 1.4.3 Dos grafos son ((iguales)) si tienen el mismo conjunto de vertices y de aristas,independientemente de su representacion grafica. La siguiente definicion especifica con mas detalleesta equivalencia:

Definicion 1.4.4 Dos grafos G y H son isomorfos si existe una biyeccion ϕ entre sus verticesque conserva las aristas:

∃ϕ : V (G)→ V (H) tal que, xy ∈ E(G) si, y solo si, ϕ(x)ϕ(y) ∈ E(H).

Ejemplo 1.4.5 Los siguientes grafos son isomorfos y existen dos isomorfismos diferentes: el quelleva a en x, b en y y c en z, y el que transforma a en z, b en y y c en x.

u u uu

u

ua b c

x z

y

Definicion 1.4.6 Un subgrafo de un grafo G es un grafo cuyos vertices y aristas pertenecen a G.

Ejemplo 1.4.7 El grafo de la derecha es un subgrafo del de la izquierda, con el mismo numero devertices:

4

1.4. GRAFOS

3. Conjetura de S. M. Ulam

Supongamos que G y H son dos grafos que tienen el mismo numero de vertices,

V (G) = {u1, . . . , un} y V (H) = {v1, . . . , vn}, n ! 3,

y de manera que para cada j = 1, . . . , n, se verifica que

G " uj # H " vj.

Estudiar si, necesariamente, G # H. El resultado es cierto, por ejemplo, si G y H sonarboles.

4. El Problema del Viajante

Un comerciante ha de visitar una sola vez todas las ciudades donde residen sus clien-tes, y quiere hacerlo de manera que el recorrido sea el mas corto posible ¿Como sepuede determinar esta ruta de manera efectiva? Si, por ejemplo, enumeramos todaslas posibilidades de ordenar las distintas ciudades (supongamos que hay n), y elegimosla que da el valor menor, habremos de considerar n! casos. Para hacernos una idea dela magnitud de este numero, si pudieramos trabajar con el ordenador mas rapido queexiste (alrededor de 40 billones de operaciones por segundo), y hubiera 25 ciudades,tardarıamos mas de 12.000 anos. Si aumentamos ligeramente este valor hasta las 30ciudades, entonces el tiempo requerido llegarıa hasta 14 veces la edad del Universo...

5. Grafos simples 3 y 4 regulares (C. Berge, 1973)

¿Es cierto que todo grafo simple 4-regular contiene un subgrafo 3-regular? Observamosque el problema tiene solucion si cambiamos 4 y 3 por k y k " 1, para k = 2, 3. Enefecto, si G es simple y 2-regular, contiene al menos una arista con vertices distintos, loque nos da un subgrafo 1-regular. Si k = 3, entonces G no puede ser un arbol (en casocontrario ! = 1), y por lo tanto G contiene un ciclo (que es un subgrafo 2-regular).

!

! !

! !

!

!

!

!

! !

! !

!

!

!Grafo 4-regular Subgrafo 3-regular

2Definicion 1.4.8 El grado de un vertice v de un grafo, que se denota por g(v), es el numero dearistas incidentes con v, donde los lazos cuentan por 2.

Ejemplo 1.4.9

u u u ua b c d

g(a) = 0, g(b) = 1, g(c) = 3, g(d) = 4

Definicion 1.4.10 La sucesion de grados de un grafo es la que se obtiene al ordenar, de maneracreciente, los grados de sus vertices.

Ejemplo 1.4.11 Ejemplos de grafos que tienen la misma sucesion de grados pero no son isomorfos:

u u u u u uj j{1, 2, 3} {1, 2, 3}

w w ww w w

w ww w w

w

{1, 1, 2, 2, 3, 3} {1, 1, 2, 2, 3, 3}

Observacion 1.4.12 Es un problema no trivial saber cuando una sucesion es la sucesion de gradosde un grafo.

Definicion 1.4.13 Sea G = (V,E) un grafo. Se denota por:

α(G) al numero de aristas de G (α(G) = Card (E)).

ν(G) al numero de vertices de G (ν(G) = Card (V )).

Grado mınimo de G: δ(G) = mın{g(v) : v ∈ V (G)}.

5


Grado maximo de G: ∆(G) = max{g(v) : v ∈ V }.

Se dice que G es un grafo regular de grado r (o r-regular) si δ = ∆ = r.

Ejemplo 1.4.14 Los grafos del Ejemplo 1.4.7 son regulares de grado 4 y 3, respectivamente.

Definicion 1.4.15 Si v ∈ V (G), G− v es el grafo que se obtiene al suprimir el vertice v, y todassus aristas incidentes. Analogamente, si e ∈ E(G), G− e es el grafo que se obtiene al suprimir laarista e.

u

u

u

u

u

u

uuv

e

GG− v G− e

Teorema 1.4.16 (Euler). En todo grafo, la suma de los grados de sus vertices es igual al dobledel numero de aristas: ∑

v∈Vg(v) = 2α. (1.1)

Demostracion. Basta observar que toda arista tiene dos extremos (incluidos los lazos), y por lotanto contribuye por dos a la suma de los grados. Formalmente, lo demostramos por induccion enel numero de aristas:

Si α = 0 es trivial. Si α = 1, entonces o bien ν = 2 y cada vertice tiene grado 1, o la arista es unlazo y hay un solo vertice de grado 2. En ambos casos (1.1) es valido. Supongamos demostrado elresultado para α ≤ k y sea G un grafo tal que α = k + 1. Consideremos una arista e de G y elgrafo H = G− e. Entonces todos los vertices de H tienen el miso grado en H que en G, excepto 2que tienen un grado menos (si e no es un lazo), o 1 con 2 grados menos (si e es un lazo). En amboscasos, usando la hipotesis de induccion, obtenemos que:

∑

v∈V (G)

g(v) =∑

v∈V (H)

g(v) + 2 = 2(α− 1) + 2 = 2α.

�

Corolario 1.4.17 En todo grafo, el numero de vertices con grado impar, es un numero par.

Ejemplo 1.4.18 En una reunion, el numero de personas que conocen a un numero impar deinvitados, es un numero par.

Corolario 1.4.19 Si G es r-regular, entonces α = rν/2.

6

1.4. GRAFOS

Ejemplo 1.4.20 Tipos de Grafos:

Completos: Cada vertice esta unido a todos los restantes, una sola vez. Se denotan comoKn. Son grafos simples y (n− 1)-regulares.

u u u u uuuu uu

K1 K2 K3 K4

Nulos: Grafos sin aristas. Se denotan por Nn.

u u u u uuuu uu

N1 N2 N3 N4

Platonicos: Representan las aristas y los vertices de los cinco poliedros Platonicos:

u

uuuu uu

u

u u

u

u

u uu u

u

uTetraedro (3-regular) Octaedro (4-regular) Cubo (3-regular)

u uu

uu

u u u

u

u

u uIcosaedro (5-regular)

7


u uu uu

uu

u u

u

u

u

u

uu

uu

uu

Dodecaedro (3-regular)

u

Definicion 1.4.21 Un camino de longitud k entre los vertices v1 6= vk+1de un grafo es unasucesion de k aristas de la forma

v1v2, v2v3, · · · , vkvk+1.

En este caso se denomina camino entre v1 y vk+1 (tambien se denota como v1v2 · · · vk+1). Uncamino simple es un camino en el que todas las aristas son diferentes. Un camino elementales un camino simple en el que todos los vertices son distintos.

Ejemplo 1.4.22

u uu

uuud e

f

bc

a

Camino entre a y e: abcbe

Camino simple entre a y e: abcdebfe

Camino elemental, de longitud 3, entre a y e: abfe

Camino elemental, de longitud 2, entre a y e: abe

Definicion 1.4.23 Un grafo es conexo si existe un camino elemental entre cada par de vertices.Una arista de un grafo es un puente si al quitarla, el nuevo grafo es disconexo. Analogamente se de-fine vertice de corte. Los mayores subgrafos conexos de un subgrafo se denominan componentesconexas. El numero de componentes conexas se denota por ω(G).

Ejemplo 1.4.24

uu u

uu uu uu u u

u uuuGrafo con 3 componentes puente

8

1.4. GRAFOS

Definicion 1.4.25 Un camino cerrado de longitud k es una sucesion de aristas del tipov1v2, v2v3, · · · , vkv1 (o tambien v1v2 · · · vkv1) que comienzan y acaban en el mismo vertice. Unciclo Ck es un camino cerrado de longitud k en el que todas las aristas son diferentes y todos losvertices intermedios tambien. Un triangulo es un ciclo de longitud 3 (C3).

Ejemplo 1.4.26 vywxyzv es un camino cerrado que no es un ciclo. vwxyzv es un ciclo de longitud5. vwyv es un triangulo.

uuu uu u

x

yz

u

v w

Ejemplo 1.4.27 Los ciclos Cn son grafos 2-regulares, con n vertices y n aristas.

u u u uuu

u u

u uC1 C2 C3 C4

Definicion 1.4.28 Un grafo bipartito es un grafo cuyo conjunto de vertices se puede dividir endos subconjuntos disjuntos A y B, de manera que cada arista del grafo une un vertice de A conotro de B. Un grafo bipartito es completo si cada vertice de A esta unido a cada vertice de B. SiCard (A) = r y Card (B) = s denotamos por Kr,s a dicho grafo bipartito completo.

Ejemplo 1.4.29 En un grafo bipartito los vertices se pueden pintar con 2 colores de manera quecada arista sea incidente con vertices de distinto color:

e

e

ee

uuu

uK4,4

u u u u

e e e eCubo

Observacion 1.4.30 Kr,s = Ks,r, ν = r + s y α = rs.

Definicion 1.4.31 Un arbol es un grafo conexo sin ciclos.

9


Ejemplo 1.4.32 Ejemplos de arboles:

uu uu u uuuu u u u u

u uuuuu u

uu u

u

Proposicion 1.4.33 G es un arbol si, y solo si, para todo par de vertices u, v ∈ V (G) existe ununico camino elemental entre u y v.

Demostracion. Si G es un arbol, entonces es un grafo conexo, y por lo tanto existe al menos uncamino elemental entre u y v. Si existieran dos, tomando uno a continuacion del otro, en sentidoinverso, encontrarıamos facilmente que G tendrıa un ciclo, lo que es una contradiccion.

u uu uu

uu

u

v

a

b c

d

eDe los caminos uabcv y uadecv encontramos el ciclo abceda.

Recıprocamente, si G no fuera un arbol, habrıa un ciclo y ası podrıamos ir de un vertice a otrodiferente de este ciclo mediante dos caminos diferentes (en sentido horario y antihorario), lo que denuevo es una contradiccion. �

Observacion 1.4.34 Se puede demostrar que un grafo conexo es un arbol, si y solo si α = ν − 1.En particular un arbol tiene el menor numero de aristas posible (ν − 1) para que un grafo con νvertices sea conexo.

Ejemplo 1.4.35 Mas ejemplos de grafos:

Elementales: Se denominan Pn, y son arboles con ν = n, α = n − 1, y si n ≥ 3 entoncesδ = 1 y ∆ = 2. u u u u u u

P1 P2 P3

Cubos: Se denotan por Qn. Los vertices representan todos los numeros binarios de n cifras.Dos vertices estan unidos si tienen solo una cifra diferente. Son grafos bipartitos, n-regulares,con ν = 2n y α = n2n−1.

10

1.4. GRAFOS

u u

u u

u u

uuuuu

u

u u0 1 00 10

01 11

000 100

001 101

010 110

011 111

Q1 Q2 Q3

Definicion 1.4.36 Sea G un grafo conexo, u, v ∈ V . Se define d(u, v), distancia de u a v, a lalongitud del menor camino elemental que los une (estos caminos se denominan geodesicas). Sellama diametro de G a la longitud de la mayor geodesica de G, y se denomina D(G).

Ejemplo 1.4.37 Es facil demostrar que d define una metrica en el conjunto de vertices V . En elsiguiente ejemplo, d(a, b) = d(a, c) = d(b, c) = d(c, d) = 1; d(a, d) = d(b, d) = 2. El diametro de Ges D(G) = 2.

u

uu u

a

b

c d

D(G) = 2

Teorema 1.4.38 (Constante de Moore). Sea G un grafo conexo con ∆ > 2. Entonces:

ν ≤ N(∆, D) :=∆(∆− 1)D − 2

∆− 2. (1.2)

Demostracion. Fijemos un vertice v ∈ V . Por hipotesis, como mucho hay ∆ vertices adyacentes av. De cada uno de estos vertices, como mucho hay ∆− 1 nuevos vertices adyacentes, y por lo tantoen total hay ∆(∆− 1) nuevos vertices. En el siguiente paso, a distancia 2 de v, encontramos, comomucho ∆(∆− 1)2 nuevos vertices. Como el diametro de G es D, como mucho podemos iterar esteproceso D-veces, a partir del cual habremos obtenido todos los vertices de G.

uu u uu u u u u u

1

∆

∆(∆− 1)

v

sss sss11


Sumando todos los vertices que hemos contado en cada paso:

d = 0 → 1

d = 1 → 1 + ∆

d = 2 → 1 + ∆ + ∆(∆− 1)

...

d = D → 1 + ∆ + ∆(∆− 1) + · · ·+ ∆(∆− 1)(D−1)

= 1 + ∆1− (∆− 1)D

1− (∆− 1)=

∆(∆− 1)D − 2

∆− 2.

�

Observacion 1.4.39 Si ∆ = 1, el unico grafo conexo que existe es P2: u u , y por lo tantoN(1, 1) = 2. Si ∆ = 2, es facil probar que N(2, D) = 2D+1 y el unico grafo regular, con parametros∆ = 2 y diametro D que tiene ese numero de vertices, es el ciclo C2D+1.

Es un problema interesante, y no trivial, determinar para que valores del par (∆, D), existen grafosregulares G para los que se alcanza la constante de Moore: ν = N(∆, D). Se puede probar que estoocurre solo si D = 1 o D = 2 y ∆ = 3, 7 y quiza 57 (es un problema abierto).

uuu uu

u

u u

u u

Grafo de Petersen (es optimo)D = 2,∆ = 3, 3-regular, ν = N(3, 2) = 10

Se conocen algunos casos optimos de grafos que tienen el mayor numero de vertices, con parametros(∆, D). Un resumen se recoge en la siguiente tabla:

(∆, D) ν N(∆, D) Nombre

(3, 2) 10 10 Petersen

(4, 2) 15 17 K3 ∗ C5

(5, 2) 24 26 K3 ∗X8

(7, 2) 50 50 Hoffman− Singleton

(3, 3) 20 22 C5 ∗ F4

(3, 4) 38 46 vC,AFY

Numero maximo de vertices posibles en grafos ∆-regulares y diametro D.

12

1.4. GRAFOS

La estimacion (1.2) permite obtener una cota inferior para el diametro de un grafo:

D ≥log

[ν(∆− 2) + 2

∆

]

log (∆− 1). (1.3)

Estimaciones del diametro de varios grafos han sido determinadas mediante experimentos empıricos.Ası, por ejemplo, se calcula que el diametro de la poblacion mundial tiene un diametro de 6 y laWWW de 19. Observamos que, en el primer caso, ν ≈ 6 · 109 y basta tomar ∆ = 50 (es decir, cadapersona conoce al menos a otras 50 mas) para que (1.3) nos de el valor D ≥ 6.

13

Capıtulo 2

Representacion matricial

2.1. Matrices de adyacencia y de incidencia

Definicion 2.1.1 Sea G un grafo. La matriz de adyacencia de G, A(G) = (ai,j)i,j=1,··· ,ν , es lamatriz cuadrada ν × ν, donde ai,j es el numero de aristas que unen los vertices i, j (los lazos secuentan por 2, si i = j).

Si G es un grafo sin lazos, la matriz de incidencia de G, I(G) = (bi,j)i=1,··· ,ν,j=1,··· ,α es la matrizν×α, donde bi,j = 1, si el vertice i es incidente con la arista j, y es igual a cero en caso contrario.

Ejemplo 2.1.2 Matrices de adyacencia y de incidencia del siguiente grafo G:

u u

u u

A(G) =

0 1 0 11 0 1 20 1 0 11 2 1 0

I(G) =

1 0 0 1 0 01 1 0 0 1 10 1 1 0 0 00 0 1 1 1 1

Ejemplo 2.1.3A(Kn) = (1)− Id.

Observaciones 2.1.4

Las matrices A e I dependen del orden en el que hayamos numerado los vertices y las aristas.Ası, por ejemplo, las siguientes matrices de adyacencia representan el mismo grafo:

15

CAPITULO 2. REPRESENTACION MATRICIAL

0 1 01 0 10 1 0

0 1 11 0 01 0 0

0 0 10 0 11 1 0

ww w

A(G) es una matriz simetrica, y toda matriz simetrica, cuya diagonal sea nula, genera ungrafo sin lazos.

G es simple si y solo si a(j, j) = 0 y a(i, j) ∈ {0, 1}.

Para todo j = 1, . . . , ν,ν∑

i=1

a(i, j) = g(j).

Para toda arista j ∈ {1, · · · , α},

ν∑

i=1

bij = 2.

Para todo vertice i = 1, . . . , ν,α∑

j=1

b(i, j) = g(i).

2.2. Grupo de automorfismos

Definicion 2.2.1 Dado G, se define el grupo de automorfismos de G:

Γ(G) = {ϕ : G→ G,ϕ es un isomorfismo (automorfismo)}.

Observacion 2.2.2 Γ(G) es un subgrupo del grupo de permutaciones de ν elementos, Sν . Ademas,se puede demostrar que todo grupo finito es (isomorfo a) el grupo de automorfismos de algun grafo.

Ejemplo 2.2.3

ww w

1

2

3

Γ(G) = {Id, (1, 2)}

16

2.3. POLINOMIO CARACTERISTICO

Observacion 2.2.4 Si dos grafos son isomorfos, es facil ver que sus respectivos grupos tambienlo son. Sin embargo, el recıproco no es cierto:

Los siguiente grafos son claramente no isomorfos pero tienen el mismo grupo de automorfismosΓ = {Id, (1, 2)}:

ww w

1

2

3 www

1 2

3

2.3. Polinomio caracterıstico

Definicion 2.3.1 El polinomio caracterıstico de un grafo G es, es el polinomio caracterısticode su matriz de adyacencia:

PG(λ) = det(A(G)− λ · Id).

El espectro de G es el conjunto de autovalores (con repeticion) de PG.

Ejemplo 2.3.2PK3(λ) = −λ3 + 3λ+ 2,

cuyo espectro es {2,−1,−1}.

Observacion 2.3.3 Si A1 y A2 son diferentes matrices de adyacencia de G, entonces

| det(A1 − λ · Id)| = |det(A2 − λ · Id)|,

y por lo tanto el espectro de G no depende de la matriz elegida.

Observacion 2.3.4 No es cierto que si 2 grafos tienen el mismo espectro entonces son isomorfos:

w w ww

Espectro = {0, 4}

y

17

CAPITULO 2. REPRESENTACION MATRICIAL

Alrededor de 1970 se encontraron ejemplos mas interesantes de grafos no isomorfos con el mismoespectro:

- Ejemplo de grafos simples con menor numero de vertices (ν = 5):

ww ww w

w

w w w wy

- Ejemplo de grafos simples y conexos con menor numero de vertices (ν = 6):

uuu

uuu uuuuu

u

y

- Ejemplo de arboles con menor numero de vertices (ν = 8):

vvv v vvvv y

vv vvv v v v

Ejemplo 2.3.5 Se puede demostrar que si G es simple y los autovalores de PG son distintos,entonces Γ(G) es abeliano. Por ejemplo, si G = K3, entonces Γ(K3) = S3, que no es abeliano, y elespectro de K3 es {2,−1,−1}. Para el grafo

ww w

sabemos que Γ(G) = {Id, (1, 2)}, que es abeliano, y el espectro es {0,√

2,−√

2}.

18

Capıtulo 3

Arboles expansivos y camino optimo

3.1. Grafos ponderados y camino optimo

Definicion 3.1.1 Sea G un grafo simple y conexo. Se dice que (G,w) es un grafo ponderado,si existe una funcion w : E(G)→ R+, que se denomina peso.

Observacion 3.1.2 En todo grafo ponderado se define la longitud de un camino c = u1u2 · · ·uncomo

longitudw(c) =n−1∑

j=0

w(ujuj+1).

La metrica o distancia dw(a, b) se calcula tomando la longitud menor de todos los caminos elemen-tales entre los vertices a y b. Por ejemplo:

x x

xx

a b

cd

3

6

2

1 7

dw(a, b) = 3, dw(a, c) = 3, dw(a, d) = 1, dw(b, c) = 6, dw(b, d) = 4, dw(c, d) = 2.

Nuestro interes es resolver el siguiente problema:

Dado un grafo ponderado, calcular la distancia entre 2 vertices arbitrarios y hallar una geodesicaque los conecta. Es lo que denominaremos el camino optimo entre dichos vertices.

19

CAPITULO 3. ARBOLES EXPANSIVOS Y CAMINO OPTIMO

3.2. Algoritmo de Dijkstra (1959)

Dado un conjunto de vertices S ⊂ G, denotamos por S = G \ S.

Sea (G,w) un grafo ponderado y, en este apartado, escribamos d para representar dw. Es facilprobar que

d(u, S) = mın{d(u, v) + w(v, z) : v ∈ S, z ∈ S}. (3.1)

Paso 1: Elegimos u ∈ V (G), denotamos u1 = u y S1 = {u1}. Usando (3.1)hallamos u2 ∈ S1 tal que

d(u1, S1) = mın{d(u1, v) + w(v, z) : v ∈ S1, z ∈ S1} = w(u1, u2).

Denotamos S2 = S1 ∪ {u2}.

Paso 2: Supongamos construidos los subconjuntos de vertices:

S1 ⊂ · · · ⊂ Sk

con k < ν. Usando (3.1) hallamos uk+1 ∈ Sk satisfaciendo:

d(u1, Sk) = d(u1, uj) + w(uj , uk+1),

para algun j ∈ {1, . . . , k}. Denotamos Sk+1 = Sk ∪ {uk+1}.

El proceso acaba si k = ν, donde obtenemos que Sν = V (G).

Observamos que en cada paso el conjunto Sk, junto a las aristas elegidas, es un arbol. Ası, para k = νobtenemos un arbol que contiene todos los vertices (es lo que se denomina un arbol expansivo oabarcador), formado por geodesicas que van del punto inicial u a cada uno de los restante vertices.

Ejemplo 3.2.1 Vamos a calcular las distancias desde el vertice a del siguiente grafo ponderado,al resto de los vertices, dando tambien una geodesica en cada caso:

vvvv va

b

c

d e

1 2

4

42

3

Tomamos u1 = a y S1 = {u1}. En el primer paso, hemos de tomar la arista desde a con el menorpeso posible, que es la ab, y denotamos u2 = b y S2 = {u1, u2} = {a, b} (indicamos en el verticeelegido la distancia obtenida al vertice inicial):

20

3.2. ALGORITMO DE DIJKSTRA (1959)

uua

1

En el segundo paso hemos de analizar todas las aristas que salen desde a (hay 2 que pesan 4)ası como las que salen desde b (a las que les sumamos la distancia entre a y b que en este casoes 1) y nos quedamos con la distancia menor, que es 3 y que corresponde a la arista bd. HacemosS3 = {a, b, d}:

uua

1

u 3Ahora desde a tenemos una arista que pesa 4 (la ac), desde b no tenemos mas opciones (todos losvertices adyacentes a b han sido ya elegidos) y desde d podemos obtener un 6 (anadiendo de) o un5 (anadiendo dc), por lo que tomamos la primera opcion desde a: S4 = {a, b, d, c}.

uua

1

u 3u4

Finalmente no nos queda otra posibilidad que anadir la arista de: S5 = {a, b, d, c, e}.

uua

1

uu4

u53

Ası, las distancias obtenidas son d(a, b) = 1, d(a, c) = 4, d(a, d) = 3, d(a, e) = 5.

Ejemplo 3.2.2 La solucion al problema del camino optimo desde a del grafo ponderado:

u u u

uuu

u u u

uu2

1 2

9

4

2

7

13

6

9

4

3

1

5

2

19

6

7

8

1

a

21


viene dado por el siguiente arbol expansivo:

u u u

uuu

u u u

uua

2

1

3 5

611 13

109

7

3.3. Numero de arboles expansivos

Nos interesamos en esta seccion por saber cuantos arboles expansivos diferentes puede haber en ungrafo simple y conexo G. Este numero se denota como τ(G). Ası, si G no fuera conexo se tendrıaque τ(G) = 0. Si G es un arbol, claramente τ(G) = 1.

Por ejemplo, mediante una comprobacion directa y elemental tenemos que τ(K3) = 3. En generalse puede probar que τ(Kn) = nn−2.

Es inmediato que si a un grafo le quitamos todos los lazos, o todas las aristas que tienen un extremode grado 1, junto con dicho vertice (esto se denomina podar), el numero de arboles expansivos novarıa.

3.3.1. Grafos contraıdos

Definicion 3.3.1 Sea e ∈ E(G). Se llama grafo contraıdo por la arista e y se denota comoG · e, al grafo que tiene los mismos vertices que G, aunque identificando en uno solo los extremosde la arista e, y sus aristas son las de G menos e.

Ejemplo 3.3.2

u u

u u uuu

e

GG · e

Observamos que α(G · e) = α(G)− 1 y ν(G · e) = ν(G)− 1. Ademas, el grafo contraıdo deja de ser,en muchos casos, un grafo simple.

22

3.3. NUMERO DE ARBOLES EXPANSIVOS

Ejemplo 3.3.3

u u

u

u

uG

e

G · e

3.3.2. Formula de Cayley

La formula de Cayley nos permite obtener τ(G) en terminos del numero de arboles expansivos degrafos que tienen un numero menor de vertices y aristas, o que pueden llegar a ser no conexos, porlo que el calculo de τ es mas sencillo. Esta formula nos dice que

τ(G) = τ(G \ e) + τ(G · e)

La demostracion es elemental y esta basada en observar que todo arbol expansivo de G o no contienea e (en cuyo caso es un arbol expansivo de G \ e), o sı que contiene dicha arista, y por lo tanto sepuede identificar con un arbol expansivo de G · e.

La manera usual de aplicar esta formula consiste en identificar el numero τ con los diversos grafosque aparecen:

Ejemplo 3.3.4 Vamos a contar el numero de arboles expansivos de K3 usando la formula deCayley:

u

u ue

=

u

u

u+ u u = 1 + u u= 1 + 2 = 3,

es decir, τ(K3) = 3.

Observacion 3.3.5 Si un grafo G se puede poner como la union de otros 2 grafos G1 y G2, unidospor un vertice en comun, o por una arista que es un puente, entonces

τ(G) = τ(G1) · τ(G2).

Ejemplo 3.3.6 El numero de arboles expansivos del grafo G:

23


uu

uu

u uuuuuuu

u uu uu

u

es igual al del siguiente grafo (podando las hojas)

uuu u u

uu u uu u

y eliminado los puentes nos queda que es igual al del siguiente grafo

uu

uu uu u

que se puede poner como union de 3 triangulos K3, por lo que

τ(G) = 3 · 3 · 3 = 27.

Observacion 3.3.7 Es importante observar que el metodo anterior de Cayley solo nos da elnumero de arboles expansivos de un grafo G, pero no nos dice cuales son ni como representarlosgraficamente.

24

Capıtulo 4

Problema de la interconexion

4.1. Arbol expansivo optimo

Estudiamos ahora la solucion al problema de la interconexion:

En un grafo ponderado (G,w), queremos encontrar un arbol expansivo que tenga el menor peso (lasuma de los pesos de sus aristas) posible. Esta situacion surge de manera natural cuando queremosoptimizar recursos en una red, y buscamos la manera optima de interconectar los puntos de dichared, con el menor gasto (precio, distancia, tiempo, u otra variable) posible.

Por ejemplo, supongamos que nos dan la siguiente red de carreteras entre 4 poblaciones, y nospiden hallar la manera de poder seguir viajando entre dichas poblaciones pero que el gasto totalde la red construida sea el mınimo (los pesos de cada arista nos da lo que cuesta construir dichotramo de carretera):

u u

u u

10

203

1

2 (4.1)

Es obvio que la solucion viene dada por hallar, de entre todos los arboles expansivos de G, aquelque tenga el menor peso. Representamos todos los casos posibles (es facil ver, usando la formulade Cayley, que hay 8). El numero que aparece en cada caso es el peso obtenido:

25

CAPITULO 4. PROBLEMA DE LA INTERCONEXION

u u

u u

u u

u u

u u

u u

u u

u uu u

u u

u u

u u

u u

u u

u u

u u

13 23 32 31

15 14 25 24

Ası, la solucion en este caso viene dada por el primer arbol expansivo:

u u

u u13

y tiene un gasto de 13.

Aunque calcular la solucion del problema de la interconexion podrıa parecer complicada, dado elelevado numero de casos que hay en un grafo completo (τ(Kn) = nn−2), existe sin embargo unalgoritmo, que se explica en la siguiente seccion, que permite hallar el arbol optimo de maneraefectiva.

4.2. Algoritmo de Kruskal (1956)

Este algoritmo construye, en ν − 1 pasos, un arbol expansivo optimo, y por lo tanto resuelve elproblema de la interconexion. Es extremadamente sencillo, y solo requiere analizar la existencia ono de ciclos al ir anadiendo nuevas aristas.

A diferencia del algoritmo de Dijkstra, se observa que en los pasos intermedios, el subgrafo quevamos obteniendo no tiene por que ser un arbol (aunque sı que lo sera el resultado final).

Ası pues, consideremos un grafo ponderado (G,w):

26

4.2. ALGORITMO DE KRUSKAL (1956)

Paso 1: Elegimos e1 ∈ E(G), tal que

w(e1) = mın{w(e) : e ∈ E(G)}.

Denotamos R1 = {e1}.

Paso 2: Supongamos construidos los subconjuntos de aristas:

R1 ⊂ · · · ⊂ Rk

con k < ν − 1. Elegimos ek+1 ∈ E(G) \Rk satisfaciendo:

- ek+1 no forma ningun ciclo junto con las aristas de Rk.

- De entre todas estas aristas, ek+1 tiene el menor peso posible w(ek+1).

Denotamos Rk+1 = Rk ∪ {ek+1}.

El proceso acaba si k = ν − 1, donde obtenemos que Rν−1 es un arbol expansivooptimo de G.

Ejemplo 4.2.1 Volvamos al ejemplo (4.1). Usando el algoritmo de Kruskal tomamos e1 la aristade menor peso, que es igual a 1:

u

u1

R1

La siguiente arista e2 es la que pesa 2:

u

u1

u2

R2

Como la arista de menor peso no elegida forma ciclo con las de R2, no la consideramos, y pasamosa la siguiente, que es la que pesa 10, obteniendo la solucion que ya hemos calculado:

27

CAPITULO 4. PROBLEMA DE LA INTERCONEXION

u

u1

u2

u10

R3

Ejemplo 4.2.2 Hallamos a continuacion la ruta que interconecta las siguientes capitales, minimi-zando la distancia total. La siguiente tabla nos da la distancia (en cientos de millas) entre Londres(L), Mexico DF (Mx), Nueva York (NY ), Parıs (Pa), Pekın (Pe) y Tokio (T ):

Mx NY Pa Pe T

L 56 35 2 51 60

Mx − 21 57 78 70

NY − − 36 68 68

Pa − − − 51 61

Pe − − − − 13

Observamos que estamos considerando el caso del grafo completo K6 y que hay 64 = 1296 arbolesexpansivos diferentes.

Usando el algoritmo de Kruskal, obtenemos en este caso 2 posibles soluciones, ambas con un pesoigual a 122:

uuu

uuu

Mx

NY

L

PaPe

T

uuu

uuu

Mx

NY

L

PaPe

T

28

Capıtulo 5

Grafos de Euler

Como ya se ha comentado en la Introduccion, la teorıa de Grafos tiene un primer precursor en lafigura de L. Euler quien, en 1736, resolvio el problema de los Puentes de Konigsberg, utilizandopor primera vez tecnica de grafos: ¿Se pueden cruzar los siete puentes que unen A,B,C,D una solavez y volver al punto de partida?

A D

C

B

Este problema equivale a saber si en el siguiente grafo podemos recorrer todas las aristas una solavez, empezando y acabando el recorrido en el mismo vertice:

u

u

u

u

5.1. Tour de Euler

Definicion 5.1.1 Sea G un grafo. Un camino de Euler es un camino simple que contiene todaslas aristas de G (una sola vez). Si el camino de Euler es cerrado (empieza y acaba en el mismo

29

CAPITULO 5. GRAFOS DE EULER

vertice) se denomina tour de Euler, y en este caso diremos que G es euleriano.

Ejemplo 5.1.2 De manera informal, un grafo es euleriano si se puede dibujar de un solo trazo,empezando y acabando en el mismo punto:

u

uuu

ub

a

c

d

e

acdecba es un tour de Euler.

uu u u

uu u

u uNo son eulerianos.

Saber si un grafo es euleriano es trivial:

Teorema 5.1.3 Sea G un grafo conexo. Entonces, G es euleriano si, y solo si, g(v) es par, paratodo v ∈ V (G).

Demostracion. Si G es euleriano, un tour de Euler incide, cada vez que pasa por un vertices, con 2aristas, por lo que como contiene todas las de E(G) la suma de aristas incidentes en cada vertice(es decir, su grado) es un numero par.

Recıprocamente, usemos un razonamiento de reduccion al absurdo, y supongamos que G es conexocon todos los vertices de grado par, y que no sea euleriano. Sea H un subgrafo de G satisfaciendoestas mismas condiciones, pero con el menor numero posible de aristas. Como g(v) ≥ 2, entoncesH no es un arbol (vease el Ejercicio 18) y necesariamente contiene un ciclo C. Podemos suponerque C es el mayor camino simple cerrado de H. Como H no es euleriano, entonces C H.

Sea H ′ una componente conexa de H \ E(C), tal que α(H ′) ≥ 1. Como H ′ H, H ′ es conexoy gH′(v) es par, para todo v ∈ V (H ′), se deduce que H ′ es euleriano (H era el que tenıa menosaristas satisfaciendo estas propiedades).

30

5.1. TOUR DE EULER

u u

u u

u v

C

u uu

u

u

uH ′

u v

u u

u u

uu uu

u

u

uu v

CH ′

Es facil ver que C y H ′ comparten necesariamente algun vertice en comun (y ninguna arista, porconstruccion), por lo que uniendolos formamos un camino simple cerrado de H, que lo denotamoscomo CH ′, tal que α(CH ′) > α(C), lo que es una contradiccion. �

Corolario 5.1.4 Un grafo G conexo contiene un camino de Euler si, y solo si, existen 2 unicosvertices de grado impar.

Ejemplo 5.1.5 Volviendo al Ejemplo 5.1.2, usando el Teorema 5.1.3 vemos que los 2 grafos dela segunda lınea no son eulerianos, pero como ambos solo tienen 2 vertices de grado impar, sı quecontienen un camino de Euler (lo que se comprueba trivialmente).

Ejemplo 5.1.6 Tenemos ahora una demostracion rigurosa del problema de los Puentes de Konigs-berg, pues claramente el grafo

u

u

u

u

no es euleriano.

31


5.2. Problema del Cartero o del Explorador

Una aplicacion interesante del estudio de los grafos eulerianos es el llamado Problema del Carteroo del Explorador, cuyo objetivo es recorrer un circuito, pasando por todas las calles (o rutas) almenos una vez, y de manera que se haga minimizando el coste (como siempre, podemos hablar dedinero, de distancias, tiempo, etc.).

Si el grafo ponderado asociado a dicho problema es euleriano, entonces todos los tours de Euler quepodamos encontrar tienen el mismo peso (pues elegimos todas las aristas, en el orden que sea, unasola vez), y la solucion es trivial. Por ejemplo, en el siguiente grafo euleriano, si comenzamos en a,hay 4 posibles tours de Euler, todos ellos con un peso igual a 21: abcdeca, abcedca, acdecba, acedcba.

u uuu u

a b

c

d e

1

23

45

6

Ası, el problema tiene interes si el grafo no es euleriano. En este caso, necesariamente hemos deduplicar algunas de las aristas, y nuestro objetivo es hacerlo de manera que se haga anadiendo elmenor peso total posible. Por ejemplo, en el grafo no euleriano:

u u

u u

a b

cd

1

2 4 3

5

si queremos recorrer todas las aristas, al menos una vez, comenzando y terminando en a, vemosque basta con duplicar las aristas ab y ad, para obtener un grafo euleriano, y el peso total anadido(1 + 2 = 3) es trivialmente el menor posible (cualquier otra arista pesa 3 o mas):

u u

u u

a b

cd

1

2 4 3

5

lo que nos da como solucion un peso total de 15 + 3 = 18, y un posible recorrido podrıa ser:

abadbcda.

32

5.2. PROBLEMA DEL CARTERO O DEL EXPLORADOR

Este ejemplo nos da las pautas para resolver el problema, con mas generalidad, pero con la hipotesisde que en (G,w) solo hay 2 vertices de grado impar:

Paso 1: Hallamos u, v ∈ V (G), unicos vertices con grado impar.

Paso 2: Usando el algoritmo de Dijkstra, calculamos una geodesica L entre u y v.

Paso 3: Duplicamos en G las aristas de L, y obtenemos el supergrafo G∗.

G∗ es un grafo euleriano y es el que tiene menos peso entre los eulerianos quecontienen a G.

Ejemplo 5.2.1 Vamos a resolver el Problema del Cartero en el siguiente grafo no euleriano:

u u u

u u

a b c

de

1

2

9

11

3

48

Observamos que solo tiene 2 vertices de grado impar, e y d, y que su peso total es de 38.

Calculamos la geodesica que los une, y obtenemos el camino:

u u u

u u

a b c

de

13 6

10

es decir, dw(e, d) = 10.

Duplicando ahora este camino construimos el supergrafo euleriano:

u u u

u u

a b c

de

1

2

9

11

3

48

33


y la solucion al problema viene dada por el recorrido: abaebcbdcdea, que tiene un peso total de38 + 10 = 48.

34

Capıtulo 6

Grafos de Hamilton

Analogamente al Problema del Cartero, el Problema del Viajante busca la manera de recorrertodos lo vertices de un grafo, una sola vez, mediante un circuito cerrado (es decir, cambiamos lasaristas por los vertices), minimizando el peso total. A diferencia de la solucion tan sencilla quehemos obtenido para los grafos eulerianos, en este caso no existe una caracterizacion de cuando talrecorrido existe, ni de como calcularlo en un tiempo efectivo.

6.1. Tour de Hamilton

Definicion 6.1.1 Un grafo simple es hamiltoniano si contiene un ciclo expansivo, es decir, uncamino elemental cerrado que pasa por todos los vertices (una sola vez). Este circuito se denominatour de Hamilton.

Ejemplo 6.1.2

1. Kn y Cn son hamiltonianos, n ≥ 3.

2. Los siguientes grafos no son hamiltonianos:

u

u u

u

ut t t t t

tt tt tt

Herschel

3. Ningun arbol es hamiltoniano.

Teorema 6.1.3 Si G es un grafo hamiltoniano y ∅ 6= S V (G), entonces ω(G \ S) ≤ |S|.

35

CAPITULO 6. GRAFOS DE HAMILTON

Demostracion. Sea C un tour de Hamilton de G. Es inmediato probar (inductivamente en ν) queel resultado es cierto para C:

ω(C \ S) ≤ |S|.Ası,

ω(G \ S) ≤ ω(C \ S) ≤ |S|.�

Ejemplo 6.1.4 Volviendo al Ejemplo 6.1.2 (2), si quitamos el vertice central de grado 4, S = {v},obtenemos que |S| = 1 y ω(G \ S) = 2, por lo que G no es hamiltoniano:

u

u u

u

u

u

u

u

uG \ Sv

Una nueva condicion necesaria, que es muy sencilla de probar, para grafos hamiltonianos bipartitoses la siguiente:

Teorema 6.1.5 Si G es un grafo hamiltoniano y bipartito, entonces ν(G) es par.

Ejemplo 6.1.6 El siguiente grafo es bipartito y ν = 9, por lo que no es hamiltoniano:

u

u

u

uue e

ee

Observacion 6.1.7 Es facil ver que ninguno de los Teoremas 6.1.3 y 6.1.5 son condiciones sufi-cientes para que G sea hamiltoniano.

El siguiente resultado nos da una condicion necesaria para que G sea hamiltoniano:

Teorema 6.1.8 (Dirac, 1952). Si G es un grafo simple, ν ≥ 3 y δ ≥ ν/2, entonces G es hamil-toniano.

36

6.1. TOUR DE HAMILTON

Demostracion. Supongamos lo contrario: De entre todos los grafos en estas condiciones, elegimosuno que sea maximal (en el numero de aristas). Como Kν es hamiltoniano se deduce que G nopuede ser completo.

Sean u, v ∈ V (G) no adyacentes, y sea G∗ = G+ uv (a G le anadimos la arista uv).

Como G∗ es simple, ν(G∗) = ν(G) ≥ 3, α(G∗) > α(G) y δ(G∗) ≥ δ(G) ≥ ν/2, deducimos que G∗

es hamiltoniano. Sea C un tour de Hamilton de G∗. Claramente uv ∈ E(C) (en caso contrario Cserıa in tour de Hamilton de G). Escribimos:

C \ uv = v1v2 · · · vν−1vν

con v1 = u y vν = v. Sean S = {vj : uvj+1 ∈ E(G)} y T = {vj : vjv ∈ E(G)}.

Claramente g(u) = |S|, g(v) = |T | y v /∈ S ∪ T (por lo que |S ∪ T | < ν). Veamos que S ∩ T = ∅:En caso contrario, si existiera vj ∈ S ∩ T , como uvj+1 ∈ E(G) y vvj ∈ E(G), podrıamos construirel siguiente tour de Hamilton de G:

u u u u u u u· · · · · ·u = v1 v2 v3 vj

vj+1 vν−1 v = vν

lo que no es posible. Finalmente, acabamos la demostracion al obtener la siguiente contradiccion:

ν > |S ∪ T | = |S|+ |T | = g(u) + g(v) ≥ 2δ ≥ ν.

�

Ejemplo 6.1.9 El siguiente grafo es hamiltoniano, pues ν = 6 y δ = 3 ≥ ν/2:

uuu u

uuObservacion 6.1.10 Usando la demostracion del Teorema 6.1.8, es facil ver que si G es un grafosimple, ν ≥ 3, y u, v ∈ V (G) son vertices no adyacentes de G tales que

g(u) + g(v) ≥ ν, (6.1)

entonces G es hamiltoniano si, y solo si, G+ uv es hamiltoniano.

37


Esta observacion permite definir la clausura c(G) de G, que se construye anadiendo, de maneraiterativa, todas las aristas cuyos vertices satisfacen la relacion (6.1).

Ası, un grafo G es hamiltoniano si, y solo si, c(G) es hamiltoniano.

Ejemplo 6.1.11 Consideremos el siguiente grafo G, en donde se indica el grado de cada vertice

uu

uuu

u4

2

3

2

3

2

a

b

c

d

e

f

Completamos en un primer paso las aristas ad y ce, dado que la suma de los grados de sus verticeses, al menos, igual a ν = 6. Obtenemos ahora el siguiente grafo, con nuevos grados:

uu

uuu

u 22

a

b

c

d

e

f

4

3

4

5

Repetimos el proceso, anadiendo ahora las aristas be y cf :

38

6.2. PROBLEMA DEL VIAJANTE

uu

uuu

u

a

b

c

d

e

f

3

5

3

55

3

Por ultimo, terminamos el proceso anadiendo bd, bf y df

uu

uuu

u

a

b

c

d

e

f

5

55

5

5

5

y como el grafo obtenido es c(G) = K6, se verifica que el grafo inicial G es hamiltoniano.

Ejemplo 6.1.12 Si n ≥ 3, entonces

c(Cn) =

{Cn, si n = 3 o n ≥ 5

K4, si n = 4.

6.2. Problema del Viajante

El Problema del Viajante busca encontrar un tour de Hamilton con menor peso posible, en un grafocompleto Kν , en el que existen (ν − 1)!/2 posibilidades. En general, este es un problema para elque no se conoce un metodo o algoritmo que calcule una solucion explıcitamente, salvo en casosmuy elementales. Ası, por ejemplo, en K4:

39


! !

! !

tenemos 3 = (4 ! 1)!/2 tours de Hamilton distintos:

! !

! !

! !

! !

! !

! !

qq

44

tenemos 3 = (4− 1)!/2 tours de Hamilton distintos:

! !

! !


! !

! !

! !

! !

! !

! !

qq

44


! !

! !

! !

! !

! !

! !

qq

44

Si ponemos un peso en cada arista,

! !

! !


! !

! !

! !

! !

! !

! !

qq

44


! !

! !


! !

! !

! !

! !

! !

! !

qq

44


! !

! !

! !

! !

! !

! !

qq

44


! !

! !4

3

5

1

6

2

los tres tours anteriores pesan, respectivamente 14, 17 y 11, por lo que la solucion del pro-blema del viajante lo da

44

los tres tours anteriores pesan, respectivamente, 14, 17 y 11, por lo que la solucion del Problemadel Viajante lo da el recorrido:

! !

! !


! !

! !

! !

! !

! !

! !

qq

44


! !

! !


! !

! !

! !

! !

! !

! !

qq

44


! !

! !

! !

! !

! !

! !

qq

44


! !

! !


! !

! !

! !

! !

! !

! !

qq

44


! !

! !


! !

! !

! !

! !

! !

! !

qq

44


! !

! !

! !

! !

! !

! !

qq

44


! !

! !4

3

5

1

6

2

los tres tours anteriores pesan, respectivamente 14, 17 y 11, por lo que la solucion del pro-blema del viajante lo da

44

los tres tours anteriores pesan, respectivamente, 14, 17 y 11, por lo que la solucion delproblema del viajante lo da

44

Sabemos que, en general, el calculo de todos los posibles recorridos es un problema extremadamentecomplicado. Si denotamos por PV (G) el valor de la solucion del Problema del Viajante (ası, enel ejemplo anterior, PV = 11), es evidente que para cualquier tour de Hamilton C de un grafoponderado (G,w), se satisface la estimacion:

PV (G) ≤ w(C).

40


Nos interesamos ahora por encontrar mejores cotas, inferiores y superiores, de PV , hasta obtenerestimaciones que tengan un error prefijado. En particular, si CI y CS son, respectivamente, cotasinferior y superior, de manera que CI ≤ PV ≤ CS, el error cometido se determina, en porcentaje,como:

error =CS − PV

PV100 ≤ CS − CI

CI100 =

(CSCI− 1)

100.

6.2.1. Primera cota inferior

Como todo tour de Hamilton C de G incide en cada vertice 2 veces, si elegimos en cada v ∈ V (G)las 2 aristas de peso mınimo, llamemoslas ej(v), j = 1, 2, obtenemos:

ν∑

j=1

[w(e1(vj)) + w(e2(vj))]

2≤ PV (G)

Volviendo al ejemplo anterior, obtenemos la estimacion:

(1 + 4) + (1 + 2) + (3 + 5) + (2 + 3)

2= 10, 5 ≤ PV = 11.

Como sabemos que la solucion ha de ser un numero entero (pues los pesos de las aristas lo son),en este caso obtenemos que 11 ≤ PV , lo que es optimo.

Esta estimacion no es siempre la mejor. Por ejemplo, en el siguiente grafo ponderado:

Viajante (ası, en el ejemplo anterior, PV = 11), es evidente que para cualquier tour deHamilton C de un grafo ponderado (G, w), se satisface la estimacion:

PV (G) ! w(C).

Nos interesamos ahora por encontrar mejores cotas, inferiores y superiores, de PV , hastaobtener estimaciones que tengan un error prefijado. En particular, si CI y CS son, respec-tivamente, cotas inferior e inferior, de manera que CI ! PV ! CS, el error cometido sedetermina, en porcentaje, como:

error =CS " PV

PV100 ! CS " CI

CI100 =

!CS

CI" 1

"100.

7.2.1. Primera cota inferior

Como todo tour de Hamilton C de G incide en cada vertice 2 veces, si elegimos en cadav # V (G) las 2 aristas de peso mınimo, llamemoslas ej(v), j = 1, 2, obtenemos:

!#

j=1

[w(e1(vj)) + w(e2(vj))]

2! PV (G).

Volviendo al ejemplo anterior, obtenemos la estimacion:

(1 + 4) + (1 + 2) + (3 + 5) + (2 + 3)

2= 10, 5 ! PV = 11.

Como sabemos que la solucion ha de ser un numero entero (pues los pesos de las aristas loson), en este caso obtenemos que 11 ! PV , lo que es optimo.

Esta estimacion no es siempre la mejor. Por ejemplo, en el siguiente grafo ponderado:

! !

! !

1

1

1

1

3

3

obtenemos que los pesos de los 3 tours de Hamilton son 6, 6 y 8, por lo que PV = 6, y

CI =(1 + 1) + (1 + 3) + (1 + 1) + (1 + 1)

2= 5 < PV.

45

obtenemos que los pesos de los 3 tours de Hamilton son 6, 6 y 8, por lo que PV = 6, y

CI =(1 + 1) + (1 + 3) + (1 + 1) + (1 + 1)

2= 5 < PV.

41


6.2.2. Segunda cota inferior

Consideremos el grafo completo ponderado (Kν , w), y supongamos que C es un tour de Hamilton,solucion de PV . Sea v ∈ V (Kν), y estudiemos en Kν \ v el subgrafo C \ v:

Claramente, C \ v es conexo, sin ciclos (es un arbol) y contiene todos los vertices de Kν \ v, por loque es un arbol expansivo de Kν \v. Por lo tanto, si Tv es solucion del Problema de la Interconexionen Kν \ v (vease el Capıtulo 4), obtenemos que:

w(Tv) ≤ w(C \ v).

Como antes, si ej(v), j = 1, 2 son las aristas de menor peso de v, entonces:

w(Tv) + w(e1(v)) + w(e2(v)) ≤ w(C \ v) + w(e1(v)) + w(e2(v)) ≤ w(C) = PV,

y obtenemos, para cada vertice v, la cota inferior:

CI = w(Tv) + w(e1(v)) + w(e2(v)) ≤ PV,

y, finalmente,

maxv∈V (Kν)

{w(Tv)+w(e1(v))+w(e2(v))

}≤ PV

Ejemplo 6.2.1 Consideremos nuevamente el ejemplo anterior, para el cual hemos obtenido, usan-do el primer metodo, la cota inferior CI = 5.

u u

u u

1

1

1

1

3

3

a b

cd

Representamos a continuacion el grafo que se obtiene al eliminar cada uno de los 4 vertices, ası comoel arbol expansivo solucion del Problema de la Interconexion y la suma de su peso y el de las aristasde menor peso en dicho vertice:

42


Vertice a:

u

u u13

3

b

cd

u

u u13

b

cd

CI = 4 + 1 + 1 = 6

Vertice b:

CI = 2 + 1 + 3 = 6

u

u u1

1

1

a

cd

u

u u1

1

a

cd

Vertice c:

CI = 2 + 1 + 1 = 4

u u

u

1

3

a b

d

1

u u

u

1a b

d

1

Vertice d:

CI = 2 + 1 + 1 = 4

u u

u

1

1

3

a b

c

u u

u

1

1

a b

c

Ası, max{6, 6, 4, 4} = 6 ≤ PV , y vemos que, en este caso, la estimacion inferior es optima ya que,como hemos probado en la Seccion 6.2.1, PV = 6.

Observacion 6.2.2 Es una observacion elemental, pero muy importante de tener en cuenta, quesi el arbol Tv que se obtiene desde el vertice v es elemental, y al anadir las 2 aristas de peso mınimo

43


desde v, e1(v) y e2(v), obtenemos un ciclo Cv, entonces este ciclo, y su peso, nos dan la solucion dePV , ya que por un lado w(Cv) = w(Tv) +w(e1(v)) +w(e2(v)) ≤ PV , pero por la propia definicion,al ser Cv un tour de Hamilton, PV ≤ w(Cv), y por lo tanto PV = w(Cv).

Observar que esto es lo que ocurre en el Ejemplo 6.2.1 desde los vertices a y b.

6.2.3. Cota superior

Veamos un procedimiento que nos permite mejorar la cota superior obtenida al seleccionar un tourde Hamilton concreto C de Kν . Este metodo se denomina cambio de aristas:

Sea C = v1v2 · · · vivi+1 · · · vjvj+1 · · · vν−1vνv1 un tour de Hamilton de Kν , de manera que PV ≤w(C), y supongamos que existen ındices 1 ≤ i < i+ 1 < j < j + 1 ≤ ν tal que

w(vivj) + w(vi+1vj+1) < w(vivi+1) + w(vjvj+1)

u uuu u

uvi vi+1

vjvj+1

Entonces, consideramos el nuevo tour de Hamilton:

C ′ = v1 · · · vivjvj−1 · · · vi+1vj+1vj+2 · · · vνv1

que satisface PV ≤ w(C ′) < w(C), lo que nos da una mejor (menor) cota superior. Repetimos esteproceso hasta que no podamos obtener una nueva mejora.

Ejemplo 6.2.3 Veamos con un ejemplo como obtener buenas estimaciones para resolver el Proble-ma del Viajante para las capitales del Ejemplo 4.2.2. Observamos que en este caso existen 5!/2 = 60tours de Hamilton distintos:

Mediante el metodo de la primera cota inferior, obtenemos

CI =37 + 77 + 56 + 38 + 64 + 73

2=

345

2= 172, 5

y por lo tanto PV ≥ 173.

Mediante el segundo metodo, si quitamos el vertice dado por NY , obtenemos el siguiente arbolsolucion del Problema de la Interconexion, cuyo peso es igual a 122:

44


u

u

u

u

u

L

Mx

Pa

Pe

T

Como las aristas de menor peso en NY suman 56, obtenemos la cota inferior CI = 122 + 56 = 178,que mejora la primera estimacion. Ası, PV ≥ 178.

Veamos ahora que cotas superiores podemos obtener para PV . Comenzamos con el tour de HamiltonLMxNY PaPeTL, cuyo peso es de 237, por lo que PV ≤ 237:

u

u

u

u

u

L

Mx

Pa

Pe

T

uNY

56

512

78

Observamos que w(LPa)+w(MxPe) = 80 < w(LMe)+w(PaPe) = 107, ası que cambiamos dichasaristas y obtenemos el nuevo tour de Hamilton LPaNYMxPeTL, cuyo peso es de 237-27=210,por lo que PV ≤ 210:

45


u

u

u

u

u

L

Pe

T

uNY

Pa

Mx

60

78

51

70

Como antes, repetimos el mismo argumento con las nuevas aristas w(LPe) + w(MxT ) = 121 <w(LT ) + w(MxPe) = 138 y obtenemos el nuevo tour de Hamilton LPeTMxNY PaL que nos dala cota PV ≤ 210− 17 = 193.

u

u

u

u

u

L

uNY

Pa

Mx

T

Pe

51

36

51

35

Iteramos una vez mas cambiando las aristas: w(LNY ) +w(PePa) = 86 < w(PaNY ) +w(LPe) =87, y obtenemos el tour de Hamilton LPaPeTMxNY L que nos da la cota PV ≤ 193− 1 = 192.

Ası, para este grafo obtenemos las estimaciones 178 ≤ PV ≤ 192 (de hecho, se puede probar quePV = 192).

46

Capıtulo 7

Emparejamientos y Problemas deAsignacion

En este capıtulo estudiaremos la solucion al siguiente problema:

- Asignacion de Personal : En una empresa con n puestos de trabajo, hay n solicitantes. Cadacandidato elige un numero de vacantes. ¿Existe una asignacion de las solicitudes que satisfaga atodos los candidatos?

Por ejemplo, si {A,B,C,D} son las personas que optan a los puestos de trabajo {1, 2, 3, 4} con lassiguientes preferencias:

A→ {1} B → {1, 3} C → {1, 2, 3, 4} D → {3}

es facil ver que tal asignacion no es posible.

Existe un problema analogo, que no se estudiara en este curso, en el que entran en juegovaloraciones (ponderadas) de las diferentes asignaciones:

- Seleccion Optima: En este caso cada candidato recibe una nota, segun sus cualificaciones, enrelacion a cada uno de los puestos de trabajo disponibles. Queremos hacer una asignacion quemaximice los resultados. En general, si tenemos n posibilidades, es facil probar que existen un totalde n! asignaciones diferentes.

Por ejemplo, si A obtiene las valoraciones de 9 y 8 puntos para los puestos de trabajo {1, 2}(respectivamente) y analogamente B obtiene 10 y 6 puntos, la mejor asignacion posible es

A→ 2 B → 1

con una nota de 8 + 10 = 18. La otra asignacion posible (A→ 1 B → 2) solo obtendrıa una notade 9 + 6 = 15.

Ambos problemas estan dentro del contexto de la teorıa de emparejamientos, que introducimos acontinuacion.

47

CAPITULO 7. EMPAREJAMIENTOS Y PROBLEMAS DE ASIGNACION

7.1. Emparejamientos

Definicion 7.1.1 Sea G un grafo simple. Un subconjunto M ⊂ E(G) es un emparejamiento deG si cualquier par de aristas de M no son adyacentes. Un emparejamiento M satura v ∈ V (G)si v es incidente con alguna arista de M . Un emparejamiento M de G es perfecto si satura todovertice de G. Un emparejamiento M es maximal si no existe otro emparejamiento M ′ con unnumero mayor de aristas.

Observaciones 7.1.2

1. Si G tiene un emparejamiento perfecto entonces ν(G) es par. En este caso ν(G) = 2|M |.

2. Si M es perfecto, entonces M es maximal.

Ejemplo 7.1.3

uuuu uuuuu

Como ν(G) = 9, G no tiene ningun emparejamiento perfecto. Por lo tanto, si M es un empareja-miento maximal, |M | ≤ 4. Sin embargo, vemos que el maximo de aristas disjuntas que podemosencontrar es de 3:

uuuu uuuuu

Veremos mas adelante (Ejemplo 7.1.8) como probar que, en efecto, cualquier emparejamiento ma-ximal tiene 3 aristas.

48

7.1. EMPAREJAMIENTOS

Ejemplo 7.1.4 Emparejamiento perfecto con |M | = 4:

u uuuuuu

uDefinicion 7.1.5 Sea M un emparejamiento de G. Se dice que un camino elemental de G es M-alternado si sus aristas estan alternativamente en M . Un camino M -alternado es M-aumentadosi los extremos no estan M -saturados.

Ejemplo 7.1.6 Si M = {bc, de}, entonces abcdef es un camino M -aumentado.

u u u

u u u

b c f

a d e

Teorema 7.1.7 (Berge, 1957). Un emparejamiento M de G es maximal si, y solo si, G nocontiene un camino M -aumentado.

Demostracion. Si G contiene un camino L que es M -aumentado, consideremos la diferencia simetri-ca:

M ′ = (M \ E(L)) ∪ (E(L) \M) = M∆E(L).

uuuuuu

L

uuuuuu

M ′

Claramente |M ′| > |M |, ya que en L hay menos aristas de M que de su complementario, y M ′ esun emparejamiento, por lo que M no es maximal.

49


Recıprocamente, si M no es maximal, podemos encontrar M∗ maximal tal que |M∗| > |M |. SeaH = G[M∆M∗] (grafo generado por las aristas de M∆M∗). Observamos que los vertices de Htiene grado 1 o 2, y por lo tanto sus componentes conexas o son ciclos de orden par o son caminoselementales con aristas alternativamente en M y M∗.

uu u

u u

u

u uuuuu

uu u

u u

u

u uuuuu

M M∗

u u

u u u uuuuu

H

Es facil ver que existe una componente conexa de H que no es un ciclo (en caso contrario |M | =|M∗|) y, ademas, esta componente ha de ser un camino M -aumentado (en caso contrario |M | ≥|M∗|). �

Ejemplo 7.1.8 Volviendo al Ejemplo 7.1.3, observamos que el emparejamiento M de la figura esmaximal pues no contiene ningun camino M -aumentado

Definicion 7.1.9 Sea G un grafo y S ⊂ V (G). Se define el conjunto de vecinos de S como:

N(S) = {v ∈ V (G) : existe u ∈ S, uv ∈ E(G)}.

50

7.1. EMPAREJAMIENTOS

Ejemplo 7.1.10 Si S = {c}, entonces N(S) = {a, b}.

uu ua b

c

Teorema 7.1.11 (Hall, 1935). Sea G = (X,Y ) un grafo bipartito. Entonces G contiene unemparejamiento que satura X si, y solo si, para todo S ⊂ X, se verifica que |N(S)| ≥ |S|.

Ejemplo 7.1.12 En el siguiente grafo bipartito, no existe un emparejamiento perfecto (que sature{a, b, c, d} y necesariamente {1, 2, 3, 4}) pues tomando S = {a, b, d} observamos que N(S) = {1, 3}y no se cumple el Teorema de Hall.

u u u u

u u u u

a b c d

1 2 3 4

Como consecuencia del Teorema 7.1.11 se prueba el siguiente resultado, que nos permite asegurarla existencia de emparejamientos perfectos en grafos bipartitos, bajo algunas condiciones previas:

Corolario 7.1.13 (Teorema del Matrimonio). Si G es un grafo bipartito k-regular, entoncesexiste un emparejamiento perfecto.

Demostracion. Si G = (X,Y ), entonces |E(G)| = k|X| = k|Y |, de lo que se deduce que |X| = |Y |.Veamos que, para todo S ⊂ X, |S| ≤ |N(S)|:

Sean E1 y E2 los conjuntos de aristas incidentes con S y N(S), respectivamente. ClaramenteE1 ⊂ E2 (pues si un extremo de la arista de E1 esta en S, por definicion el otro extremo estara enN(S)). Ası, k|S| = |E1| ≤ |E2| = k|N(S)|, y se deduce el resultado. �

Ejemplo 7.1.14 Ejemplo de grafo bipartito 2-regular y de un posible emparejamiento perfecto:

u u u u

u u u u

a b c d

1 2 3 4

51


7.2. Problema de la Asignacion de Personal. Metodo Hungaro

Estudiamos el siguiente algoritmo que nos permite construir un emparejamiento perfecto, en caso deque exista, y en caso negativo demostrar que no existe. Partimos de un grafo bipartito G = (X,Y ),y de un emparejamiento M (que puede consistir de una sola arista):

Paso 1:

(a) Si M satura X, acabamos.

(b) Si M no satura X, elegimos u ∈ X no M -saturado, S = {u} y T = ∅.

Paso 2:

(c) Si N(S) = T , por el Teorema de Hall deducimos que no existe un emparejamientoperfecto (ya que |N(S)| < |S|).

(d) Si T N(S), tomamos y ∈ N(S) \ T .

Paso 3:

(e) Si y es M -saturado, existe yz ∈M : definimos S = S∪{z} y T = T ∪{y} y volvemosal Paso 2.

(f) Si y no es M -saturado, encontramos un camino P de u a y, M -aumentado, ycambiamos M por el emparejamiento M∆P . Volvemos al Paso 1.

Observacion: en (d) es conveniente elegir y no M -saturado, si es posible, pues elalgoritmo acaba antes en este caso.

Ejemplo 7.2.1 Consideremos el siguiente grafo bipartito con emparejamiento inicial:

M = {15}

u u u

u u u

1 2 3

4 5 6

Como M no satura X = {1, 2, 3}, tomamos u = 3, que no es M -saturado, y escribimos S = {3} yT = ∅.

Como T N(S) = {5, 6}, tomamos 5 ∈ N(S) \ T , que es M -saturado con el vertice 1.

52

7.2. PROBLEMA DE LA ASIGNACION DE PERSONAL. METODO HUNGARO

Hacemos S = {1, 3} y T = {5}. Nuevamente T N(S) = {4, 5, 6}, y tomamos 6 ∈ N(S) \ T , queno es M -saturado.

Calculamos el camino M -aumentado que va de este vertice al primero de todos u = 3, P = 36, yobtenemos M = {15, 36}:

u u u

u u u

1 2 3

4 5 6

Como M no satura 2, volvemos a escribir S = {2} y T = ∅, y como antes, T N(S) = {4}.

Tomamos 4 ∈ N(S) \ T , que no es M -saturado y obtenemos P = 24.

Finalmente M = {15, 24, 36}, que es un emparejamiento perfecto:

u u u

u u u

1 2 3

4 5 6

Ejemplo 7.2.2 Veamos otro ejemplo, esquematicamente:

u u u

u u u

1 2 3

4 5 6

M = {14}, S = {2} y T = ∅.

N(S) = {4}, 14 ∈M .

S = {1, 2} y T = {4}.

N(S) = {4, 5} y 5 no es M -saturado: P = 5142.

M = {15, 24}

53


u u u

u u u

1 2 3

4 5 6

S = {3} y T = ∅.

N(S) = {5, 6} y 6 ∈ N(S) \ T no es M -saturado: P = 63.

M = {15, 24, 36}

u u u

u u u

1 2 3

4 5 6

Ejemplo 7.2.3 Veamos otro ejemplo en el que se demuestra que no existe un emparejamientoperfecto:

u u u

u u u

1 2 3

4 5 6

M = {15}, S = {3} y T = ∅.

N(S) = {6} y 6 no es M -saturado: P = 36.

M = {15, 36}

u u u

u u u

1 2 3

4 5 6

S = {2} y T = ∅.

54

7.2. PROBLEMA DE LA ASIGNACION DE PERSONAL. METODO HUNGARO

N(S) = {6} y 6 ∈ N(S) \ T es M -saturado.

S = {2, 3} y T = {6}.

N(S) = {6} = T , y por lo tanto no existe un emparejamiento perfecto.

55

Capıtulo 8

Coloracion de Mapas y Grafos Planos

En 1852 Francis Guthrie propuso el problema de encontrar el menor numero de colores necesariospara pintar un mapa, de manera que paıses con frontera comun tuvieran asignados colores distintos.Es facil ver que existen mapas en los que al menos se necesitan 4 colores:

A B

C

D

En 1879 Alfred Kempe dio una primera demostracion de que 4 era el menor numero necesario, peroen 1890 Percy J. Heawood encontro un error en dicha prueba, aunque fue capaz de concluir quecon 5 colores se podıa pintar cualquier mapa.

En 1880, Peter G. Tait dio una nueva demostracion, con 4 colores, que de nuevo fue refutada porJulius Petersen en 1891.

Todos estos intentos, ademas de acotar que la solucion del problema era 4 o 5 colores, abrieronuna nueva vıa de estudio, mostrando que bastaba encontrar una coloracion optima para un numerofinito (pero elevado) de configuraciones.

No fue hasta 1976 que Kenneth Appel y Wolfgang Haken probaron en una serie de artıculos devarios cientos de paginas que, en efecto, 4 colores son suficientes (Teorema de los Cuatro Colores).Usando las ideas antes citadas, redujeron el estudio a un total de 1834 configuraciones irreducibles,comprobando con el uso de varios ordenadores que habıa siempre una solucion. Este empleo deprogramas informaticos en demostraciones matematicas ha sido el comienzo de todo un desarrolloposterior computacional (no exento de cierta polemica) en otro tipo de aplicaciones. Los calculos

57

CAPITULO 8. COLORACION DE MAPAS Y GRAFOS PLANOS

iniciales requirieron un total del 1200 horas de calculo (posteriormente el numero de configuracionesse ha reducido).

En este capıtulo veremos algunos resultados sobre la caracterizacion de grafos planos (es decir, querepresentan mapas) y el numero de colores necesarios para pintar los vertices, o las aristas, de ungrafo. Probaremos tambien el Teorema de los Seis Colores (5 requiere un poco mas de trabajo, yse deja al alumno interesado, y no hay tiempo para 4...).

8.1. Numero cromatico

Vamos a introducir una serie de parametros que determinan la complejidad de un grafo en cuantoal problema de la coloracion:

Definicion 8.1.1 Sea G un grafo simple y conexo:

χ(G) ≡ numero cromatico de vertices es el menor numero de colores con los que sepueden pintar los vertices de G de manera que, si son vecinos, tengan un color diferente.

χ′(G) ≡ numero cromatico de aristas es el menor numero de colores con los que sepueden pintar las aristas de G de manera que, si son adyacentes, tengan un color diferente.

Ejemplo 8.1.2

1. χ(G) ≥ 2 ⇐⇒ α(G) ≥ 1.

2. χ(Kn) = n.

3. χ(Cn) =

{2 si n es par,

3 si n es impar.

4. χ′(Kn) =

{n− 1 si n es par,

n si n es impar.

5. χ′(Cn) =

{2 si n es par,

3 si n es impar.

6. G es bipartito y α(G) ≥ 1 si, y solo si, χ(G) = 2.

7. ∆ ≤ χ′(G) y se puede probar que, si G es simple, entonces χ′(G) ≤ ∆ + 1 (Teorema deVizing).

Observacion 8.1.3 Que un grafo G tenga numero cromatico χ(G) = k equivale a que podemosencontrar una particion V (G) = V1 ∪ · · · ∪ Vk de manera que los vertices de cada Vj , 1 ≤ j ≤ k, nosean adyacentes. Esto permite replantear el calculo de χ(G) como la solucion del llamado Problemadel Almacenamiento:

58

8.1. NUMERO CROMATICO

Dada una familia de productos explosivos, como podemos almacenarlos de manera optima (mini-mizando el numero de contenedores) con la condicion de que productos que puedan reaccionar sise mezclan no esten juntos.

Si se representa el grafo G donde los vertices son los productos y las aristas indican que dichosproductos no se pueden mezclar, la solucion es χ(G).

El calculo de los numeros cromaticos de un grafo es, en general, un problema difıcil. Veamos unaestimacion para χ(G):

Proposicion 8.1.4 Para todo grafo simple G,

ν2

ν2 − 2α≤ χ(G) ≤ ν. (8.1)

Demostracion. Que χ(G) ≤ ν es trivial. Supongamos que V (G) = V1 ∪ · · · ∪Vk, union disjunta, conk = χ(G). Sea xj = |Vj |, de manera que

k∑

j=1

xj = ν.

Sea v ∈ Vj . Como mucho habra ν − xj aristas incidentes en v, y por lo tanto

∑kj=1 xj(ν − xj)

2≥ α. (8.2)

Usando la desigualdad de Cauchy-Schwarz:

ν =

k∑

j=1

xj ≤( k∑

j=1

x2j

)1/2

k1/2,

y obtenemos que

ν2

k≤

k∑

j=1

x2j .

Finalmente, usando (8.2):

2α ≤ ν2 −k∑

j=1

x2j ≤ ν2(

1− 1

k

),

y, despejando k,ν2

ν2 − 2α≤ k = χ(G).

�

Ejemplo 8.1.5 El siguiente grafo tiene ν = 4 y α = 5, por lo que χ(G) ≥ 16/(16 − 10) = 8/3.Ası, χ(G) ≥ 3 y es facil ver que, en efecto, χ(G) = 3, por lo que la estimacion inferior de laProposicion 8.1.4 puede ser optima:

59


x u

u zVeamos un segundo resultado que nos permitira mejorar la cota superior trivial χ(G) ≤ ν.

Definicion 8.1.6 Diremos que G es un grafo crıtico si para todo subgrafo propio H de G, sesatisface que χ(H) < χ(G). G es k-crıtico si es crıtico y χ(G) = k.

Observaciones 8.1.7

1. Si G es 1-crıtico, entonces χ(G) = 1 y por lo tanto E(G) = ∅. Ademas, al ser crıtico claramenteν(G) = 1 de lo que se concluye que G = K1.

2. Si G es 2-crıtico, χ(G) = 2 y existe e ∈ E(G). Si tomamos el subgrafo H = e, claramenteχ(H) = 2 por lo que G = H; es decir, G = K2 = K1,1.

3. Si G es 3-crıtico se prueba que G = C2n+1. Los grafos k-crıticos, con k ≥ 4, no han sidotodavıa caracterizados.

Proposicion 8.1.8 Si G es k-crıtico, entonces δ ≥ k − 1.

Demostracion. Supongamos lo contrario: G es k-crıtico y δ < k− 1. Sea v ∈ V (G) tal que g(v) = δy sea H = G \ v, que es un subgrafo propio de G. Ası, χ(H) = k − 1 (si χ(H) < k − 1 podrıamoselegir un nuevo color para pintar v de manera que χ(G) < k, lo que es una contradiccion) yV (H) = V1 ∪ · · · ∪ Vk−1, union disjunta. Como δ < k − 1, existe j ∈ {1, . . . , k − 1} tal que v no esadyacente a ningun vertice de Vj . Por lo tanto, si denotamos V ′j = Vj ∪ {v}, tenemos la siguientedescomposicion disjunta:

V (G) = V1 ∪ · · · ∪ V ′j ∪ · · ·Vk−1,y obtenemos la contradiccion de que χ(G) ≤ k − 1. �

Corolario 8.1.9 Si χ(G) = k, entonces existen al menos k vertices con grado al menos k − 1.

Demostracion. Sea H un subgrafo de G que sea k-crıtico. Por la Proposicion 8.1.8 tenemos queδH ≥ k − 1, y todo vertice de H tiene al menos grado k − 1. Como νH ≥ χ(H) = k, en H hayal menos k vertices, con grado al menos k − 1. Claramente, si v ∈ V (H), gG(v) ≥ gH(v) y en Gencontramos al menos k vertices con grado al menos k − 1. �

Corolario 8.1.10 χ(G) ≤ ∆ + 1.

60

8.2. GRAFOS PLANOS

Demostracion. Si χ(G) = k, G tiene al menos k-vertices (y por lo tanto UNO) con grado al menosk − 1. Ası,

∆ ≥ k − 1 = χ(G)− 1.

�

Observacion 8.1.11 Si G es simple, ∆ ≤ ν − 1, y por lo tanto el Corolario 8.1.10 es una mejorade la cota superior de (8.1):

χ(G) ≤ ∆ + 1 ≤ ν.El Teorema de Brook nos permite todavıa mejorar esta estimacion: si G es conexo y no es ni unciclo de orden impar, ni un grafo completo, entonces χ(G) ≤ ∆.

8.2. Grafos planos

Definicion 8.2.1 Un grafo G es plano si las aristas no tienen ningun cruce. Un grafo G es planarsi es isometrico a un grafo plano.

Veremos que ni K5 ni K3,3 son grafos planares y, esencialmente, todo grafo que no sea planarcontiene una copia de uno de ellos.

Demostracion. Sea H un subgrafo de G que sea k-crıtico. Por la Proposicion 9.1.7 tenemosque δH ≥ k−1, y todo vertice de H tiene al menos grado k−1. Como νH ≥ χ(H) = k, en Hhay al menos k vertices, con grado al menos k − 1. Claramente, si v ∈ V (H), gG(v) ≥ gH(v)y en G encontramos al menos k vertices con grado al menos k − 1. �

Corolario 9.1.9 χ(G) ≤ ∆ + 1.

Demostracion. Si χ(G) = k, G tiene al menos k-vertices (y por lo tanto UNO) con grado almenos k − 1. Ası,

∆ ≥ k − 1 = χ(G) − 1.

�

Observacion 9.1.10 Si G es simple, ∆ ≤ ν − 1, y por lo tanto el Corolario 9.1.9 es unamejora de la cota superior de (9.1):

χ(G) ≤ ∆ + 1 ≤ ν.

El Teorema de Brook nos permite todavıa mejora esta estimacion: si G es conexo y no es niun ciclo de orden impar, ni un grafo completo, entonces χ(G) ≤ ∆.

9.2. Grafos planos

Definicion 9.2.1 Un grafo G es plano si las aristas no tienen ningun cruce. Un grafo Ges planar si es isometrico a un grafo plano.

Veremos que ni K5 ni K3,3 son grafos planares y, esencialmente, todo grafo que no sea planarcontiene una copia de uno de ellos.

✉ ✉

✉ ✉

✉ ✉

✉ ✉63

Aquı vemos como K4 es planar, pues el grafo de la derecha es una representacion plana del de laizquierda.

Es facil ver que una mapa (en el que los paıses son conexos) se puede representar mediante ungrafo plano, identificando los vertices con cada paıs, y estableciendo la relacion de adyacencia si lospaıses tienen una frontera en comun. Y recıprocamente, todo grafo plano representa un mapa. Porejemplo, el grafo asociado a Alemania, Belgica, Francia y Luxemburgo es K4:

61


No es trivial determinar cuando un grafo es planar. Veamos algunos resultados que nos ayudarana estudiar este problema:

Definicion 8.2.2 Un grafo H es una subdivision de G, si se obtiene a partir de G anadiendovertices en sus aristas.

Ejemplo de un grafo G y de una subdivision H:

u

u u

u

G H

u

u u

uuu uu

Observacion 8.2.3

1. Si H es una subdivision de G, entonces H es planar si, y solo si, G es planar.

2. Cn es una subdivision de Cm, si n > m.

3. Si H es un subgrafo de G y G es planar, entonces H es planar.

4. Si G contiene un subgrafo que es una subdivision de un grafo no planar, entonces G no esplanar.

Definicion 8.2.4 Si G es un grafo plano, llamaremos caras de G a las regiones del plano deli-mitadas por sus aristas; es decir, las componentes conexas de R2 \ G. La cara (componente) noacotada se denomina cara exterior de G. El numero de caras de G se representa como C(G).

Ejemplo 8.2.5

1. Si G = K2, G solo tiene una cara (que es la exterior). En general, si G es un arbol, entoncesC(G) = 1.

2. C(Cn) = 2, si n ≥ 3.

3. C(K4) = 4.

Teorema 8.2.6 (Teorema de la Caracterıstica de Euler). Si G es un grafo plano, entonces:

ν − α+ C = 2.

62

8.2. GRAFOS PLANOS

Demostracion. Lo haremos por induccion en ν:

Si ν = 1, entonces α = 0 y C = 1, por lo que ν−α+C = 1−0+1 = 2. Supongamos el resultado ciertopara ν = k y sea G tal que ν(G) = k + 1. Tomemos v ∈ V (G) y hagamos H = G \ v. Claramenteν(H) = ν(G) − 1 y α(H) = α(G) − g(v). Como v esta en una cara de H, que sera isomorfa a unciclo, es inmediato que

C(G) = C(H)− 1 + g(v).

u

uu

uuuv

Cara de H en la que esta v

u

uu

uuuv

Caras que se forman al anadir v

Usando estos datos y la hipotesis de induccion:

2 = ν(H)− α(H) + C(H)

= ν(G)− 1− α(G) + g(v) + C(G) + 1− g(v)

= ν(G)− α(G) + C(G).

�

Observacion 8.2.7 Observamos que si G es un arbol, como C(T ) = 1, obtenemos que α =ν + 1− 2 = ν − 1.

Definicion 8.2.8 Un grafo plano es maximal, si al anadirle una arista, entre 2 vertices no ad-yacentes, no es planar.

Observacion 8.2.9 Cn es maximal si, y solo si, n = 3. En particular, G es maximal si, y solo si,todas las caras de G son triangulos.

Corolario 8.2.10 Si G es plano y maximal, entonces α = 3ν − 6. Si G es plano y todas las carasson isomorfas a C4, entonces α = 2ν − 4.

Demostracion. Si G es maximal, todas las caras son triangulos y por lo tanto 3C = 2α. Ası, por elTeorema 8.2.6:

ν − α+2

3α = 2 ⇒ 3ν − 6 = α.

Analogamente, si las caras son C4, entonces 4C = 2α y

ν − α+α

2= 2 ⇒ 2ν − 4 = α.

�

63


Corolario 8.2.11 Kn no es planar si, y solo si, n ≥ 5.

Demostracion. Basta probar que K5 no es planar. Si lo fuera, al ser completo serıa maximal, yhabrıa de satisfacerse la igualdad 3ν − 6 = α. Pero 3 · 5− 6 = 9 6= 10. �

Corolario 8.2.12 K3,3 no es planar.

Demostracion. Si lo fuera, todas las caras serıan C4, y habrıa de satisfacerse la igualdad 2ν−4 = α.Pero 2 · 6− 4 = 8 6= 9. �

Definicion 8.2.13 Dado G, llamaremos numero de corte de G al menor numero de cruces dearistas posible al representar todas las copias isomorfas de G. Este numero se denomina cr(G).

Observacion 8.2.14 Un grafo G es planar si, y solo si, cr(G) = 0.

Ejemplo 8.2.15

1. cr(K5) = cr(K3,3) = 1.

Ejemplo 9.2.15

1. cr(K5) = cr(K3,3) = 1.

✉

✉ ✉✉✉

✉ ✉ ✉

✉ ✉ ✉cr(K5) = cr(K3,3) = 1

2. El grafo de Petersen, P , no es planar (vease la Observacion 1.3.39) y cr(P ) = 2. Enefecto, veamos que P contiene una subdivision de K3,3:

El grafo de la izquierda es isomorfo a K3,3, que no es planar, y el de la derecha, H, esuna subdivision de K3,3, y por lo tanto tampoco es planar.

✉ ✉ ✉✉ ✉

✉ ✉ ✉ ✉✉ ✉

✉✉

✉ ✉

✉

K3,3 H

✉ ✉ ✉✉ ✉

✉✉

✉ ✉

✉

P

Como H es un subgrafo de P , se deduce que el grafo de Petersen no es planar. Ası,cr(P ) ≥ 1. Por otro lado, es facil ver que P es isomorfo al siguiente grafo, que solotiene 2 cruces de aristas, y se deduce que 1 ≤ cr(P ) ≤ 2:

67

2. El grafo de Petersen, P , no es planar (vease la Observacion 1.4.39) y cr(P ) = 2. En efecto,veamos que P contiene una subdivision de K3,3:

El grafo de la izquierda es isomorfo a K3,3, que no es planar, y el de la derecha, H, es unasubdivision de K3,3, y por lo tanto tampoco es planar.

64

8.2. GRAFOS PLANOS

u u uu uu u u uu uuu

u u

u

K3,3 H

u u uu uuu

u u

u

P

Como H es un subgrafo de P , se deduce que el grafo de Petersen no es planar. Ası, cr(P ) ≥ 1.Por otro lado, es facil ver que P es isomorfo al siguiente grafo, que solo tiene 2 cruces de aristas,y se deduce que 1 ≤ cr(P ) ≤ 2:

u uu uuu u uu

uVeamos que cr(P ) = 2. En caso contrario, si cr(P ) = 1, existirıa un vertice v ∈ V (P ) tal quecr(P \ v) = 0. Pero es facil ver que en P \ v se puede encontrar siempre otra subdivision de K3,3,lo que es una contradiccion. Por lo tanto, cr(P ) = 2.

El siguiente resultado da una caracterizacion completa de cuando un grafo es planar, y muestraque K5 y K3,3 son los grafos minimales no planares:

Teorema 8.2.16 (Kuratowski, 1930). Un grafo G es planar si, y solo si, no contiene ningunasubdivision de K5 o de K3,3.

Proposicion 8.2.17 Si G es simple y ν ≥ 3, entonces α− 3ν + 6 ≤ cr(G).

65


Demostracion. Si cr(G) = 0, entonces por el Corolario 8.2.10 se deduce que α ≤ 3ν−6, que es lo quequeremos probar. Si cr(G) = k, k ≥ 1, podemos quitar k aristas en G y obtener un subgrafo H de Gsatisfaciendo que cr(H) = 0. Usando la hipotesis de induccion, se tiene que α(H)− 3ν(H) + 6 ≤ 0,y como α(G) = α(H) + 6 y ν(G) = ν(H) finalmente probamos que:

α(G)− k − 3ν(G) + 6 = α(G)− 3ν(G) + 6− cr(G) ≤ 0.

�

Corolario 8.2.18 cr(K6) = 3.

Demostracion. La siguiente representacion muestra que cr(K6) ≤ 3:

u u

u u

u u

Por otro lado, usando el Corolario 8.2.17 obtenemos que:

α− 3ν + 6 = 15− 3 · 6 + 6 = 3 ≤ cr(K6).

�

Observacion 8.2.19 solo se conocen los valores de cr(Kn) para n = 1, . . . , 12. Hasta n = 10 loprobo R.K. Guy en 1972 y para n = 11, 12 el resultado es de S. Pan y R.B. Richter (2007):

n 1 2 3 4 5 6 7 8 9 10 11 12

cr(Kn) 0 0 0 0 1 3 9 18 36 60 100 150

Guy conjeturo que si

Z(n) =1

4

[n

2

][n− 1

2

][n− 2

2

][n− 3

2

],

entonces Z(n) = cr(Kn), que coincide con la solucion para n = 1, . . . , 12. Se sabe que

0, 8594 · Z(n) ≤ cr(Kn) ≤ Z(n).

66

8.3. COLORACION DE MAPAS

8.3. Coloracion de mapas

Estudiamos el problema de la coloracion de mapas, es decir, de grafos planos. El resultado principalde esta teorıa es el llamado Teorema de los Cuatro Colores, que nos asegura que para todo grafoplano, χ(G) ≤ 4. Por lo comentado en la introduccion, dada la complejidad de su demostracion, noes factible darla en este curso, y nos conformaremos con probarlo para seis colores.

La demostracion esta basada en el siguiente resultado auxiliar:

Lema 8.3.1 Si G es un grafo planar, entonces δ ≤ 5.

Demostracion. Podemos suponer que ν ≥ 6. Por la Proposicion 8.2.17, como cr(G) = 0, tenemosque α ≤ 3ν − 6. Ası,

δν ≤∑

v∈V (G)

g(v) = 2α ≤ 6ν − 12,

lo que nos da la estimacion

δ ≤ 6− 12

ν< 6,

es decir, δ ≤ 5. �

Teorema 8.3.2 (Teorema de los Seis Colores). Si G es un grafo planar, entonces χ(G) ≤ 6.En particular todo mapa se puede pintar con 6 colores.

Demostracion. Lo haremos de manera inductiva. El resultado es obvio si ν ∈ {1, 2, 3, 4, 5, 6}. Su-pongamos que todo grafo planar con ν = k se puede pintar con 6 colores, y sea G un grafo planocon ν(G) = k + 1.

Sea v ∈ V (G) tal que g(v) = δ ≤ 5 (por el Lema 8.3.1), y sea H = G \ v, que es un grafo planarcon ν(H) = k. Ası, χ(H) ≤ 6. Como g(v) ≤ 5, existe un color, del 1 al 6, que no se ha usado paracolorear los δ vecinos de v. Por lo tanto, si pintamos v de este color, tenemos una coloracion de G,con a lo mas 6 colores. Es decir, χ(G) ≤ 6. �

67

Capıtulo 9

Ejercicios

1. Representar graficamente todas las moleculas de los hidrocarburos alcanos del tipo CnH2n+2,n = 3, 4, 5. ¿Cuantos vertices y aristas tiene cada molecula?

2. Estudiar si son isomorfos los siguientes grafos:

(a)

Teorıa de Grafos. Curso 2007-08

Hoja 1

1. Representar graficamente las moleculas de los hidrocarburos alcanos del tipo CnH2n+2,n = 3, 4, 5. ¿Cuantos vertices y aristas tiene cada molecula?


(a)

!

!

!

!

!

!

!

! !

!

!

! !

!

!

!(b)

(c)

1

(b)

Teorıa de Grafos (2009/10). Hoja 1

1. Representar graficamente todas las moleculas de los hidrocarburos alcanos del tipo CnH2n+2, n =3, 4, 5. ¿Cuantos vertices y aristas tiene cada molecula?


(a)


Hoja 1



(a)

!

!

!

!

!

!

!

! !

!

!

! !

!

!

!(b)

(c)

1

(b)

!

!

!

!

!

!

!

!"#$%

"#$%

!

!

!

!

!

!

!

!!

(d)! ! !

! ! !

!!

! !!

!

3. Para cada k = 0, 1, . . . , 5, representar graficamente (si es posible) algun grafo que tenga la siguientesucesion de grados: {0, . . . , k}.

4. Demostrar que en todo grafo simple con mas de 2 puntos, siempre existen al menos 2 vertices con elmismo grado.

5. Encontrar una representacion de K6 con el menor numero de cortes posible.

6. Representar todos los grafos simples r- regulares, para r = 0, · · · , ! ! 1 y ! = 1, · · · , 5.

7. Demostrar que " " 2#/! " !.

8. Demostrar que si G es un grafo simple, entonces # " !(! ! 1)/2. Probar que la igualdad se alcanzasi y solo si G = K! .

9. Demostrar que si G es un arbol y e # E(G), entonces G \ e tiene 2 componentes conexas que sonarboles.

10. Demostrar que si G es un grafo simple y conexo, entonces ! ! 1 " #. Probar que la igualdad sealcanza si y solo si G es un arbol.

(c)

Teorıa de Grafos. Curso 2008-09Hoja 1



(a)


Hoja 1



(a)

!

!

!

!

!

!

!

! !

!

!

! !

!

!

!(b)

(c)

1

(b)

!

!

!

!

!

!

!

!"#$%

"#$%

(c) !

!

!

!

!

!

!

!!

(d) ! ! !

! ! !

!!

! !!

!(d)

Teorıa de Grafos. Curso 2008-09Hoja 1



(a)


Hoja 1



(a)

!

!

!

!

!

!

!

! !

!

!

! !

!

!

!(b)

(c)

1

(b)

!

!

!

!

!

!

!

!"#$%

"#$%

(c) !

!

!

!

!

!

!

!!

(d) ! ! !

! ! !

!!

! !!

!

3. Para cada k = 0, 1, . . . , 5, representar graficamente (si es posible) algun grafo que tenga lasiguiente sucesion de grados {0, . . . , k}.

4. Estudiar si existen grafos con las siguientes sucesiones de grados y las propiedades que seindican. En caso afirmativo, encontrar todos los grafos no isomorfos:

a) {1, 2, 4, 6, 8, . . . , 98, 100}.b) {0, 2, 2, 2, 2, . . . , 2, 2} y conexo.

c) {2, 2, 3, 3, 4} y simple.

d) {1, 2, 3, . . . , 8, 9, 10} y simple.

e) {1, 2, 2, 3, 4, 4, 5, 5} y arbol.

f ) {2, 2, 2, 2, 2, 2} y simple.

5. Probar que en todo grafo simple, si ν ≥ 2, existen al menos 2 vertices con el mismo grado.

6. Encontrar una representacion de K6 con el menor numero de cortes posible.

69

CAPITULO 9. EJERCICIOS

7. Representar todos los grafos simples r- regulares, para r = 0, · · · , ν − 1 y ν = 1, · · · , 5.

8. Demostrar que δ ≤ 2α/ν ≤ ∆. Estudiar los casos en los que se puede dar alguna de las 2igualdades.

9. Demostrar que si G es un grafo simple, entonces α ≤ ν(ν − 1)/2. Probar que la igualdad sealcanza si y solo si G = Kν .

10. Dado n ∈ N \ {1} se define Phi[n] como el conjunto de los numeros menores que n, distintosde 1, que son primos relativos con n. En Phi[n] se define un grafo simple, Grafo[n], quetiene como vertices los elementos de Phi[n], con la relacion de que 2 vertices distintos sonadyacentes si (los numeros correspondientes) no son primos entre sı.

Dibujar Grafo[n], para n = 3, 4, · · · , 10. Estudiar si estos grafos son isomorfos. Hacer lo mismopara n = 24, 30.

Ejemplo para n = 7:

Grafo[7]

11. Demostrar que si G es un arbol y e ∈ E(G), entonces G \ e tiene 2 componentes conexas queson arboles.

12. Demostrar que si G es un grafo simple y conexo, entonces ν − 1 ≤ α. Probar que la igualdadse alcanza si y solo si G es un arbol.

13. Contar el numero de caminos elementales entre 2 vertices cualesquiera de Cn. Lo mismo paraKn.

14. Demostrar que todo camino (camino simple) contiene un camino simple (elemental) quecomienza y acaba en los mismos vertices que el original.

15. Escribir todos los caminos elementales entre y y s del siguiente grafo:

x x x x

x x x xv u y x

s t z w

70

16. Escribir todos los ciclos de longitudes 1, 2, 3 y 4 del siguiente grafo:

u u

u� �� ux w

u v

17. Demostrar que si G es un grafo simple y k ≤ δ, entonces G tiene un camino elemental delongitud k. Probar con un ejemplo que si k > δ, el resultado puede ser falso.

18. Si G es un arbol y ν ≥ 2 demostrar que δ = 1, y existen al menos 2 vertices cuyo grado es 1(hojas). ¿Es cierto el recıproco?

19. Caracterizar los arboles que tienen exactamente 2 hojas. Caracterizar los arboles con ν verticesy que tienen el mayor numero de hojas.

20. Demostrar que si un arbol tiene solo 3 hojas, entonces ν ≥ 4, ∆ = 3 y tiene un unico verticede grado maximo.

21. Demostrar que un arbol es un grafo bipartito.

22. Demostrar que un grafo conexo es bipartito si y solo si todo ciclo tiene un numero par dearistas.

23. Dibujar todos los arboles con ν ∈ {1, . . . , 6}.

24. Caracterizar los arboles T tales que:

(a) D(T ) = ν − 1 (b) D(T ) = 2.

25. Demostrar que si G es conexo, entonces (V, d) es un espacio metrico.

26. Calcular el diametro de los siguientes grafos:

(a) Kn (b) Km,n (c) Cn (d) Pn.

Observar que existen grafos cuyo diametro es 1 y δ es arbitrariamente grande, y otros con∆ = 2 y diametro arbitrariamente grande.

27. Se define el radio de un grafo G como r = r(G) = mıny∈V

[maxx∈V d(x, y)

].

Demostrar que r ≤ D ≤ 2r. Demostrar con sendos ejemplos que puede ocurrir que r = D oque 2r = D.

28. Demostrar que no existen grafos 3-regulares con un numero impar de vertices. Estudiar laexistencia de grafos simples 3-regulares, planos, con diametro 3 y con ν ∈ {4, 6, 8, 10, 12}.

29. Encontrar una cota superior del numero de grafos simples que puede haber con ν vertices yα aristas. Encontrar todos los casos posibles (no isomorfos) para ν ∈ {1, 2, 3, 4}.

71


30. Demostrar que todo grafo conexo contiene un subgrafo con el mismo numero de vertices yque es un arbol.

31. Estudiar el numero de vertices, el grado maximo, el diametro (indicar 2 puntos con distanciamaxima) y la constante de Moore de los siguientes grafos:

(a)

uuu uu

u

u u

u u

Grafo de Petersen

(b) (c)

vvvvvv vvvv

vv

32. Calcular la matriz de adyacencia de Kn y de Kn,m. ¿Cual es el espectro de Kn?

33. (i) Calcular la matriz de incidencia y de adyacencia del grafo del ejercicio [2 (a)].

(ii) Representar los grafos cuyas matrices de adyacencia son:

(a)

0 1 0 1 11 0 0 0 10 0 0 0 01 0 0 0 21 1 0 2 0

(b)

2 2 1 02 2 2 11 2 2 00 1 0 2

(iii) Representar los grafos cuyas matrices de incidencia son:

(a)

1 1 1 1 0 0 0 01 1 0 0 1 1 0 00 0 0 0 0 0 0 00 0 0 1 0 1 1 10 0 1 0 1 0 1 1

(b)

1 1 1 0 0 01 0 0 1 0 00 1 0 0 1 00 0 1 0 0 10 0 0 1 1 1

72

34. Sea G un grafo:

(a) Demostrar que Γ(G) (automorfismos de G), tiene estructura de grupo.

(b) Calcular Γ(Kn) y Γ(C4). Estudiar si son abelianos.

35. Dados los siguientes grafos, calcular el polinomio caracterıstico de la matriz de adyacencia,encontrar Γ y estudiar si son isomorfos:

uuu

uuu uuuuu

u36. Encontrar el valor mınimo de ν(G) ≥ 2 para que exista un grafo simple G de manera que

Γ(G) solo contenga la identidad.

37. Calcular el maximo numero de pasos que requiere el algoritmo de Dijkstra en un grafo pon-derado con ν vertices.

38. Una companıa tiene delegaciones en seis ciudades C1, C2, . . . , C6. La tarifa de un vuelo directoentre las ciudades Ci y Cj , viene dada por el elemento (i, j) de la siguiente matriz (- indicaque no existe tal vuelo):

0 50 − 40 25 1050 0 15 20 − 25− 15 0 10 20 −40 20 10 0 10 2525 − 20 10 0 5510 25 − 25 55 0

¿Cuales son, y cuanto valen, las rutas mas baratas entre las ciudades Ci y Cj?

39. Las distancias entre los siete pueblos de una comarca vienen dadas por el siguiente mapa decarreteras:

v

v

v

v

v

s

v

v

A

B

C

D

E

G

F

30

50

19

40

6

12 23

35

11

8

20

10

Encontrar el camino mas corto entre A y G.

73


40. Determinar los puentes y los vertices de corte del grafo:

v

v

vv v

v

vv

vv

A

Representar todos los posibles arboles expansivos que se obtienen al aplicar el algoritmo deDijkstra empezando en el vertice A.

41. Demostrar que si G es un grafo conexo entonces, e ∈ E es un puente, si y solo si e no pertenecea ningun ciclo de G. Probar que un grafo G conexo es un arbol si y solo si todas las aristasde G son puentes.

42. Representar todos los arboles expansivos del grafo:

v v

v v

v

v¿Cuantos tipos no isomorfos hay?

43. Calcular τ(Cn), n = 1, 2, . . . Lo mismo para τ(Kn), n = 3, 4, 5.

44. Sea Cn +m el grafo formado por el ciclo Cn junto con m copias anadidas de una unica arista(ası Cn + 0 = Cn). Calcular τ(Cn +m).

45. Calcular el numero de arboles expansivos del grafo de Petersen (vease el ejercicio 31).

46. Usando la formula de Cayley, calcular τ(G), siendo G:

uu u

u

uu u

uu

u

47. Calcular el numero de arboles expansivos del siguiente grafo:

74

ss ss sssss

s ss

ssssssssss

s

s

48. a) Estudiar si es cierto que si G es un grafo conexo y simple, H ⊂ G es un subgrafo conexoy T es un arbol expansivo de G, entonces H ∩ T es un arbol expansivo de H.

b) Calcular el numero de arboles expansivos del siguiente grafo y dar un ejemplo concretode un arbol expansivo:

u uuu

uuuuuu

uuu

u

u uu u

c) Para el grafo anterior, calcular δ, ∆ y D (el diametro).

49. Calcular el numero de arboles expansivos del siguiente grafo y dar un ejemplo concreto de unarbol expansivo:


✈

✈ ✈✈✈

✈ ✈✈✈ ✈

✈✈ ✈

✈✈✈ ✈

✈✈

✈✈

✈

50. Encontrar un ejemplo de un grafo ponderado cuya solucion para el problema de la intercone-xion no sea la solucion para el problema del camino mınimo, desde ninguno de sus vertices.

51. Demostrar que todo subgrafo sin ciclos y maximal de un grafo conexo es, necesariamente, unarbol expansivo.

52. Demostrar que si G es conexo, T es un arbol expansivo de G y e es un puente de G, entoncese pertenece a T .

53. Sea G un grafo ponderado y supongamos que existe e ∈ E(G) tal que w(e) > w(f), para todaf ∈ E(G) \ {e}. Demostrar que si e pertenece a un arbol expansivo optimo de G, entonces ees un puente de G.

54. Describir todas las clases isomorfas de los grafos simples que contienen a Pn como un arbolexpansivo, n = 3, 4.

55. Representar todos los arboles expansivos de Kn, n = 3, 4. ¿Cuanto tiempo (en anos) llevarıarepresentar todos los arboles expansivos de K10 si tardaramos 1 segundo por cada arbol?

56.Calcular el peso de todos los arboles expansivos delgrafo:

✈ ✈

✈ ✈21 3

4

5

57.

El primero de los siguientesgrafos ponderados representalas distancias, en kilometros,entre cuatro ciudades, y el se-gundo muestra el cociente deesta distancia, dividido por lasuma de las respectivas pobla-ciones de cada ciudad, y mul-tiplicado por un millon.

✈✈ ✈

✈T

B

G

L

✈✈ ✈

✈T

B

G

L

19692, 5

86, 580, 5

145, 5

21117

16

28

83

Calcular, en cada uno de los dos casos, el camino minimal desde cada ciudad a las tresrestantes (usando el algoritmo de Dijkstra), y la solucion del problema de la interconexion(usando el algoritmo de Kruskal).

76

50. Encontrar un ejemplo de un grafo ponderado cuya solucion para el problema de la intercone-xion no sea la solucion para el problema del camino mınimo, desde ninguno de sus vertices.

75


51. Demostrar que todo subgrafo sin ciclos y maximal (es decir, que no esta contenido en otrosubgrafo sin ciclos), de un grafo conexo es, necesariamente, un arbol expansivo.

52. Demostrar que si G es conexo, T es un arbol expansivo de G y e es un puente de G, entoncese pertenece a T .

53. Sea G un grafo ponderado y supongamos que existe e ∈ E(G) tal que w(e) > w(f), para todaf ∈ E(G) \ {e}. Demostrar que si e pertenece a un arbol expansivo optimo de G, entonces ees un puente de G.

54. Describir todas las clases isomorfas de los grafos simples que contienen a Pn como un arbolexpansivo, n = 3, 4.

55. Representar todos los arboles expansivos de Kn, n = 3, 4. ¿Cuanto tiempo (en anos) llevarıarepresentar todos los arboles expansivos de K10 si tardaramos 1 segundo por cada arbol?

56.Calcular el peso de todos los arboles expansivos delgrafo:

v v

v v21 3

4

5

57.

El primero de los siguientesgrafos ponderados representalas distancias, en kilometros,entre cuatro ciudades, y el se-gundo muestra el cociente deesta distancia, dividido por lasuma de las respectivas pobla-ciones de cada ciudad, y mul-tiplicado por un millon.

vv vvT

B

G

L

vv vvT

B

G

L

19692, 5

86, 580, 5

145, 5

21117

16

28

83

Calcular, en cada uno de los dos casos, el camino minimal desde cada ciudad a las tresrestantes (usando el algoritmo de Dijkstra), y la solucion del problema de la interconexion(usando el algoritmo de Kruskal).

58.

Una companıa tiene delegaciones en seis ciudadesC1, C2, . . . , C6. La tarifa de un vuelo directo entre lasciudades Ci y Cj , viene dada por el elemento (i, j) dela siguiente matriz (- indica que no existe tal vuelo).¿Que rutas permiten conectar todas las ciudades conun coste mınimo?

0 50 − 40 25 1050 0 15 20 − 25− 15 0 10 20 −40 20 10 0 10 2525 − 20 10 0 5510 25 − 25 55 0

59.

La siguiente tabla muestra la distancia entre lasislas de un archipielago. Calcular la ruta marıti-ma que permite viajar entre cualquier par de is-las, posiblemente haciendo escala en puertos in-termedios, minimizando la distancia total y cal-cular esa distancia.

A B C D E FA 0 20 12 22 17 41B 20 0 11 21 19 25C 12 11 0 28 33 9D 22 21 28 0 27 16E 17 19 33 27 0 43F 41 25 9 16 43 0

76

60. El coste de la transmision de datos entre las distintas antenas de una red de telefonıa, nume-radas por n = 1, . . . , 5, viene tabulado por la siguiente funcion:

C(n,m) = ((−1)n+mn−m)2(6− n)(6−m).

Calcular la menor red que comunica todas las antenas con un coste mınimo.

61.

Encontrar dos redes viarias distin-tas, que comuniquen todos los pue-blos del grafo ponderado, cuyas lon-gitudes sean la menor posible y cal-cular esta distancia.

v v

v v

v

vv

5

2

4

3 3

1 1

2

9

6

5

62. A partir del plano del Metro de Barcelona (lıneas L1,. . . , L5) generamos el siguiente grafoponderado: conservamos como vertices las estaciones que son principio o fin de lınea, y tambienaquellas que pertenecen a varias lıneas. La distancia entre los vertices es igual al numerode estaciones comprendidas entre ambos mas 1. Calcular la solucion del problema de lainterconexion.

63. ¿Cual de las siguientes figuras se puede dibujar de un solo trazo, sin repetir las lıneas mas deuna vez? En caso afirmativo, representarlo esquematicamente:

77


64. Estudiar si se puede encontrar un recorrido, no necesariamente cerrado, que atraviese todoslos puentes del siguiente mapa una sola vez, y representar graficamente una solucion en casoafirmativo:

65. Demostrar que si G es un grafo conexo, entonces G contiene un camino de Euler si y solo siexisten solo 2 vertices de grado impar.

66. ¿Cuales de los siguientes grafos son eulerianos? ¿Cuales admiten un camino de Euler?

(a) Kn (b) Kn,m (c) Cn (d) Petersen (e) un arbol

67. Calcular el numero de tours eulerianos de K5.

68. Demostrar que si un grafo conexoG se puede poner como union de ciclos (i.e.,G = C1∪· · ·∪Ck,y dos de estos ciclos no comparten aristas), entonces G es euleriano.

69. Estudiar cuales de los siguiente grafos admite una descomposicion como la del ejercicio ante-rior, y en caso afirmativo escribirla explıcitamente:


Hoja 5

41. ¿Cual de las siguientes figuras se puede dibujar de un solo trazo, sin repetir las lıneasmas de una vez? En caso afirmativo, representar esquematicamente como se puedehacer:

42. Demostrar que si G es un grafo que no es euleriano, pero que contiene un camino deEuler v1v2 · · · vk!1vk, entonces v1 != vk y g(v1) = g(vk) " 1 (mod. 2).

43. Demostrar que si un grafo conexo G se puede poner como union de ciclos (i.e., G =C1 # . . . # Ck, y dos de estos ciclos no comparten aristas y a lo mas tienen un verticeen comun), entonces G es euleriano.

44. Estudiar cuales de los siguiente grafos admite una descomposicion como la del ejercicioanterior, y en caso afirmativo escribirla explıcitamente:

! !

! !

! !

! !

! !! !

45. ¿Cuales de los siguientes grafos son eulerianos?

(a) Kn (b) Kn,m (c) Cn (d) Petersen (e) un arbol

46. Encontrar la solucion del problema del Cartero Chino para el siguiente grafo ponderado:

1

78

70. Representar graficamente todos los grafos eulerianos simples, no isomorfos, con ν = 3, 4, 5, 6.

71. Encontrar la solucion del Problema del Cartero para el siguiente grafo ponderado:

w

w

w

w

ww

u

v

w

z

y

x

1 5

1

22

26

4

3

2

3

72. Idem:

w

w

w

w

w

s

w

w

A

B

C

D

E

G

F

30

50

19

40

6

12 23

11

8

20

10

73. Usando los datos del ejercicio 58, encontrar el recorrido mas barato que permite volar entretodas las ciudades que tengan conexion aerea, al menos una vez, y volver al punto de partida.Calcular el coste mınimo.

74. a) Sea G un grafo ponderado, y sea e = uv una arista de G con g(v) = 1 (ası, e es un puentede manera que G− e tiene una componente conexa con un solo punto: {v}). Conociendola solucion del Problema del Cartero para G− v, ¿como se puede resolver este problemaen G?

b) Encontrar la solucion del Problema del Cartero para el siguiente grafo ponderado:

79


uuu

u u

u

vx

y

z

10012

4

23

75. Encontrar la solucion del Problema del Cartero para el siguiente grafo ponderado:

v

v

v

v

vv

u

v

z

y1

v

wx

a

13

28

5

7

27

7

27

21

2

19

10

v b25

76. Encontrar la solucion del Problema del Cartero para la urbanizacion del siguiente plano. ¿Cuales un posible recorrido, comenzando desde A y cual es su longitud?

x xxxx

x xx

x x xx xx

30

40

1

11009080

70

2

1 20 20

60 1 50

1230

4 303A

77. Encontrar la solucion del Problema del Cartero para la urbanizacion del siguiente plano. ¿Cuales un posible recorrido, comenzando desde A y cual es su longitud?

80

u

u

u

u

u

u

u

u

u

u

u

u

u

u

u u

u

u

u u

u u

957

2 3

2

12542

2

7

1 2 14

2

2

2

2

142

13

155

1

46

314

104

9

74

1151

61

A

1

78. Para el siguiente grafo ponderado (G,w), hallar las soluciones a los siguientes problemas (essuficiente encontrar una en cada caso), explicando en que consisten:

a) Camino optimo desde cada vertice. Calcular el diametro de G (para la metrica dw).

b) Interconexion.

c) Cartero.

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉ ✉

✉

✉

✉ ✉

✉ ✉

957

2 3

2

12542

2

7

1 2 14

2

2

2

2

142

13

155

1

46

314

104

9

74

1151

61

A

1

78. Para el siguiente grafo ponderado (G, w), hallar las soluciones a los siguientes problemas (essuficiente encontrar una en cada caso), explicando en que consisten:

a) Camino optimo desde cada vertice. Calcular el diametro de G (para la metrica dw).

b) Interconexion.

c) Cartero.

①①

①

①

①①

A

B C

D

EF

1

2

4

7

3

13

10

5

4

4

15

79. Encontrar la solucion del Problema del Cartero para la urbanizacion del siguiente plano. ¿Cuales un posible recorrido y cual es su longitud?

81

79. Encontrar la solucion del Problema del Cartero para la urbanizacion del siguiente plano. ¿Cuales un posible recorrido y cual es su longitud?

x xxx x

x xx

x x

13 3 13

3

11 9

8

75

14 4

106

2

1

81


80. a) ¿Es cierto que si G es un grafo euleriano (hamiltoniano) y G∗ es un supergrafo de G conel mismo numero de vertices, entonces G∗ es euleriano (respectivamente hamiltoniano)?

b) Estudiar si los siguientes grafos son hamiltonianos:

Grafo θ0 Grafo de Grotzsch

81. Estudiar si el grafo de Petersen es hamiltoniano (vease el ejercicio 31).

82. Demostrar que si G es un grafo simple y hamiltoniano, entonces G es conexo, α ≥ ν y δ ≥ 2.Estudiar si el resultado recıproco es cierto.

83. Demostrar que, para todo n ≥ 3 existe un numero α(n) < n(n − 1)/2, y existe un subgrafono hamiltoniano G ⊂ Kn, con α(G) = α(n), y de manera que para cualquier otro subgrafoH ⊂ Kn con α(H) > α(n) se verifica que H es hamiltoniano. Probar que α(3) = 2, α(4) = 4y α(5) = 7.

84. Sea S ⊂ V (Cn) un subconjunto no vacıo. Entonces ω(Cn \S) ≤ |S|. Demostrar que existe ungrafo conexo G, con ν ≥ 3, que no es hamiltoniano, y para el que ω(G \ S) ≤ |S|, para todoS ⊂ V .

85. Estudiar si son hamiltonianos los grafos platonicos.

86. Representar todos los subgrafos expansivos hamiltonianos de K4.

87. Encontrar todos los grafos simples hamiltonianos, no isomorfos, con ν = 3, 4.

88. Estudiar si un grafo hamiltoniano puede tener un puente.

89. Demostrar que si un grafo bipartito G es hamiltoniano, entonces ν(G) es par.

90. Estudiar para que valores de n,m ∈ N se verifica que Kn o Kn,m es hamiltoniano.

91. Dar ejemplos de grafos simples, con δ ≥ 2 y conexos, y con al menos un ciclo, que demuestrenque se pueden dar todas la combinaciones de las propiedades ser euleriano y ser hamiltoniano.

92. Demostrar que si G es un subgrafo expansivo no hamiltoniano de Kn (n ≥ 3) entonces existeun supergrafo G∗ 6= Kn no hamiltoniano, maximal por la inclusion, tal que G ⊂ G∗ ⊂ Kn.

93. Demostrar que, para todo ν ≥ 3, existe un grafo conexo no hamiltoniano G, con ν(G) = ν yde manera que la suma de los grados de dos vertices distintos es, al menos, ν − 1.

94. Demostrar que si G se puede poner como la union de dos ciclos que no tienen aristas comunesy que comparten dos vertices, que no son adyacentes en uno de ellos, entonces G no eshamiltoniano. ¿Es cierto el resultado sin la condicion sobre los vertices?

82

95. Estudiar si el Grafo de Herschel es hamiltoniano:

v v v v v

vv v

v vv

96. Demostrar que si δ ≥ ν/2, entonces c(G) es completo. ¿Es cierto el recıproco?

97. Demostrar que si ν ≥ 4 es par, siempre existe un grafo hamiltoniano satisfaciendo que δ = ν/2y que tiene el menor numero de aristas posible (calcular este valor).

98. Demostrar que el grafo que describe los movimientos de un caballo sobre un tablero de ajedrezde dimensiones n×n, no es hamiltoniano si n = 2, 4 o si n es impar. Estudiar los casos n = 6, 8.

99. Estudiar si el siguiente algoritmo genera una solucion del Problema del Viajante en todo grafoponderado completo: Se elige en primer lugar la arista de menor peso. Para elegir una nuevaarista, de entre todas las que no han sido seleccionadas, se considera la de menor peso demanera que no genere un vertice de grado 3, ni un ciclo (salvo que sea la ultima), con las yaelegidas.

100. Sabiendo que cada una de las siguiente representaciones es isomorfa al grafo de Desargues,deducir que es hamiltoniano, y encontrar en cada uno de los 5 grafos un ciclo de Hamilton:

17/04/2007 06:40 PMDesargues Graph -- from Wolfram MathWorld

Página 1 de 1http://mathworld.wolfram.com/DesarguesGraph.html

Search Site

Algebra

Applied Mathematics

Calculus and Analysis

Discrete Mathematics

Foundations of Mathematics

Geometry

History and Terminology

Number Theory

Probability and Statistics

Recreational Mathematics

Topology

Alphabetical Index

Interactive Entries

Random Entry

New in MathWorld

MathWorld Classroom

About MathWorld

Send a Message to the Team

Order book from Amazon

12,647 entriesFri Apr 6 2007

Discrete Mathematics > Graph Theory > Simple Graphs > Bicolorable Graphs

Discrete Mathematics > Graph Theory > Simple Graphs > Bipartite Graphs

Discrete Mathematics > Graph Theory > Simple Graphs > Class 1 Graphs

Discrete Mathematics > Graph Theory > Simple Graphs > Distance-Regular Graphs

Discrete Mathematics > Graph Theory > Simple Graphs > Hamiltonian Graphs

Discrete Mathematics > Graph Theory > Simple Graphs > Integral Graphs

Discrete Mathematics > Graph Theory > Simple Graphs > LCF Notation

Discrete Mathematics > Graph Theory > Simple Graphs > Noneulerian Graphs

Discrete Mathematics > Graph Theory > Simple Graphs > Nonplanar Graphs

Discrete Mathematics > Graph Theory > Simple Graphs > Perfect Graphs

Discrete Mathematics > Graph Theory > Simple Graphs > Regular Graphs

Discrete Mathematics > Graph Theory > Simple Graphs > Square-Free Graphs

Discrete Mathematics > Graph Theory > Simple Graphs > Traceable Graphs

Discrete Mathematics > Graph Theory > Simple Graphs > Triangle-Free Graphs

Discrete Mathematics > Graph Theory > Simple Graphs > Weakly Regular Graphs

Recreational Mathematics > Mathematics in the Arts > Mathematical Book Covers

MathWorld Contributors > Pegg

Desargues Graph

The Desargues graph is a cubic symmetric graph distance-regular graph on 20 vertices and 30 edges, illustrated

above in several embeddings. It can be represented in LCF notation as (Frucht 1976).

This graph is implemented as UnitransitiveGraph in the Mathematica package

DiscreteMath`Combinatorica` (available starting with Version 4.2 and which can be loaded using the

command <<DiscreteMath`) . The Desargues graph is 3-unitransitive (Harary 1994, p. 175), and is identical to

the generalized Petersen graph .

The Desargues graph is isospectral with another nonisomorphic graph (Haemers and Spence 1995, van Dam and

Haemers 2002).

The Desargues is an integral graph and has graph spectrum .

The Desargues graph is the first of four graphs depicted on the cover of Harary (1994).

SEE ALSO: Cubic Symmetric Graph, Distance-Regular Graph, Unitransitive Graph. [Pages Linking Here]

REFERENCES:

Brouwer, A. E. "Desargues Graph." http://www.win.tue.nl/~aeb/drg/graphs/Desargues.html.

Brouwer, A. E. and Haemers, W. H. "The Gewirtz Graph: An Exercise in the Theory of Graph Spectra." European J. Combin. 14, 397-407, 1993.

Frucht, R. "A Canonical Representation of Trivalent Hamiltonian Graphs." J. Graph Th. 1, 45-60, 1976.

Haemers, W. H. and Spence, E. "Graphs Cospectral with Distance-Regular Graphs." Linear Multilin. Alg. 39, 91-107, 1995.

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.

Royle, G. "F020B." http://www.csse.uwa.edu.au/~gordon/foster/F020B.html.

Royle, G. "Cubic Symmetric Graphs (The Foster Census): Distance-Regular Graphs."http://www.cs.uwa.edu.au/~gordon/remote/foster/#drgs.

van Dam, E. R. and Haemers, W. H. "Spectral Characterizations of Some Distance-Regular Graphs." J. Algebraic Combin. 15, 189-202, 2002.

Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, p. 1032, 2002.

LAST MODIFIED: March 2, 2007

CITE THIS AS:

Weisstein, Eric W. "Desargues Graph." From MathWorld--A Wolfram Web Resource.http://mathworld.wolfram.com/DesarguesGraph.html

© 1999-2007 Wolfram Research, Inc. | Terms of Use

Other Wolfram Sites:

Wolfram Research

Integrator

Tones

Functions Site

Wolfram Science

more…

Latest Mathematica Information >>

Download Mathematica Trial >>

Complete MathematicaDocumentation >>

Show your math savvy with aMathWorld T-shirt.

Read the latest Technical SoftwareNews.

101. Encontrar la solucion del Problema del Viajante para el grafo:


Hoja 6

51. Demostrar que si G es hamiltoniano, entonces ! ! ". Estudiar si el resultado recıproco

es cierto.


53. Encontrar todos los grafos simples hamiltonianos, no isomorfos, con " = 3, 4.


55. Estudiar para que valores de n se verifica que Kn es hamiltoniano.

56. Encontrar ejemplos de grafos que demuestren que se pueden dar todas la combinaciones

de las propiedades ser euleriano y ser hamiltoniano.

57. Demostrar que si G se puede poner como la union de dos ciclos que no tienen aristas

comunes y que comparten dos vertices, que no son adyacentes en uno de ellos, entonces

G no es hamiltoniano. ¿Es cierto el resultado sin la condicion sobre los vertices?

58. Estudiar si el siguiente grafo es hamiltoniano:

! ! ! ! !

!! !

! !!

Grafo de Herschel

59. Demostrar que si # ! "/2, entonces c(G) es completo. ¿Es cierto el recıproco?

60. Encontrar c(Cn), n ! 3.

61. Demostrar que una ficha que se mueva como el caballo de ajedrez, no puede recorrer

una sola vez todas las casillas de un tablero de dimensiones 4 " 4, comenzando y

acabando en la misma casilla.

1

62. Dos ciclos de Hamilton de un grafo son equivalentes si cada vertice tiene, en ambos

ciclos, las mismas relaciones de adyacencia. Encontrar la formula que nos da el numero

de los ciclos de Hamilton no equivalentes del grafo completo Kn, n ! 3.

63. Estudiar si el siguiente algoritmo genera una solucion del problema del viajante en

todo grafo ponderado completo: Se elige en primer lugar la arista de menor peso. Para

elegir una nueva arista, de entre todas las que no han sido seleccionadas, se consideran

aquellas que son incidentes con vertices que no pertenecen a 2 de las aristas ya elegidas,

y que, salvo que sea la ultima en elegirse, no generen un ciclo con las anteriores, y de

entre todas se coge la de peso menor.

64. Encontrar la solucion del problema del viajante para el grafo:

! !

! !1

3

25

6

4

65. Calcular el ciclo de Hamilton que se obtiene al aplicar la construccion del ejercicio 63

en el grafo anterior.

66. Encontrar el peso de todos los ciclos de Hamilton del grafo:

2

Calcular el ciclo de Hamilton que se obtiene al aplicar la construccion del ejercicio 99 en elgrafo anterior.

83




Hoja 6

51. Demostrar que si G es hamiltoniano, entonces ! ! ". Estudiar si el resultado recıproco escierto.

52. Sea S " V (Cn) un subconjunto no vacıo. Entonces #(Cn \ S) # |S|.


54. Encontrar todos los grafos simples hamiltonianos, no isomorfos, con " = 3, 4.


56. Estudiar para que valores de n, m $ N se verifica que Kn o Kn,m es hamiltoniano.

57. Encontrar ejemplos de grafos que demuestren que se pueden dar todas la combinaciones delas propiedades ser euleriano y ser hamiltoniano.

58. Demostrar que si G se puede poner como la union de dos ciclos que no tienen aristas comunesy que comparten dos vertices, que no son adyacentes en uno de ellos, entonces G no eshamiltoniano. ¿Es cierto el resultado sin la condicion sobre los vertices?

59. Estudiar si el siguiente grafo es hamiltoniano:

! ! ! ! !

!! !

! !!

Grafo de Herschel

60. Demostrar que si $ ! "/2, entonces c(G) es completo. ¿Es cierto el recıproco?

61. Demostrar que si " es par, siempre existe un grafo hamiltoniano satisfaciendo que $ = "/2 yque tiene el menor numero de aristas posible (calcular este valor).

62. Demostrar que el grafo que describe los movimientos de un caballo sobre un tablero de ajedrezde dimensiones n% n, no es hamiltoniano si n = 3, 4.

63. Estudiar si el siguiente algoritmo genera una solucion del problema del viajante en todografo ponderado completo: Se elige en primer lugar la arista de menor peso. Para elegir unanueva arista, de entre todas las que no han sido seleccionadas, se consideran aquellas que sonincidentes con vertices que no pertenezcan a 2 de las aristas ya elegidas, y que, salvo que seala ultima en elegirse, no generen un ciclo con las anteriores, y de entre todas se coge la depeso menor.


62. Dos ciclos de Hamilton de un grafo son equivalentes si cada vertice tiene, en ambos

ciclos, las mismas relaciones de adyacencia. Encontrar la formula que nos da el numero

de los ciclos de Hamilton no equivalentes del grafo completo Kn, n ! 3.

63. Estudiar si el siguiente algoritmo genera una solucion del problema del viajante en

todo grafo ponderado completo: Se elige en primer lugar la arista de menor peso. Para

elegir una nueva arista, de entre todas las que no han sido seleccionadas, se consideran

aquellas que son incidentes con vertices que no pertenecen a 2 de las aristas ya elegidas,

y que, salvo que sea la ultima en elegirse, no generen un ciclo con las anteriores, y de

entre todas se coge la de peso menor.


! !

! !1

3

25

6

4

65. Calcular el ciclo de Hamilton que se obtiene al aplicar la construccion del ejercicio 63

en el grafo anterior.


2

65. Calcular el ciclo de Hamilton que se obtiene al aplicar la construccion del ejercicio 63 en elgrafo anterior.


! !!

!!

1

23

4

56

7

8 9

10

67. En el grafo G del ejercicio anterior, obtener todas las cotas inferiores de la solucion delproblema del viajante, usando el algoritmo de Kruskal en G menos cada uno de sus vertices.

68. Como en el ejercicio anterior, obtener todas las cotas inferiores para el grafo visto en claseformado por las distancias entre las ciudades: Londres, Parıs, Tokio, Pekın, Mexico DF yNY.

69. Obtener buenas estimaciones (superior e inferior) de la solucion del problema del viajante delas rutas marıtimas del ejercicio 38, dadas por la matriz de adyacencia:

!

""""""""#

A B C D E FA 0 20 12 22 17 41B 20 0 11 21 19 25C 12 11 0 28 33 9D 22 21 28 0 27 16E 17 19 33 27 0 43F 41 25 9 16 43 0

$

%%%%%%%%&

103. En el grafo G del ejercicio anterior, obtener todas las cotas inferiores de la solucion delProblema del Viajante, usando los resultados del Capıtulo 6.

104. Como en el ejercicio anterior, obtener todas las cotas inferiores para el grafo del Ejemplo 4.2.2.

105. Implementar en un ordenador el calculo de todos los ciclos de Hamilton del ejercicio 104 yhallar la solucion del Problema del Viajante.

106. Obtener buenas estimaciones (superior e inferior) de la solucion del Problema del Viajante delas rutas marıtimas del ejercicio 59.

107. Si un grafo conexo ponderado no es completo, anadimos las aristas que faltan (hasta comple-tarlo) con peso igual al peso de la geodesica entre los vertices que no son adyacentes. Con esteprocedimiento, calcular la solucion del Problema del Viajante para los grafos del ejercicio 57.

108. La matriz siguiente muestra las distancias entre 5 ciudades:

A B C D E

A 0 10 1 2 50

B 10 0 20 5 3

C 1 20 0 30 4

D 2 5 30 0 40

E 50 3 4 40 0

Encontrar las cotas inferiores para la solucion del Problema del Viajante que se obtienendesde cada ciudad.

Calcular la cota superior que da el ciclo ABCDEA.

Mejorar esta estimacion mediante el metodo de cambio de aristas, hasta conseguir unadistancia menor que 30. ¿Es esta cota optima?

109. La siguiente matriz muestra las distancias entre 5 ciudades:

A B C D E

A 0 2 20 10 1

B 2 0 3 25 15

C 20 3 0 4 30

D 10 25 4 0 100

E 1 15 30 100 0

a) Encontrar todas las cotas inferiores posibles del Problema del Viajante.

b) Calcular la cota superior que da el ciclo ABCDEA.

84

c) Mejorar (b) mediante el metodo de cambio de aristas, hasta conseguir un peso menorque 40.

d) Usando (a) y (c), calcular, en porcentaje, el error que se obtiene.

110. Encontrar la solucion del Problema del Viajante para el siguiente grafo:

A B C D E

A 0 2 19 1 9

B 2 0 14 10 4

C 19 14 0 7 3

D 1 10 7 0 6

E 9 4 3 6 0

111. Calcular todas las acotaciones inferiores que se obtienen desde cada uno de los vertices, de lasolucion del Problema del Viajante, para el grafo cuya matriz de adyacencia es:

A B C D E FA 0 19 12 22 17 21B 19 0 13 21 19 25C 12 13 0 28 33 9D 22 21 28 0 21 16E 17 19 33 21 0 23F 21 25 9 16 23 0

Obtener buenas estimaciones superiores de la solucion del Problema del Viajante calculandoel porcentaje del error cometido.

112. Calcular todas las acotaciones inferiores posibles de la solucion del Problema del Viajante,del grafo cuya matriz de adyacencia es:

A B C D E FA 0 1 6 17 21 50B 1 0 2 8 19 7C 6 2 0 3 16 18D 17 8 3 0 4 15E 21 19 16 4 0 5F 50 7 18 15 5 0

Comenzando por el ciclo ABCDEFA obtener buenas estimaciones superiores de la soluciondel Problema del Viajantehasta reducir el error a un numero menor que el 19 %.

113. a) Sea G, con V (G) = {a, b, c, d, e}, el grafo ponderado dado por la matriz:

b c d e

a 1 1 1 1

b − 2 2 2

c − − 5 3

d − − − 4

(i) Encontrar todas las cotas inferiores del PV obtenidas desde cada vertice.

85


(ii) Empezando por el ciclo abcdea, encontrar una cota superior k, mediante el metododel cambio de aristas, de manera que

k − 1 ≤ PV ≤ k.

b) Encontrar la solucion del PV del grafo ponderado G, con V (G) = {a, b, c, d, e, f}, dadopor la matriz:

b c d e f

a 1 7 7 7 6

b − 2 2 2 2

c − − 3 7 7

d − − − 4 7

e − − − − 5

114. Demostrar los siguientes enunciados:

a) Si G es regular, simple, conexo, ν ≥ 3 y α ≥ ν2/4, entonces G es hamiltoniano.

b) Sea G un grafo simple con ν ≥ 3.:

(i) Si ν = 3: G es hamiltoniano si, y solo si, G ≈ C3.

(ii) Si ν ≥ 4: G es hamiltoniano y no contiene copia de Ck, para todo k ∈ {3, . . . , ν− 1}si, y solo si, G ≈ Cν .

c) Si G es hamiltoniano, entonces contiene un emparejamiento maximal de cardinal [ν/2].

d) Para todo k ≥ 3 existe un grafo simple, conexo, no hamiltoniano, δ(G) ≥ 2, ν = 2k yque contiene un emparejamiento perfecto.

115. Calcular la longitud (con respecto a la distancia euclıdea del plano) del menor ciclo que recorretodos los puntos del conjunto

{(j, k) ∈ N× N : j, k ∈ {1, . . . , N}

},

para cada valor N ∈ {2, 3, . . . }.

116. a) Encontrar un emparejamiento perfecto (o maximal, en su caso) en Kn, siendo n =2, 3, 4, 5, 6.

b) Estudiar para que valores de m,n el grafo bipartito completo Km,n admite un empare-jamiento perfecto. En este caso, calcular el numero total de dichos emparejamientos. Encaso negativo, calcular el numero de aristas de un emparejamiento maximal de Km,n.

117. Estudiar la existencia de un emparejamiento perfecto y encontrar un emparejamiento maximaldel grafo:

vvvv

v

vv

v

vv86

118. Lo mismo para el grafo:

119. La siguiente lista muestra la compatibilidad entre 10 modelos distintos de circuitos:

[1,2], [1,5], [2,3], [2,4], [2,5], [3,5], [4,5], [4,6], [4,9],

[5,6], [5,7], [6,7], [6,8], [6,9], [6,10], [7,9], [8,9], [9,10].

¿Cual es el numero maximo de pares de circuitos compatibles que se pueden obtener?

120. La siguiente tabla muestra las preferencias de los trabajadores de una empresa {1, 2, 3, 4, 5},en relacion a los posibles puestos de trabajo {a, b, c, d, e}:

∣∣∣∣∣∣∣∣∣∣∣∣

a b c d e1 ∗ ∗2 ∗ ∗3 ∗ ∗4 ∗ ∗ ∗5 ∗

∣∣∣∣∣∣∣∣∣∣∣∣

Usando el Metodo Hungaro, estudiar si existe una asignacion de personal que respete laspreferencias de cada trabajador

121. En una academia de baile hay que formar 6 parejas entre los 6 chicos ({1,2,3,4,5,6}) y 6 chicas({a, b, c, d, e, f}) de la clase. La siguiente tabla muestra la relacion de amistad entre ellos:

∣∣∣∣∣∣∣∣∣∣∣∣∣∣

a b c d e f1 ∗ ∗2 ∗ ∗3 ∗4 ∗ ∗5 ∗ ∗6 ∗ ∗

∣∣∣∣∣∣∣∣∣∣∣∣∣∣

¿Se puede conseguir que las parejas esten formadas por amigos? (Comenzar por {a1, e2, c3}).

122. Demostrar que si X = {x1, · · · , x7} e Y = {y1, · · · , y7} son las particiones del siguinte grafo

87


bipartito: ∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣

x1 x2 x3 x4 x5 x6 x7y1 ∗ ∗ ∗ ∗ ∗ ∗ ∗y2 ∗ ∗y3 ∗ ∗ ∗ ∗ ∗y4 ∗ ∗y5 ∗ ∗ ∗ ∗ ∗y6 ∗ ∗y7 ∗ ∗ ∗ ∗ ∗

∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣

entonces no existe un emparejamiento perfecto. Encontrar al menos un emparejamiento ma-ximal M . ¿Existe un camino M -aumentado?

123. Comenzando por el emparejamiento M = {a1, c3}, y usando el Metodo Hungaro, estudiar laexistencia de un emparejamiento perfecto del siguiente grafo:

v v v v v

v v v v v

a b c d e

1 2 3 4 5

124. Sea B3 el conjunto de todos los grafos bipartitos G = (X,Y ), con |X| = |Y | = 3 y tal queδ(G) ≥ 1. Encontrar para que valores de k ∈ N, existe G ∈ B3, con α(G) = k y G no poseeun emparejamiento perfecto.

125. Fijado n ∈ N, calcular el maximo y el mınimo del siguiente conjunto:

{|M | : M es un emparejamiento maximal de algun grafo simple y conexo de n vertices

}.

126. Demostrar que si P es el grafo de Petersen, entonces χ(P ) = 3.

127. Sea Rn una rueda. Calcular χ(Rn), n ≥ 3.t ttt t

tt tt t

t ttt

t

R3 R4 R5

128. Demostrar que si χ(G) = k, existe un subgrafo H ⊂ G que es k-crıtico. Para el caso G = P3,representar todos sus subgrafos con χ = 2 y hallar los 2-crıticos.

129. Encontrar una representacion de K7 que tenga 9 cruces de aristas.

130. a) Calcular cr(K2,n), para todo n ≥ 1.

88

b) Calcular cr(K3,4).

c) Demostrar que 3 ≤ cr(K4,4) ≤ 4.

131. Demostrar que existe un grafo plano G tal que δ(G) = 4.

132. Encontrar un ejemplo de un mapa para cada uno de los subgrafos conexos expansivos de K4.

133. Representar el grafo asociado del siguiente mapa y calcular su numero cromatico:

134. a) Demostrar que existe un grafo plano G que no contiene a K4 y χ(G) = 4.

b) Representar el siguiente mapa como un grafo plano G y calcular χ(G):

1

2

3

4

5

6

7

8

9

10

c) Demostrar que si H es una subdivision de G, entonces 2 ≤ χ(H) ≤ χ(G) + 1. Probarcon sendos ejemplos que ambas desigualdades son optimas.

d) Encontrar cr(G) y χ(G) para los siguientes grafos:

v v vv v v

v v vv v v

G1

v vv vvv vv vv

v vv vvG2

89


135. Representar el grafo asociado de los siguientes mapas. Calcular su numero cromatico. Encon-trar el cardinal del mayor submapa que sea un arbol (dar un ejemplo concreto).

90

Capıtulo 10

Apendice

10.1. Notaciones

Algoritmos, Problemas y Resultados

• Formula de Cayley

• Metodo del cambio de aristas

• Problema del Almacenamiento

• Problema de la Asignacion de Perso-nal (Metodo Hungaro)

• Problema del Camino mas Corto (Al-goritmo de Dijkstra)

• Problema del Cartero o del Explora-dor

• Problema de la Interconexion (Algo-ritmo de Kruskal)

• Problema del Viajante

• Teorema de Berge

• Teorema de la Caracterıstica de Euler

• Teorema de los Cuatro Colores (Ap-pel y Haken)

• Teorema de Euler

• Teorema de Hall

• Teorema de Kuratowski

• Teorema del Matrimonio

Aristas (E)

• contraıda (G · e)• duplicada

• emparejamiento (M)

◦ maximal

◦ perfecto

• grafo menos arista (G \ e)• lazo (loop)

• multiples

• numero de aristas (α)

• puente (bridge, cut edge)

Camino (walk)

• cerrado

• ciclo

◦ equivalente

◦ de Hamilton

◦ optimal

• elemental (path)

• de Euler

• de Hamilton

• M -alternado

• M -aumentado

• minimal

• simple (trail)

• tour

Distancia (d)

• diametro (D)

• geodesica

91

CAPITULO 10. APENDICE

• radio (r)

Grafo (G)

• arbol (T )

◦ alcano

◦ expansivo (spanning tree)

◦ genealogico

◦ numero de arboles expansivos(τ(G))

◦ optimal

• bipartito (completo, Kn,m)

• cara

◦ exterior

• ciclo (Cn)

• clausura (c(G))

• completo (Kn)

• conexo

◦ componente conexa

◦ numero de componentes conexas(ω(G))

• crıtico, k-crıtico

• cubo (Qn)

• dirigido (digrafo)

• elemental (Pn)

• espectro

• euleriano

• grupo de automorfismos (Γ(G))

• hamiltoniano

• Konigsberg

• mapa

• matriz de adyacencia (A(G))

• matriz de incidencia (I(G))

• nulo (Nn)

• numero de corte (cr(G))

• numero cromatico (χ(G))

• Petersen

• planar

• plano

• platonico

• polinomio caracterıstico (PG)

• ponderado (con pesos)

• regular

• simple

• subdivision

• subgrafo

• supergrafo

• triangulo (K3)

Vertices (V )

• conjunto de vecinos (N(S))

• constante de Moore (N(∆, D))

• de corte (cut vertex)

• grado de un vertice (g(v))

◦ grado maximo (∆)

◦ grado mınimo (δ)

◦ sucesion de grados

• grafo menos vertice (G \ v)

• numero de vertices (ν)

• saturado por M

92

10.2. PROBLEMAS ABIERTOS

10.2. Problemas abiertos

1. ¿Cuantos cruces se han de dar como mınimo para poder dibujar Kn, con n ≥ 13?

Se sabe que los numeros de corte de los grafos completos Kn, para n = 1, · · · , 12 son, respec-tivamente, 0, 0, 0, 0, 1, 3, 9, 18, 36, 60, 100, 150.

http://mathworld.wolfram.com/GraphCrossingNumber.html

2. ¿Cual es el mayor numero de vertices que puede tener un grafo plano dediametro 3 y con grado maximo igual a 3?

Este problema, propuesto por P. Erdos, tiene relevancia en la construccion de redes de orde-nadores trabajando en paralelo. La configuracion maxima que se conoce actualmente contiene12 vertices (y es optima si exigimos que el grafo sea 3-regular):

vvvvvv vvvv

vv

Se sabe que, como mucho, puede tener 15 vertices.

http://www.unc.edu/~rpratt/degdiam.html

http://faculty.uccb.ns.ca/jpreen/ef/table.htm

3. Conjetura de la Reconstruccion (S. M. Ulam)

Supongamos que G y H son dos grafos que tienen el mismo numero de vertices,

V (G) = {u1, . . . , un} y V (H) = {v1, . . . , vn}, n ≥ 3,

y de manera que para cada j = 1, . . . , n, se verifica que

G− uj ≈ H − vj .

Estudiar si, necesariamente, G ≈ H. El resultado es cierto, por ejemplo, si n ≤ 11 o si G y Hson arboles.

http://garden.irmacs.sfu.ca/?q=op/reconstruction_conjecture

http://en.wikipedia.org/wiki/Reconstruction_conjecture

4. Arboles Expansivos

Se dice que un vertice v de un arbol T es un vertice de soporte si es adyacente a una hoja deT (es decir, vecino de un vertice de grado 1).

Si G es un grafo simple y conexo, con δ(G) ≥ 2, ¿existe un arbol expansivo T de G de maneraque, para todo v que sea un vertice de soporte de T , si gG(v) ≥ 3, entonces gT (v) ≥ 3?

93

http://mathworld.wolfram.com/GraphCrossingNumber.html

http://www.unc.edu/~rpratt/degdiam.html

http://faculty.uccb.ns.ca/jpreen/ef/table.htm

http://garden.irmacs.sfu.ca/?q=op/reconstruction_conjecture

http://en.wikipedia.org/wiki/Reconstruction_conjecture

CAPITULO 10. APENDICE

Observamos, en el ejemplo siguiente, que T1 es solucion del problema, pues v es el unico verticede soporte de T1 y gG(v) = gT (v) = 3. Sin embargo vemos que no todo arbol expansivo essolucion, ya que v es tambien un vertice de soporte de T2, pero gT2(v) = 2.

Se sabe que el resultado es correcto si ν(G) ≤ 8.

u u

u u

u u

u u

u u

u uG T1 T2

v

http://garden.irmacs.sfu.ca/?q=op/spanning_trees

5. El Problema del Viajante

Un comerciante ha de visitar una sola vez todas las ciudades donde residen sus clientes, yquiere hacerlo de manera que el recorrido sea el mas corto posible ¿Como se puede determinaresta ruta de manera efectiva? Si, por ejemplo, enumeramos todas las posibilidades de ordenarlas distintas ciudades (supongamos que hay n), y elegimos la que da el valor menor, habremosde considerar n! casos. Para hacernos una idea de la magnitud de este numero, si pudieramostrabajar con el ordenador mas rapido que existe (alrededor de 40 billones de operaciones porsegundo), y hubiera 25 ciudades, tardarıamos mas de 12.000 anos. Si aumentamos ligeramenteeste valor hasta las 30 ciudades, entonces el tiempo requerido llegarıa hasta 14 veces la edaddel Universo...

http://www.tsp.gatech.edu/

http://www.mat.ub.es/~soria/Viajante/Problema-Viajante.html

6. Un listado con mas de 150 problemas se puede encontrar en la pagina Open Problems Garden:Graph Theory:

http://garden.irmacs.sfu.ca/?q=category/graph_theory&sort=desc&order=Rec.%C2%

B2

94

http://garden.irmacs.sfu.ca/?q=op/spanning_trees

http://www.tsp.gatech.edu/

http://www.mat.ub.es/~soria/Viajante/Problema-Viajante.html

http://garden.irmacs.sfu.ca/?q=category/graph_theory&sort=desc&order=Rec.%C2%B2




Bibliografıa

[1] C. Alsina, Mapas del Metro y Redes Neuronales, Barcelona: RBA, 2010.

[2] J.M. Basart i Munoz, Grafs: Fonaments i Algorismes, Bellaterra: Universitat Autonoma deBarcelona, 1994.

[3] C. Berge, Theorie des Graphes et ses Applications, 2a ed., Paris: Dunod, 1967.

[4] N.L. Bigg, E.K. Lloyd y R.J. Wilson, Graph Theory: 1736-1936, Oxford: ClarendonPress, 1986.

[5] J.A. Bondy y U.S.R. Murty, Graph Theory, New York: Springer, 2008.

[6] R. Diestel, Graph Theory, 3a ed., Berlın: Springer, 2005.

[7] J.R. Evans y E. Minieka, Optimization Algorithms for Networks and Graphs, 2a ed., NewYork: Marcel Dekker, 1992.

[8] A. Gibbons, Algorithmic Graph Theory, Cambridge: Cambridge Univ. Press, 1985.

[9] F. Harary, Graph Theory, Reading: Addison-Wesley, 1969.

[10] O. Ore, Grafos y sus Aplicaciones, Madrid: DLS-EULER, 1995.

[11] S. Skiena, Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mat-hematica, Redwood City: Addisson Wesley, 1990.

[12] R.J. Wilson, Introduccion a la Teorıa de Grafos, Madrid: Alianza Universidad 367, 1983.

95

http://cataleg.ub.edu/record=b1977933~S1*spi













apuntes grafos

Documents