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

De Cuba-Wiki
Revisión del 18:35 11 may 2007 de 201.235.48.153 (discusión) (→‎Ejercicio 05.09:: Creo que estaba mal, puse otra demo)

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,w1,..,wn,vf} y C2={vi,xl,..,xm,vf} tq {wi,..,wn}∩{xl,..,xm}={}. Entonces, si se elige otro camino C3 = {vi,w1,..,wn,vf,xm,..,x1,vi} se obtiene un circuito.
b) Se forma un circuito no simple

Ejercicio 05.09:

Sean G conexo y 2 de los caminos de long. maxima C1 = {vi,vi+1,..,vi+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 wj para todo i y j. Tomemos al camino mínimo P de todos los de la forma: P = vi-P'-wj .

Veamos que en P' no puede haber vértices ni de C1 ni C2.

  • Supongamos que vl pertenece a P' . Entonces P = vi-P1-vl-P2-wj . Pero entonces el camino vl-P2-wj es más corto que P y es de la forma vi-P'-wj. Absurdo, ya que P era mínimo dijimos. Entonces P' no puede tener vértices de C1 ni C2 (con un razonamiento análogo se ve para C2).

Ahora, sigamos con P. Los siguientes caminos son simples, y se ve que alguno de ellos tiene mayor longitud que C1 y C2 (se ve ya que tanto vi como wj están antes od después de la mitad de C1 y C2, entonces nos quedamos con la parte más larga de C1 y la más larga de C2): v1...vi-P'-wj...w1 v1...vi-P'-wj...wk vk...vi-P'-wj...w1 vk...vi-P'-wj...w1

Esto es absurdo, ya que C1 y C2 eran de longitud máxima, y este absurdo provino de suponer que no tenían ningún vértice en común.

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, por lo que si hay camino orientado entre dos vertices cualquiera tambien habra uno no orientado entre esos vertices.
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) Tiene que formar un grafo fuertemente conexo

Ejercicio 05.11:


a)
b) (Hay que hallar las cliques maximas)

Ejercicio 05.12:


=>) Si d1,..,dn es una secuencia valida de grados de un grafo -> Σ di = 2*m = par
<=) Mm.. esto creo que sale usando el algoritmo que esta en 5.13

Ejercicio 05.13:


a) Esto lo saque de una pagina:
Una secuencia numérica decreciente representa una lista de grados de una gráfica si el siguiente algoritmo devuelve una lista de ceros: (Algoritmo de Havel-Hakimi)

  • P.1 Leer la lista creciente (a1,a2,...,ap).
  • P.2 Mientras el primer elemento sea a1>0
    • P.3 Eliminar el elemento a1 de la lista.
    • P.4 Restar 1 a los primeros a1 elementos de la nueva lista.
    • P.5 Ordenar (decreciente) la nueva lista.
  • P.6 Retornar la lista (a1,a2,...).


Usando esto se deberia llegar a que las del ej. no lo son.


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

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) Vale por la biyeccion entre comp. conexas entre G y H
f)
g)

Ejercicio 05.20:


a) No
b) No

Ejercicio 05.21:


a)
b)

Ejercicio 05.22:


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


a) 

Mat. Adyacencia:

  ABCDEF   ABCDEF
A 011100 A 001100
B 101010 B 100000 
C 110111 C 010001
D 101011 D 001011
E 011101 E 011100
F 001110 F 000010

  ABCDEFG   ABCDEFG
A 0111111 A 0110011 
B 1000000 B 0000000 
C 1001100 C 0000100
D 1010100 D 1010000
E 1011001 E 1001000
F 1000001 F 0000001
G 1000110 G 0000100


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

Ejercicio 05.24:

Asegurando la simetria, es decir, que para todo i,j, Aij = Aji

Ejercicio 05.25:


a) Si se toman como filas/columnas de la matriz de adyacencia de un grafo bipartito a v1,..,vm,w1,..,wn, donde v1,..,vm son los vertices de una particion y w1,..wn los de la otra, entonces la matriz se puede dividir de la siguiente forma: 

M = [ 0 A ]
    [ B 0 ]


b) Como n es impar -> aii^n = cant. de recorridos de long. n desde el vertice vi a si mismo = cant. de circuitos de long. impar que contienen el vertice vi. Con lo cual, si aii^n = 0 para todo i y todo n impar, se esta asegurando que el grafo sea bipartito

Ejercicio 05.26:

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

Ejercicio 05.27:

Si dos grafos son isomorfos, entonces debe existir una forma de intercambiar las filas y luego las columnas de la matriz de adyacencia de uno para que sea igual a la del otro. Como el problema de isomorfismo es NP, no se conoce un buen algoritmo para decidirlo.

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)

Obtenido de «https://www.cubawiki.com.ar/index.php?title=Práctica_5:_Clases_de_Grafos_(Algoritmos_III)&oldid=1404»