Práctica 5: Clases de Grafos (Algoritmos III)

Ejercicio 05.01:

3*n = Σ_v 3 <= Σ_v d(v) = 2*m = 2*19 = 38
Entonces n <= 38/3 ∼ 12

Ejercicio 05.02:

a)
2*n = Σ_v 2 = Σ_v d(v) = 2*m = 2*12 = 24
Entonces n = 24/2 = 12
b)
3*n + 3 = 12 + 3*n - 9 = 3*4+(n-3)*3 = Σ_v d(v) = 2*m = 2*15 = 30
Entonces n = 27/3 = 9
c)
k*n = Σ_v d(v) = 2*m = 2*20 = 40
Entonces n = 40/k

Ejercicio 05.03:

P(n) = G digrafo de n vertices -> Σ din(v) = Σ dout(v) (todo v en V)

• CB: n = 1

Σ din(v) = Σ dout(v) <=> 0 = 0 OK

• PI: P(n-1)->P(n)

Sup. que vale para un digrafo de n-1 vertices. qvq vale para G, si agregamos un vertice w de k ejes de entrada y j de salida. Sabemos que
Σ{i=1..n} din(vi) = Σ{i=1..n-1} din(vi) + j + din(w)
Σ{i=1..n-1} dout(vi) = Σ{i=1..n-1} dout(vi) + k + dout(w)
Entonces
Σ{i=1..n} din(vi) = Σ{i=1..n} dout(vi) <=> Σ{i=1..n-1} din(vi) + j + din(w) = Σ{i=1..n-1} dout(vi) + k + dout(w) <=> (Por HI Σ{i=1..n-1} din(vi) = Σ{i=1..n-1} dout(vi)) j + din(w) = k + dout(w) <=> j + k = k + j -> OK

Ejercicio 05.04:

Sup. que todos los grados son distintos. Entonces los vertices tienen todos los grados posibles, de 0 a n-1. Pero si esto pasa, entonces tengo un vertice conectado a todos (el de grado n-1) y al mismo tiempo otro conectado a ninguno (el de grado 0). ABS => Existen 2 vertices del mismo grado.

Ejercicio 05.05:

Si esto pasara entonces Σ_v d(v) = 2*m <=> 21 = 3*7 = Σ_v 3 = 2*m <=> Impar = Par ABS => No es posible.

Ejercicio 05.06:

=>) Sup. que no hay arcos de V1 a V2. Sea W1={V1} y W2={V2,..,Vn}. Pero como no hay arco de V1 a V2, entonces no existe camino de V1 a V2. G no es conexo. ABS

<=) Sup. que no es conexo -> existen 2 vertices vi,vj / no hay camino entre ellos.
Elegimos W1={vi} U Z1, / Z1 = conj. de vertices alcanzables desde vi.
Elegimos W2={vj} U Z2 U X, /Z2 = conj. de vertices alcanzables desde vj y X conj. de vertices NO alcanzables desde vi y vj.
Si no hay camino entre vi y vj. W1∩W2 = {}. Pero sabemos que debe haber un arco entre W1 y W2, por lo tanto sera desde un vertice alcanzable por vi (o vi) hacia uno NO alcanzable, pero entonces habra un camino de vi a vj o a algun vertice de X. ABS

Ejercicio 05.08:

a)
b)

Ejercicio 05.10:

a)
b)
=>) !
<=) Sup G' es f. conexo. Si G' = G listo. Si G != G, Ex. v en G-G'
Como G es conexo, Ex. camino C de v a w (w en G'). Me quedo con el ultimo eje de C.
Ex. v' no en G' / e = (v',w).
Por HI e pertenece a un ciclo => G'U{C} es f. conexo -> G es f.conexo

c)

Ejercicio 05.11:

a)
b)

Ejercicio 05.13:

a)
b)

Ejercicio 05.15:

R es el conj. de grafos tq:

• Г(v) inc Г(w) o Г(w) inc Г(v) v,w ady
• Г'(v) inc Г'(w) o Г'(w) inc Г'(v) v,w no ady

OBS: 1. Sean S,T conj. Si |S|=|T| y S inc T o T inc S -> S=T
     2. |Г(v)|=d(v) y |Г'(v)|=d(v)+1
     3. v en Г(w) <=> v,w ady
     4. Sean S,T conj. Si |S|>=|T| y S inc T o T inc S -> T inc s

a)
Sup. no vale prop. -> Ex. u,v,w / d(u)=d(v)=d(w) y u en Г(v) y u no en Г(w)
|Г'(u)| = d(u)+1 = d(v)+1 = |Г'(v)| y 2. ->(1.) Г'(u) = Г'(v) -> v no en Г(w)
|Г(w)| = d(w)+1 = d(u)+1 = |Г(u)| y 1. -> Г(w) = Г(u) -> v en Г(w) ABS
-> Solo pueden ser todos ady o todos no ady.

b)
Sup. no vale prop. -> Todo vertices tiene un ady o un no ady.
Sean v el vertice de mayor grado, w no en Г(v)
|Г(w)|<=|Г(v)| y 1. ->(4). Г(v) inc Г(w)
d(w)>0 -> Ex. z en Г(w) -> z en Г(v)
|Г'(z)| = d(z)+1 <= d(v)+1 = |Г'(v)| y 2. -> Г(z) inc Г(v) -> w en Г(v) ABS

Ejercicio 05.16:

a)
b)
c)
d)

Ejercicio 05.19:

a) Vale por la biyeccion entre V y V'
b) Sup. que |E|>|E'| => existe e en E / e = (v,w) y no existe (f(v),f(w)) ABS
c) Es equivalente a decir que d(v) = d(f(v))
d) Vale por la biyeccion entre circuitos simples entre G y H
e)
f)
g)

Ejercicio 05.20:

a)
b)

Ejercicio 05.21:

a)
b)

Ejercicio 05.22:

a)
b)

Ejercicio 05.23:

a)
b)
c)
d)
e)
f)
g)

Ejercicio 05.25:

a)
b)

Ejercicio 05.28:

a) Usando la prop. de 5.25 b)

for i = 1..n (i impar)
	si (diagonal A^i no es nula)
		devolver falso;
devolver verdadero;

b)

for i = 1..n (i impar)
	for j = 1..n (i impar)
		invertir A[i,j];

c) a. O(n^4), b. O(n^2)

Ejercicio 05.29:

a)
b)
c)

Ejercicio 05.30:

a)
b)
c)