Instituto Nacional Superior del Profesorado Técnico
Profesorado de matemática y matemática aplicada
Cálculo Numérico
Trabajo Práctico G1
Algunas propiedades de los grafos y sus aplicaciones
A. Prueba cada una de las siguientes propiedades:
1. a. En un grafo no orientado, la suma de los grados de los vértices coincide con el
doble del cardinal del conjunto de aristas. Probar por inducción completa ¿sobre qué
conjunto realizas inducción?
b. ¿es posible realizar esta demostración sin aplicar inducción completa?
2. Sea G = (V, A, ) un grafo. Probar que la relación “es conectable con”, definida en
el conjunto de vértices es una relación de equivalencia.
3. Las siguientes proposiciones son equivalentes:
i) G = (V, A, ) un grafo no conexo
ii) Existe una partición en por lo menos dos componentes V1 y V2 de V
tales que ninguna arista tiene un extremo en V1 y otro en V2.
4. Si G = {V,A, } es un grafo conexo con #A = 17 y g(v) 3 para todo v V, ¿cuál
es el valor máximo que podría tomar #V?. Justifique.
5. Sea G = {V,A, } un grafo no dirigido conexo sin lazo 3-regular (esto es, cada
vértice de G tiene grado 3). Si #A = 2 #V – 6 ¿Cuánto valen #V y #A?
6. Si G es un grafo no dirigido con n vértices y a aristas, sean míng ( ) y
V
máxg ( ). Demuestre que
2a
.
V n
7. Demuestra que en todo grafo simple de n vértices siempre existe al menos un par de
vértices con igual grado (Ayuda: considera el rango de valores que pueden tomar los
grados de los vértices).
B. Aplica algunas ideas de grafo para resolver los siguientes problemas y ejercicios:
1. Un esquema de los tramos de autopista que conectan a seis ciudades: A, B, C, D, E,
F, revela la existencia de los siguientes tramos: dos entre A y D, dos entre A y F, uno
entre A y B, uno entre B y F, uno entre C y E y uno entre B y D.
a. Describe la situación mediante un grafo.
b. ¿Quedan todas las ciudades conectadas (directa o indirectamente) mediante
los tramos de autopista construidos?
c. ¿Cuántos tramos sería necesario construir para que esto fuera posible?
¿Dónde?
d. Si las estaciones de peaje se encuentran a la entrada de cada ciudad, ¿puede
un habitante de A ir a cada una de las otras ciudades pagando a lo sumo dos
peajes?
e. ¿Cuál es el número máximo de tramos de autopista que pueden cortarse
manteniendo todas las ciudades intercomunicadas? (Utilice para esta
respuesta la situación obtenida a partir del punto c.).
1
f. Explica cada una de las respuestas utilizando conceptos de teoría de grafos.
2. Construye un grafo que represente el funcionamiento de una máquina muy simple de
caramelos, con las siguientes reglas:
o cada caramelo cuesta $ 0.15
o la máquina acepta sólo monedas de $ 0.10 y de $ 0.05
o la máquina NO da vuelto.
Para construir el grafo, deben considerarse distintos “estados de dinero ingresado”, y como
se va pasando de uno a otro. Por ejemplo, si en un momento tenemos ingresados 5 centavos,
y agregamos 5 centavos más, pasamos a otro estado, que es el mismo que si hubiésemos
ingresado 10 centavos al principio.
3. En los casos en que sea posible, trace un grafo que verifique las condiciones pedidas.
En caso de no ser posible, justifique:
a. que tenga exactamente 6 vértices, cada uno de grado 3;
b. que tenga exactamente 5 vértices, cada uno de grado 3;
c. que tenga exactamente 4 vértices, cada uno de grado 1;
d. que tenga exactamente 6 vértices y 4 aristas;
e. que tenga exactamente 4 vértices de grados 1, 2, 3 y 4 y 4 aristas;
f. que tenga exactamente 4 vértices de grados 1, 2, 3 y 4;
g. que tenga exactamente 6 vértices de grados 1, 2, 3, 4, 5 y 5 y sea simple (esto es:
sin lazos ni aristas paralelas);
h. que tenga exactamente 5 vértices de grados 2, 3, 3, 4 y 4 y sea simple.
4. a. ¿Cuál es la cantidad total de vértices de un grafo que tiene 2 vértices de grado 4, 1
de grado 3, 5 de grado 2 y el resto colgantes (de grado 1) sabiendo que en total hay 12
aristas?
b. Trázalo.
5. Traza el siguiente grafo:
V = {w1,w2,w3,w4} A = {a1,a2,a3,a4,a5,a6}
φ(a1)=(w1 ; w2) φ (a2)=(w2; w3) φ(a3)=(w4 ; w4)
φ(a4)=(w2 ; w1) φ(a5)=(w4; w1) φ(a6)= (w2 ; w3)
6. En una oficina donde reina la discordia trabajan 17 personas. ¿Es posible que cada
persona se lleve bien exactamente con 5 de las restantes?
7. Elige la respuesta correcta. Sea G un grafo con un ciclo.
a. Todo subgrafo de G es conexo por tener un ciclo.
b. Todo subgrafo cuyo conjunto de vértices coinciden con los del ciclo es
necesariamente conexo.
c. Todo subgrafo cuyo conjunto de arcos coincide con el del ciclo es conexo.
d. El subgrafo determinado por un conjunto de vértices del ciclo no es
necesariamente conexo.
8. Un grafo simple de n vértices y cada vértice es adyacente a todos los demás se denomina
grafo completo de n vértices y se denomina Kn.
a. Traza K1, K2, K3, K4 y K5.
b. Halla una fórmula que permita calcular la cantidad de aristas de K n en
función de la cantidad de vértices de vértices n.
9. Un grafo se llama bipartido o dicotiledóneo si existe una partición del conjunto V de sus
vértices en dos subconjuntos V1 y V2, tal que toda arista es incidente con un vértice de V1
y otro de V2.
2
Instituto Nacional Superior del Profesorado Técnico
Profesorado de matemática y matemática aplicada
Cálculo Numérico
Se dice que un grafo bipartido es bipartido completo de n+m vértices y se lo indica Kn,m
si es simple y #(V1)=n, #(V2)=m y además todo vértice de V1 es adyacente a todo vértice
de V2.
a. Traza K2,3, K2,4, K3,3, K3,4 y K2,5.
b. Halla una fórmula que permita calcular la cantidad de aristas de K n,m en
función de las cantidades de vértices de vértices n y m.
10. Determina cuales de los siguientes grafos son bipartidos
11. Dado el siguiente grafo:
Halla:
a. Grado de cada vértice
b. 3 maneras de llegar de “a” hacia “f”
c. Ciclos de longitud 3, 4, 5 y 7
12. En una fiesta hay 8 personas que en un determinado momento llenan sus copas
de sidra y brindan entre ellos, todos con todos.
a. ¿Cuántos choques de copas hay en total?
b. ¿Qué significa esa pregunta en teoría de grafos?
