guia grafos

Universidad de Talca.
Instituto de Matem´tica y F´
a
ısica

M´dulo: Elementos 1
o
Carrera: Arquitectura

Guia N◦ 1

1. Con respecto al grafo de la figura:
(a) Etiquetar los v´rtices ydeterminar el conjunto de aristas.
e
(b) Hallar el grado de cada v´rtice.
e
(c) Determinar la cantidad de aristas del grafo.
(d) Encontrar el largo maximal que puede tener un camino.
(e) Determinar4 caminos de largo 7
(f) Encontrar todas las aristas que se pueden eliminar del grafo sin que se pierda la conexidad.
(g) Encontrar todas las aristas que al eliminarse del grafo, hagan que el grafodeje de ser
conexo.
(h) Determinar los ciclos del grafo.
•
•

•

•

•

•
•

•

•

•

•

•

2. Dise˜ ar si es posible (en caso de no ser posible, justifique su respuesta):
n(a) Una planta de 6 habitaciones, donde cada habitaci´n tenga 3 puertas que la conectan
o
con tres habitaciones distintas.
(b) Una planta de 7 habitaciones, donde cada habitaci´n tenga 3 puertas quela conectan
o
con tres habitaciones distintas.
3. Determinar el conjunto de v´rtices y aristas de los grafos K3,3 y K5 .
e
4. Ocho ciudades a1 , a2 , a3 , a4 , a5 , a6 , a7 y a8 desean unirsepor carreteras de modo que las
mismas no se crucen. Se pretenden construir los siguientes tramos a1 a2 , a1 a6 , a1 a7 , a1 a8 ,
a2 a5 , a3 a6 , a3 a7 , a3 a8 , a4 a6 , a4 a7 , a4 a8 y a5 a6 .Averiguar si ello s posible mediante el grafo
correspondiente.
5. Dado un grafo simple G, el complemento de G, denotado por G, es el grafo simple cuyo
conjunto de v´rtices es el mismo que el de G y suconjunto de aristas consiste de todas
e

las aristas que no est´n presentes en G. Determinar el complemento del grafo de la figura.
a
Adem´s, determinar una relaci´n entre el grado de un v´rtice enG y G.
a
o
e
•

•

•

•
•

•

6. Si G es un grafo simple con n v´rtices.
e
(a) ¿Cu´l es el n´ mero m´ximo de aristas que puede tener G?
a
u
a
(b) ¿Cu´l es el n´ mero m´
a
u...