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 desde vi) hacia uno NO alcanzable, pero entonces habra un camino de vi a vj o a algun vertice de X. ABS

Ejercicio 05.07:

Por induccion en n:

• CB: n=2

m > (n-1)(n-2)/2 = 0. G es conexo <=> G=K2 -> m = 1 > 0 -> OK

• PI:

Sea G'= G-v, tq { si m(G') > ((n-1)-1)((n-1)-2)/2 = (n-2)(n-3)/2 -> G' es conexo }. qvq si m(G) > (n-1)(n-2)/2 -> G es conexo

m(G) = m(G')+d(v)

• Sup. m(G') > (n-2)(n-3)/2
  • Si d(v) > 0 -> v conecta con algun vert. de G' -> Como G' es conexo, G sigue siendo conexo
  • Si d(v) = 0 -> m(G) = m(G') > (n-1)(n-2)/2. Pero G' no puede tener mas ejes que el grafo completo K(n-1) -> ABS
• Sup. m(G') <= (n-2)(n-3)/2
  • (n-1)(n-2)/2 < m(G) = m(G') + d(v) <= (n-2)(n-3)/2 + d(v) -> d(v) > n-1 -> ABS

Ejercicio 05.08:

a) Sup. hay dos caminos C1={vi,wi,..,wn,vf} y C2={vi,xl,..,xm,vf} tq {wi,..,wn}∩{xl,..,xm}={}. Entonces, si se elige otro camino C3 = {vi,wi,..,wn,vf,xm,..,x1,vi} se obtiene un circuito.
b)

Ejercicio 05.09:

Sean G conexo y 2 de los caminos de long. maxima C1 = {vi,vi+1,..,wi+k} y C2 = {wi,wi+1,..,wi+k}. Sup. que no tienen un vertice en comun. Como es conexo, hay un camino de Vi a Vj.

• 1. Si vi y vj estan conectados -> ABS (el camino simple de long. maxima seria la union de C1 y C2, que es mas largo que la long. maxima)
• 2. Si no estan conectados a traves que no estan en C1 o C2, esos vertices podrian ser agregados a C1 o C2 -> ABS (C1 y C2 ya no tendria long maxima)

Ejercicio 05.10:

a)
Si un digrafo es fuertemente conexo -> se puede ir desde cualquier vertice a otro, lo que es la def. de grafo conexo.
La reciproca no vale, por ej: o->o<-o. Si bien el grafo subyacente es conexo, no es posible llegar de un vertice cualquiera a otro.

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) (Hay que hallar las cliques maximas)

Ejercicio 05.13:

a)
b)

Ejercicio 05.14:

Si G tiene m ejes -> Gc tiene n(n-1)/2 - m ejes
Sea V={v1,..,vn} / v1,..,vn-1 tienen grado impar y vn tiene grado par.
Sea vi de grado impar -> dG(vi) = 2k+1. Si dG(vi) = 2k+1 -> dGc(vi) = (n-1)-(2k+1)=n-2-2k
->Si n es impar habra n-1 vertices de grado impar, sino habra 1

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.18:

1. 2. Si 3. 4. Si

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) o-o-o-o
b) Si G es autocomplementario entonces m = n(n-1)/2 - m -> 2m = n(n-1)/2 -> m = n(n-1)/4 (entonces m ≡ 0(4)). Viendo las congruencias modulo 4:
n=4k -> 4k(4k-1)/4 ≡ 0(4)
n=4k+1 -> (4k+1)(4k+1-1)/4 = (4k+1)4k/4 ≡ 0(4)
n=4k+2 -> (4k+2)(4k+2-1)/4 = (4k+2)(4k+1)/4 ≡ 2(4)
n=4k+3 -> (4k+3)(4k+3-1)/4 = (4k+3)(4k+2)/4 ≡ 2(4)
-> Con lo cual solo puede pasar que n=4k o n=4k+1

Ejercicio 05.22:

a)
b)

Ejercicio 05.23:

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

Ejercicio 05.25:

a)
b)

Ejercicio 05.26:

Se puede hacer A^(n-1) y tomar todos los distintos de 0 como 1 (ya que son alcanzables)

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)