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 18: |
Línea 15: |
|
| |
|
| ==Ejercicio 05.03:== | | ==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)
| |
|
| |
| <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} dout(vi) = Σ{i=1..n-1} dout(vi) + k + dout(w)
| |
| <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
| |
|
| |
| ==Ejercicio 05.04:== | | ==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 | | 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 |
Línea 35: |
Línea 20: |
|
| |
|
| ==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 es conexo -> existen 2 vertices vi,vj tales que no hay camino entre ellos.
| |
| <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>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:== | | ==Ejercicio 05.07:== |
| <br>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) --> n > d(v) > n-2 --> d(v) = n-1 --> G es conexo.
| |
|
| |
| ==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) |
| Entonces, si se elige otro camino C3 = {vi,w1,..,wn,vf,xm,..,x1,vi} se obtiene un circuito.
| | <br>b) |
| <br>b) Se forma un circuito no simple | |
| | |
| ==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 .
| |
|
| |
| Veamos primero que en el "subcamino" 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 (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:== |
| <br>a) | | <br>a) |
| <br> 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.
| |
| <br> 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.
| |
|
| |
| <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 37: |
| <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:== |
| <br>a) | | <br>a) |
| <br>b) (Hay que hallar las cliques maximas) | | <br>b) |
| | |
| ==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>Sea V={v1,..,vn} / v1,..,vn-1 tienen grado impar y vn tiene grado par.
| |
| <br>Sea vi de grado impar -> dG(vi) = 2k+1. Si dG(vi) = 2k+1 -> dGc(vi) = (n-1)-(2k+1)=n-2-2k
| |
| <br>->Si n es impar habra n-1 vertices de grado impar, sino habra 1
| |
|
| |
| ==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 66: |
|
| |
|
| <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 79: |
| ==Ejercicio 05.17:== | | ==Ejercicio 05.17:== |
| ==Ejercicio 05.18:== | | ==Ejercicio 05.18:== |
| <br> 1. No
| |
| <br> 2. Si
| |
| <br> 3. ()
| |
| <br> 4. Si
| |
|
| |
| ==Ejercicio 05.19:== | | ==Ejercicio 05.19:== |
| <br>a) Vale por la biyeccion entre V y V' | | <br>a) Vale por la biyeccion entre V y V' |
| <br>b) Sup. que |E|>|E'| => existe e en E / e = (v,w) y no existe (f(v),f(w)) ABS | | <br>b) Sup. que |E|>|E'| => existe e en E / e = (v,w) y no existe (f(v),f(w)) ABS |
| <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) |
| <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) |
| <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) |
| <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+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>-> 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 105: |
| <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:== |
| Se puede hacer A^(n-1) y tomar todos los distintos de 0 como 1 (ya que son alcanzables)
| | <br>a) |
| | | <br>b) |
| ==Ejercicio 05.26:== | | ==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:== |
| <br>a) Usando la prop. de 5.25 b)
| |
| <pre>
| |
| for i = 1..n (i impar)
| |
| si (diagonal A^i no es nula)
| |
| devolver falso;
| |
| devolver verdadero;
| |
| </pre>
| |
|
| |
| <br>b)
| |
| <pre>
| |
| for i = 1..n
| |
| for j = 1..n
| |
| invertir A[i,j];
| |
| </pre>
| |
|
| |
| <br>c) a. O(n^4), b. O(n^2)
| |
|
| |
| ==Ejercicio 05.28:== | | ==Ejercicio 05.28:== |
| <br>a) | | <br>a) |
Línea 274: |
Línea 119: |
| <br>b) | | <br>b) |
| <br>c) | | <br>c) |
| | | ==Ejercicio 05.30:== |
| | | <br>a) |
| [[Category: Prácticas]]
| | <br>b) |
| | <br>c) |