Planaridad y coloración PDF

Preview

Summary

Download Planaridad y coloración PDF

Description

DepartamentodeMatemáticaAplicada.FacultaddeInformática.UPM Grupo3S1M

MatemáticaDiscretaII Curso11‐12

PLANARIDADYCOLORACIÓN 1. DemuestraquelossiguientesgrafossonplanaresycompruebalafórmuladeEuler.

2. ¿ParaquévaloresdenelgrafocompletoKnesplanar? 3. ¿ParaquévaloresderyselgrafobipartidocompletoKr,sesplanar? 4. SeaG=K5yeunaaristadeG.DemuestraqueG–eesplanar. 5. Estudia si son planares los siguientes grafos. En caso afirmativo, da una representación plana y comprueba la fórmula de Euler. En caso negativo, aplica el teorema de Kuratowski para demostrar quenoloson.

6. SeaGungrafoplano,conexo,4‐regularycon16aristas.¿Cuántascarastiene? 7. Hallaelnúmerocromáticodelossiguientesgrafos:

1

8. Hallaunconjuntoindependientemaximaldetamaño3,otro detamaño4 y otro de tamaño 5 enel grafo(A)delafigura.Hallaconjuntosindependientesmaximales dedistintotamañoencada uno de losrestantesgrafos.¿Cuáleselnúmerodeindependenciadecadagrafo? 

1

4



3

2



1

6

5

3

2

7

6

7



9

8

(A)



5

4

9

11

10

8

9. Enunaempresaquímicasefabrican8productos:A, B, C,D, E,F,G yH.Algunosdeesosproductos reaccionanviolentamentealmezclarseconotrosporloqueesobligatorioalmacenarlosendiferentes contenedores.Silatablaadjuntainformade lassustanciascuyamezclaespotencialmentepeligrosa, ¿cuáleselmínimonúmerodecontenedoresquesenecesitan?   B C D E F G

A      

B      

C      

D      

E      

F      

G      

H      

 10. El “Teorema de los cuatro colores” dice que que todo grafo planar se puede colorear con cuatro colores.SiGesungrafoconnúmerocromático3,¿esciertoqueelgrafodebeserplanar? 11. Colorearlossiguientesmapasutilizandoelmenornúmeroposibledecolores. 

   

 2...