Relación 2

Matemática Discreta
Grado en Matemáticas
Relación de Problemas (2)
2.1. Sea el grafo G, tal que V (G) = {a, b, c, d, e, f } y A(G) = {ab, ae, bd, cd, de}. Se pide: a) Repre-
sentarlo gráficamente; b) obtener su matriz de adyacencia; c) obtener su matriz de incidencia;
d) obtener el subgrafo de G inducido por < b, c, d, f > y representarlo gráficamente; e) idem
con el subgrafo G − d.
2.2. Obtener la matriz de incidencia y una representación gráfica del grafo cuya matriz de adyacencia
es la siguiente:  
0 1 1 0 1 1
 1 0 1 1 1 0 
 
 1 1 0 1 0 0 
 
 0 1 1 0 1 1 
 
 1 1 0 1 0 0 
1 0 0 1 0 0
2.3. Cinco amigos salen de vacaciones al mismo tiempo y a diferentes lugares. Deciden que al llegar
a su destino, cada uno de ellos enviará una postal a tres de los restantes. ¿Es posible que cada
amigo reciba postales de precisamente los tres a los que él les envió las suyas?. Razonar la
respuesta, en caso de ser negativa, o representar mediante un grafo dicha situación, en caso
afirmativo. Contestar a la misma cuestión si ahora son seis los amigos que marchan de viaje.
2.4. Probar que en todo grafo (finito), con dos o más vértices, hay siempre dos vértices con el mismo
grado. ¿Ocurre lo mismo si el grafo es infinito?
2.5. Dado un grafo G de orden mayor o igual que 6, probar que G o G ha de contener un triángulo.
2.6. Indicar razonadamente cuál es el menor número de vértices n de un grafo autocomplementario.
Dar ejemplos de grafos autocomplementarios de orden n y n + 1 para ese valor de n antes
citado. En general, dado un grafo autocomplementario de orden n, demostrar que o bien n o
bien n − 1 ha de ser un múltiplo de 4.
2.7. Un conjunto ordenado (en orden decreciente) de números enteros no negativos {a1 , a2 , . . . , an } se
denomina conjunto gráfico si existe un grafo tal que al ordenar en orden decreciente las valencias
de todos sus vértices se obtenga dicho conjunto. Razonar si los siguientes tres conjuntos de
números son o no gráficos: C1 : {1, 1, 1, 1, 1, 1}, C2 : {5, 4, 3, 2, 2, 1}, C3 : {5, 5, 4, 4, 0}.
2.8. ¿Son isomorfos los siguientes grafos?
(a)
(b)
2.9. Dado un grafo G, denotamos δ(G) = min {δ(v), v ∈ G}. Probar que todo grafo G contiene un
arco de longitud δ(G), y un ciclo de longitud al menos δ(G) + 1 (suponiendo δ(G) ≥ 2).
2.10. Demostrar que en todo grafo conexo G se cumple la desigualdad g(G) ≤ 2d(G) + 1, donde g(G)
y d(G) denotan el contorno y el diámetro de G, respectivamente.
2.11. Sea G el grafo tal que V (G) = {b, c, d, e} y A(G) = {bd, be, cd, ce}. Consideremos un vértice
nuevo a. Determinar el contorno, la circunferencia y el diámetro del grafo G + a.
2.12. Sea G un grafo. Se denomina potencia enésima de G a otro grafo, denotado por Gn , tal que
(a) V (Gn ) = V (G).
(b) ∀ u, v ∈ V (G), la arista uv ∈ A(Gn ) si y sólo si d(u, v) ≤ n (en G).
Dar un ejemplo de un grafo de orden mayor o igual que 5 y tamaño 8 y representar su cuadrado
y su cubo.
2.13. Dado un grafo G conexo, un vértice de G se denomina central si tiene excentricidad mı́nima.
Dar ejemplos de los siguientes árboles:
(a) Con un punto central.
(b) Con dos puntos centrales.
2.14. Se denomina centro de un grafo al conjunto de sus vértices centrales. Probar que el centro de
un árbol está formado por un único vértice o por dos vértices adyacentes.
2.15. Probar que cada árbol es un grafo bipartito. ¿Qué árboles son grafos bipartitos completos?
2.16. Probar que si G es un grafo conexo, r(G) ≤ d(G) ≤ 2r(G), donde r(G) y d(G) denotan el radio
y el diámetro de G, respectivamente.
2.17. Los grafos bipartitos completos K1,n se llaman estrellas. Probar que un árbol con p ≥ 3 vértices
tiene diámetro 2 si y sólo si es una estrella.
2.18. Dado un grafo conexo G, ¿son ciertas las siguientes afirmaciones?:
(a) Si G tiene diámetro 2, entonces tiene una estrella spanning.
(b) Si G tiene una estrella spanning, entonces tiene diámetro igual a 2.
2.19. Sea T un árbol no trivial y sea P = u0 u1 ...un un arco de longitud máxima en T (en T no hay
arcos de longitud > n). Probar que δ(u0 ) = δ(un ). Como consecuencia probar que un árbol no
trivial tiene más de una hoja.
2.20. Sea T un árbol y sea v un vértice de valencia máxima en T , por ejemplo δ(v) = k. Probar que
T tiene al menos k vértices de valencia 1.

Relación 2

Cargado por

Copyright:

Formatos disponibles

Relación 2

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Relación 2

Cargado por

Copyright:

Formatos disponibles

Matemática Discreta

También podría gustarte