Edición de «Práctica 5: Clases de Grafos (Algoritmos III)»

De Cuba-Wiki
Advertencia: no has iniciado sesión. Tu dirección IP se hará pública si haces cualquier edición. Si inicias sesión o creas una cuenta, tus ediciones se atribuirán a tu nombre de usuario, además de otros beneficios.

Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.

Revisión actual Tu texto
Línea 1: Línea 1:
__NOTOC__
{{Back|Algoritmos y Estructuras de Datos III}}
==Ejercicio 05.01:==
==Ejercicio 05.01:==
<math>3*n = \sum_v 3 \leq \sum_v  d(v) = 2*m = 2*19 = 38</math><br>
<br>3*n = Σ<sub>v</sub> 3 <= Σ<sub>v</sub> d(v) = 2*m = 2*19 = 38
Entonces n <= 38/3 ∼ 12<br>
<br>Entonces n <= 38/3 ∼ 12


==Ejercicio 05.02:==
==Ejercicio 05.02:==
Línea 26: Línea 23:
<br>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
<br>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
<br>Σ{i=1..n} din(vi) = Σ{i=1..n-1} din(vi) + j + din(w)
<br>Σ{i=1..n} din(vi) = Σ{i=1..n-1} din(vi) + j + din(w)
<br>Σ{i=1..n} dout(vi) = Σ{i=1..n-1} dout(vi) + k + dout(w)
<br>Σ{i=1..n-1} dout(vi) = Σ{i=1..n-1} dout(vi) + k + dout(w)
<br>Entonces
<br>Entonces
<br>Σ{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
<br>Σ{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
Línea 35: Línea 32:


==Ejercicio 05.05:==
==Ejercicio 05.05:==
¿Es posible que haya un grupo de 7 personas tal que cada persona conozca exactamente otras 3 personas del grupo?
Si esto pasara entonces Σ<sub>v</sub> d(v) = 2*m <=> 21 = 3*7 = Σ<sub>v</sub> 3 = 2*m <=> Impar = Par ABS => No es posible.
 
Supongamos que <math>\exists G=(V, X)</math>, tal que, <math>|V|=7</math> y <math>|X|=m</math>.
 
Para todo <math>v \in V</math>, <math>d(v) = 3</math>. Entonces, <math>\sum_{i=1}^{7} d(v_i) = \sum_{i=1}^{7} 3 = 21 = 2m \Rightarrow m = \frac{21}{2} \notin \mathbb{N}</math>
 
'''Absurdo!''' m debe ser entero.


==Ejercicio 05.06:==
==Ejercicio 05.06:==
Probar que un grafo <math>G=(V,X)</math> es conexo si y sólo si para toda partición de <math>V</math> en dos subconjuntos <math>V_{1}</math> y <math>V_{2}</math>
(<math>V_{1} \ne \emptyset</math>, <math>V_{2} \ne \emptyset</math>, <math>V_{1} \cap V_{2} = \emptyset</math>, <math>V_{1} \cup V_{2} = V</math>)
hay un arco de G que une un punto de <math>V_{1}</math> con uno de <math>V_{2}</math>.
=>) 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 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 tales que no hay camino entre ellos.
<=) Sup. que no es conexo -> existen 2 vertices vi,vj / no hay camino entre ellos.
<br>Elegimos W1={vi} U Z1, / Z1 = conj. de vertices alcanzables desde vi.
<br>Elegimos W1={vi} U Z1, / Z1 = conj. de vertices alcanzables desde vi.
<br>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.
<br>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.
Línea 68: Línea 55:
** 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
** 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
*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) --> n > d(v) > n-2 --> d(v) = n-1 --> G es conexo.
**(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:==
==Ejercicio 05.08:==
<br>a) Sup. hay dos caminos C1={vi,w1,..,wn,vf} y C2={vi,xl,..,xm,vf} tq {wi,..,wn}∩{xl,..,xm}={}.
<br>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,w1,..,wn,vf,xm,..,x1,vi} se obtiene un circuito.
Entonces, si se elige otro camino C3 = {vi,wi,..,wn,vf,xm,..,x1,vi} se obtiene un circuito.
<br>b) Se forma un circuito no simple
<br>b)


==Ejercicio 05.09:==
==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 .
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)
Veamos primero que en el "subcamino" P' no puede haber vértices ni de C1 ni C2.
* 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)
* 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 (gracias al resultado anterior), 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 o después o en 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:==
==Ejercicio 05.10:==
Línea 95: Línea 73:


