Grafos -tp2

Matemática II - Curso on line 2014.
Unidad 2 – Grafos y Simetría
Antes de resolver el TP vamos a hacer una aclaración que, en más de un caso, puede llevar a
confusión. En la Teoría de Grafos hablamosde vértices, aristas y la relación que vincula a ellos,
pero nunca hacemos notar la diferencia entre lo que es un Grafo y lo que es un Multigrafo.
Llamaremos Grafo al que es Grafo Simple; ellosignifica que no tiene aristas múltiples ni lazos.
Al que, por el contrario, posee esa cualidad lo llamaremos multigrafo. La diferencia radica en que
hay algunas propiedades que son válidas para losprimeros, pero no para los segundos.
Por ejemplo: En un grafo, para que haya una cara son necesarias al menos tres aristas porque
con dos se trataría de un multígrafo.
Si, en algún caso, la respuesta delalumno llega a ser refiriéndose a un grafo o a un multígrafo
sin hacer distinción, lo calificaremos como correcto, pero son conceptos a considerar y hacer
notar la diferencia.

Grafo Simple – (grafo)Multigrafo
B

B

Cara

C

C

Cara

A

A
Cara

D

E

E

D

Resolución
1) Construir, en cada caso, un grafo con las características que se indican.
a) Grafo conexo de 5 vértices que sea plano, que notenga aristas múltiples y posea
dos vértices de grado 3.
B

Resolución:

C
A

Grado(B)=Grado(D)=3

E

D

b) Grafo poligonal de seis vértices que admita un recorrido euleriano restringido.
Resolución: Paraello es necesario que el grafo posea exactamente dos vértices de
grado impar.

Grado(D)=Grado(E)=3

c) Grafo poligonal de cinco caras (incluida
la cara del infinito), donde se precisen
tres coloresdiferentes para poder
diferenciar áreas pintadas.
Resolución
Lo que figura pintado de color amarillo
es la cara del infinito.

d) Un grafo plano simple que sea regular pero no completamente regular.Resolución
A

B
Todos los vértices tienen igual grado, pero las
caras no están rodeadas por la misma cantidad
de aristas.

C
G
H
F

D

E

e) Un grafo plano simple de seis caras que sea completamente...