Wituam

UNIVERSIDAD PERUANA DE CIENCIAS ´ E INFORMATICA Facultad de Ciencias e Ingenier´ ıa Carrera Profesional de Ingenier´ de Sistemas ıa e Inform´tica a Solucionario de la Segunda Pr´ctica Calificada a deMatem´tica Discreta a Profesor: Pascual F. Onofre Mayta. 1. Sea G = (V, E) un grafo no dirigido conexo sin bucles que sea 3-regular. Si G es 3-regular, se tiene que ∀v ∈ V : gr (v) = 3 Entonces gr (v)=
v∈V v∈V

gr(v7 ) = 5, gr(v8 ) = 7, Sabemos que
8

gr (v) =
v∈V i=1

gr (vi ) = 2 |E|

(2.1)

De (2.1), se obtiene |E| = 12. No es posible dibujar un grafo no dirigido conexo, simple ysin bucles, puesto que con las condiciones del grafo ´ste es un multie grafo. En efecto, • Empecemos con el v´rtice v8 , el cual e es de grado 7, y de esta manera es adyacente a los otros (sietes)v´rtices en e V , tal como se muestra en la siguiente figura

3 = 3 |V |

Como gr (v) = 2 |E| ,
v∈V

se sigue que 2 |E| = 3 |V | (1.1) • Como G es simple no debe tener aristas m´ltiples, es por estaraz´n que u o el v´rtice v8 se conecta con los dem´s e a v´rtices como se muestra en la figura e anterior. Hasta el momento se tiene 7 aristas. Consideremos el v´rtice v7 e el cual debe conectarse conlos dem´s a v´rtices pero no con los de grados uno e (v1 , v2 y v3 ). Al hacer el intento observamos lo siguiente y reemplazando en (1.1) la condici´n del proo blema |E| = 2 |V | − 6, tenemos 2 (2 |V| − 6) = 3 |V | obteni´ndose |V | = 12. e De (1.1), se obtiene |E| = 18. Un grafo con las caracter´ ısticas del problema es la que se muestra en la siguiente figura

2. (a) Sea el grafo G = (V, E),donde V = {v1 , v2 , v3 , v4 , v5 , v6 , v7 , v8 } tal que gr(v1 ) = 1, gr(v2 ) = 1, gr(v3 ) = 1, gr(v4 ) = 2, gr(v5 ) = 3, gr(v6 ) = 4,

• El v´rtice v7 no puede ser adyacente e a s´ mismo, a menosque tengan buı cles, se sigue que gr(v7 ) ≤ 4 y no podemos trazar un grafo con las condiciones dadas. (b) Se puede dibujar de varias formas el multigrafo. Considerando la ultima figura, y ´...