<br>b)
<br>b)
<br> =>)
<br> =>) !
<br>G orientable de forma que quede fuertemente conexo => todos los nodos tienen grado mayor o igual que 2.
<br>Todo camino que no es ciclo tiene al menos un nodo de grado 1 (extremos) => como no hay nodos de grado 1, G no tiene caminos que no sean ciclos
<br>Por lo tanto, todos los nodos de G pertenecen a un ciclo.
<br> <=) Sup G' es f. conexo. Si G' = G listo. Si G != G, Ex. v en G-G'
<br> <=) Sup G' es f. conexo. Si G' = G listo. Si G != G, Ex. v en G-G'
<br>Como G es conexo, Ex. camino C de v a w (w en G'). Me quedo con el ultimo eje de C.
<br>Como G es conexo, Ex. camino C de v a w (w en G'). Me quedo con el ultimo eje de C.
Línea 104: Línea 79:
<br>Por HI e pertenece a un ciclo => G'U{C} es f. conexo -> G es f.conexo
<br>Por HI e pertenece a un ciclo => G'U{C} es f. conexo -> G es f.conexo


<br>c) Tiene que formar un grafo fuertemente conexo
<br>c)


==Ejercicio 05.11:==
==Ejercicio 05.11:==
Línea 111: Línea 86:


==Ejercicio 05.12:==
==Ejercicio 05.12:==
<br>=>) Si d1,..,dn es una secuencia valida de grados de un grafo -> Σ di = 2*m = par
<br><=) Como el grafo puede ser pseudografo, tomamos a todos los di pares y haces di/2 loops. Con todos los impares hacemos (di-1)/2 loops y como hay una cantidad par de di impares (pues la suma de todo es par) unimos los di imparers de a pares.
==Ejercicio 05.13:==
==Ejercicio 05.13:==
<br>a) Esto lo saque de una pagina:
<br>a)
<i>
<br>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,...).
</i>
<br> Usando esto se deberia llegar a que las del ej. no lo son.
 
Otra forma seria asi:
<br> (7,6,5,4,3,3,2), si la miramos fijo vemos que n=7 , pero hay un nodo que
<br> tiene 7 ejes y el grado máximo de un nodo (en un grafo simple) es n-1.
<br> (6,6,5,4,3,3,1), en un grafo simple no pueden existir dos nodos con n-1 ejes y un vértice con grado 1, pues todos los nodos son incidentes -al menos- a dos aristas.
 
<br>b)
<br>b)
==Ejercicio 05.14:==
==Ejercicio 05.14:==
<br>Si G tiene m ejes -> Gc tiene n(n-1)/2 - m ejes
<br>Si G tiene m ejes -> Gc tiene n(n-1)/2 - m ejes
Línea 142: Línea 97:
==Ejercicio 05.15:==
==Ejercicio 05.15:==
R es el conj. de grafos tq:
R es el conj. de grafos tq:
* I) Г(v) inc Г(w) o Г(w) inc Г(v)        v,w ady
* Г(v) inc Г(w) o Г(w) inc Г(v)        v,w ady
* II) Г'(v) inc Г'(w) o Г'(w) inc Г'(v)    v,w no ady
* Г'(v) inc Г'(w) o Г'(w) inc Г'(v)    v,w no ady


<pre>
<pre>
Línea 159: Línea 114:


<br>b)
<br>b)
<br>Sup. no vale la propiedad, entonces: todo vértice tiene un adyacente y uno no ady.
<br>Sup. no vale prop. -> Todo vertices tiene un ady o un no ady.
<br>Sean v el vertice de mayor grado, w un vértice no en Г(v)
<br>Sean v el vertice de mayor grado, w no en Г(v)
<br>|Г(w)|<=|Г(v)| sumado a (I),  por (4) vale Г(v) inc Г(w)
<br>|Г(w)|<=|Г(v)| y 1. ->(4). Г(v) inc Г(w)
<br>d(w)>0 --> Existe z en Г(w), luego, z también está en Г(v)
<br>d(w)>0 -> Ex. z en Г(w) -> z en Г(v)
<br>|Г'(z)| = d(z)+1 <= d(v)+1 = |Г'(v)| y por (II), --> Г(z) inc Г(v) --> w está en Г(v) ABSURDO. Entonces debe valer la propiedad.
<br>|Г'(z)| = d(z)+1 <= d(v)+1 = |Г'(v)| y 2. -> Г(z) inc Г(v) -> w en Г(v) ABS


==Ejercicio 05.16:==
==Ejercicio 05.16:==
Línea 172: Línea 127:
==Ejercicio 05.17:==
==Ejercicio 05.17:==
==Ejercicio 05.18:==
==Ejercicio 05.18:==
<br> 1. No
<br> 1. 2. Si 3. 4. Si
<br> 2. Si  
<br> 3. ()
<br> 4. Si


==Ejercicio 05.19:==
==Ejercicio 05.19:==
Línea 182: Línea 134:
<br>c) Es equivalente a decir que d(v) = d(f(v))
<br>c) Es equivalente a decir que d(v) = d(f(v))
<br>d) Vale por la biyeccion entre circuitos simples entre G y H
<br>d) Vale por la biyeccion entre circuitos simples entre G y H
<br>e) Vale por la biyeccion entre comp. conexas entre G y H
<br>e)  
<br>f)
<br>f)
<br>g)
<br>g)


==Ejercicio 05.20:==
==Ejercicio 05.20:==
<br>a) No
<br>a)
<br>b) No
<br>b)
 
==Ejercicio 05.21:==
==Ejercicio 05.21:==
<br>a) o-o-o-o  
<br>a) o-o-o-o
<br>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:  
<br>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:
<br>n=4k -> 4k(4k-1)/4 ≡ 0(4)  
<br> n=4k -> 4k(4k-1)/4 ≡ 0(4)
<br>n=4k+1 -> (4k+1)(4k+1-1)/4 = (4k+1)4k/4 ≡ 0(4)  
<br> n=4k+1 -> (4k+1)(4k+1-1)/4 = (4k+1)4k/4 ≡ 0(4)
<br>n=4k+2 -> (4k+2)(4k+2-1)/4 = (4k+2)(4k+1)/4 ≡ 2(4)  
<br> n=4k+2 -> (4k+2)(4k+2-1)/4 = (4k+2)(4k+1)/4 ≡ 2(4)
<br>n=4k+3 -> (4k+3)(4k+3-1)/4 = (4k+3)(4k+2)/4 ≡ 2(4)  
<br> n=4k+3 -> (4k+3)(4k+3-1)/4 = (4k+3)(4k+2)/4 ≡ 2(4)
<br>-> Con lo cual solo puede pasar que n=4k o n=4k+1
<br> -> Con lo cual solo puede pasar que n=4k o n=4k+1


==Ejercicio 05.22:==
==Ejercicio 05.22:==
<br>a)
<br>a)
<pre>
<br>b)
Mat. Adyacencia:
==Ejercicio 05.23:==
 
<br>a)
  ABCDEF  ABCDEF
A 011100 A 001100
B 101010 B 100000
C 110111 C 010001
D 101011 D 001001
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
</pre>
 
<br>b)
<br>b)
<br>c)
<br>c)
Línea 228: Línea 161:
<br>f)
<br>f)
<br>g)
<br>g)
==Ejercicio 05.23:==
Si D es el grafo dirigido y G el subyacente, y MD y MG sus respectivas matrices de adyacencia, entonces:
Para todo i,j
MG(i,j) = max(MD(i,j), MD(j,i))
==Ejercicio 05.24:==
==Ejercicio 05.24:==
<br>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:
<pre>
M = [ 0 A ]
    [ B 0 ]
</pre>
<br>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.25:==
==Ejercicio 05.25:==
<br>a)
<br>b)
==Ejercicio 05.26:==
Se puede hacer A^(n-1) y tomar todos los distintos de 0 como 1 (ya que son alcanzables)
Se puede hacer A^(n-1) y tomar todos los distintos de 0 como 1 (ya que son alcanzables)
==Ejercicio 05.26:==
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.27:==
==Ejercicio 05.27:==
==Ejercicio 05.28:==
<br>a) Usando la prop. de 5.25 b)
<br>a) Usando la prop. de 5.25 b)
<pre>
<pre>
Línea 259: Línea 180:
<br>b)
<br>b)
<pre>
<pre>
for i = 1..n
for i = 1..n (i impar)
for j = 1..n
for j = 1..n (i impar)
invertir A[i,j];
invertir A[i,j];
</pre>
</pre>
Línea 266: Línea 187:
<br>c) a. O(n^4), b. O(n^2)
<br>c) a. O(n^4), b. O(n^2)


==Ejercicio 05.28:==
==Ejercicio 05.29:==
<br>a)
<br>a)
<br>b)
<br>b)
<br>c)
<br>c)
==Ejercicio 05.29:==
==Ejercicio 05.30:==
<br>a)
<br>a)
<br>b)
<br>b)
<br>c)
<br>c)
[[Category: Prácticas]]
Ten en cuenta que todas las contribuciones a Cuba-Wiki pueden ser editadas, modificadas o eliminadas por otros colaboradores. Si no deseas que las modifiquen sin limitaciones, no las publiques aquí.
Al mismo tiempo, asumimos que eres el autor de lo que escribiste, o lo copiaste de una fuente en el dominio público o con licencia libre (véase Cuba-Wiki:Derechos de autor para más detalles). ¡No uses textos con copyright sin permiso!

Para editar esta página, responde la pregunta que aparece abajo (más información):

Cancelar Ayuda de edición (se abre en una ventana nueva)

Plantilla usada en esta página:

Obtenido de «https://www.cubawiki.com.ar/index.php/Práctica_5:_Clases_de_Grafos_(Algoritmos_III)»