https://www.cubawiki.com.ar/index.php?title=Final_del_12/02/10_(Algoritmos_III)&feed=atom&action=history
Final del 12/02/10 (Algoritmos III) - Historial de revisiones
2024-03-29T10:43:40Z
Historial de revisiones de esta página en la wiki
MediaWiki 1.39.2
https://www.cubawiki.com.ar/index.php?title=Final_del_12/02/10_(Algoritmos_III)&diff=8210&oldid=prev
190.139.145.64: /* Ejercicio 1 */ Corregir una -> un
2010-12-12T06:10:53Z
<p><span dir="auto"><span class="autocomment">Ejercicio 1: </span> Corregir una -> un</span></p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="es">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Revisión anterior</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revisión del 06:10 12 dic 2010</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1">Línea 1:</td>
<td colspan="2" class="diff-lineno">Línea 1:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{Back|Algoritmos y Estructuras de Datos III}}</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{Back|Algoritmos y Estructuras de Datos III}}</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Ejercicio 1 ==</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Ejercicio 1 ==</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>a) Si el camino entre ''i'' y ''j'' tiene más de <del style="font-weight: bold; text-decoration: none;">una </del>camino mínimo ¿Cual elige Floyd?.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>a) Si el camino entre ''i'' y ''j'' tiene más de <ins style="font-weight: bold; text-decoration: none;">un </ins>camino mínimo ¿Cual elige Floyd?.</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>b) Adaptarlo para que calcule los caminos mas cortos tal que no pasen por un conjunto de nodos dado.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>b) Adaptarlo para que calcule los caminos mas cortos tal que no pasen por un conjunto de nodos dado.</div></td></tr>
</table>
190.139.145.64
https://www.cubawiki.com.ar/index.php?title=Final_del_12/02/10_(Algoritmos_III)&diff=8030&oldid=prev
201.231.234.10: /* Ejercicio 3 */
2010-08-05T20:31:29Z
<p><span dir="auto"><span class="autocomment">Ejercicio 3</span></span></p>
<p><b>Página nueva</b></p><div>{{Back|Algoritmos y Estructuras de Datos III}}<br />
== Ejercicio 1 ==<br />
a) Si el camino entre ''i'' y ''j'' tiene más de una camino mínimo ¿Cual elige Floyd?.<br />
<br />
b) Adaptarlo para que calcule los caminos mas cortos tal que no pasen por un conjunto de nodos dado.<br />
<br />
== Ejercicio 2 ==<br />
''G=''(''V,X'') es Hamiltoniano entonces para todo <math>S \in V, S \neq \empty</math> <br />
<br />
<math> W(G-S) \leq |S|</math> (''W''(''G'') es la cantidad de componentes conexas de ''G'')<br />
<br />
a) Dar un ejemplo de que el teorema no es una condición suficiente para asegurar que el grafo es hamiltoniano.<br />
<br />
b) Mostrar, usando el teorema, que el grafo de la figura no es hamiltoniano.<br />
<br />
<br />
[[Image:Grafo.png|thumb|Grafo ej. 2]]<br />
<br />
== Ejercicio 3 ==<br />
Un grafo G es coloreable en forma única si todo coloreo induce la misma partición de los vértices. Probar que si G es coloreable de forma única entonces el subgrafo inducido por dos conjuntos cualesquiera de la partición es conexo.<br />
<br />
== Ejercicio 4 ==<br />
Dado un flujo máximo que puede circular por una red donde <math>C_e</math> es la capacidad máxima de la arista ''e'' y <math>F_e</math> es el valor del flujo del arco ''e'', decimos que el arco es ''vital máximo'' si al eliminarlo de la red se produce el máximo decrecimiento del valor del flujo (obtenido eliminando un solo arco). Decir si es V o F y justificar.<br />
<br />
a) Un arco vital máximo es un arco ''e'' que tiene valor maximo de <math>C_e</math>.<br />
<br />
b) Un arco vital máximo es un arco ''e'' que tiene valor maximo de <math>F_e</math>.<br />
<br />
c) Un arco vital máximo es un arco ''e'' que tiene valor maximo de <math>F_e</math> entre los que pertenecen a un corte mínimo.<br />
<br />
d) Un arco que no pertenece a un corte de capacidad mínima no puede ser un arco vital máximo.<br />
<br />
e) Una red puede contener varios arcos vitales maximos.<br />
<br />
== Ejercicio 5 ==<br />
a) ¿Qué se puede decir de <math>\Pi_1</math> sabiendo que existe una reducción polinomial de <math>\Pi_1</math> a <math>\Pi_2</math> y que <math>\Pi_2 \in P </math>?<br />
<br />
b) ¿Qué se puede decir de <math>\Pi_1</math> sabiendo que existe una reducción polinomial de <math>\Pi_1</math> a <math>\Pi_2</math> y que <math>\Pi_2 \in NP</math> ?<br />
<br />
c) ¿Qué se puede decir de <math>\Pi_1</math> sabiendo que existe una reducción polinomial de <math>\Pi_1</math> a <math>\Pi_2</math> y que <math>\Pi_2 \in NP-Completo </math> ?<br />
<br />
d) ¿Qué se puede decir de <math>\Pi_2</math> sabiendo que existe una reducción polinomial de <math>\Pi_1</math> a <math>\Pi_2</math> y que <math>\Pi_1 \in NP-Completo</math> ?<br />
<br />
e) ¿Qué se puede decir de <math>\Pi_2</math> sabiendo que existe una reducción polinomial de <math>\Pi_1</math> a <math>\Pi_2</math> y que <math>\Pi_1 \in NP-Completo</math> y <math>\Pi_2 \in NP</math>?<br />
<br />
[[Category:Finales]]</div>
201.231.234.10
https://www.cubawiki.com.ar/index.php?title=Final_del_12/02/10_(Algoritmos_III)&diff=7595&oldid=prev
200.69.58.171: /* Ejercicio 1 */
2010-02-23T03:52:35Z
<p><span dir="auto"><span class="autocomment">Ejercicio 1</span></span></p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="es">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Revisión anterior</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revisión del 03:52 23 feb 2010</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1">Línea 1:</td>
<td colspan="2" class="diff-lineno">Línea 1:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Ejercicio 1 ==</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Ejercicio 1 ==</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>a) Si el camino entre ''i'' y ''j'' tiene <del style="font-weight: bold; text-decoration: none;">mas </del>de una camino mínimo ¿Cual elige Floyd?.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>a) Si el camino entre ''i'' y ''j'' tiene <ins style="font-weight: bold; text-decoration: none;">más </ins>de una camino mínimo ¿Cual elige Floyd?.</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>b) Adaptarlo para que calcule los caminos mas cortos tal que no pasen por un conjunto de nodos dado.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>b) Adaptarlo para que calcule los caminos mas cortos tal que no pasen por un conjunto de nodos dado.</div></td></tr>
</table>
200.69.58.171
https://www.cubawiki.com.ar/index.php?title=Final_del_12/02/10_(Algoritmos_III)&diff=7594&oldid=prev
200.69.58.171: /* Ejercicio 1 */
2010-02-23T03:50:29Z
<p><span dir="auto"><span class="autocomment">Ejercicio 1</span></span></p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="es">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Revisión anterior</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revisión del 03:50 23 feb 2010</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1">Línea 1:</td>
<td colspan="2" class="diff-lineno">Línea 1:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Ejercicio 1 ==</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Ejercicio 1 ==</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>a) Si el camino entre ''i'' y ''j'' tiene mas de una camino mínimo ¿Cual elige Floyd?.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>a) Si el camino entre ''i'' y ''j'' tiene mas de una camino mínimo ¿Cual elige Floyd?.</div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>b) Adaptarlo para que calcule los caminos mas cortos tal que no pasen por un conjunto de nodos dado.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>b) Adaptarlo para que calcule los caminos mas cortos tal que no pasen por un conjunto de nodos dado.</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
</table>
200.69.58.171
https://www.cubawiki.com.ar/index.php?title=Final_del_12/02/10_(Algoritmos_III)&diff=7593&oldid=prev
200.69.58.171: /* Ejercicio 5 */
2010-02-23T03:49:15Z
<p><span dir="auto"><span class="autocomment">Ejercicio 5</span></span></p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="es">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Revisión anterior</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revisión del 03:49 23 feb 2010</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l29">Línea 29:</td>
<td colspan="2" class="diff-lineno">Línea 29:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Ejercicio 5 ==</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Ejercicio 5 ==</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>a) <del style="font-weight: bold; text-decoration: none;">¿Que </del>se puede decir de \<del style="font-weight: bold; text-decoration: none;">pi_1 </del>sabiendo que existe una <del style="font-weight: bold; text-decoration: none;">reduccion </del>polinomial de \<del style="font-weight: bold; text-decoration: none;">pi_1 </del>a \<del style="font-weight: bold; text-decoration: none;">pi_2 </del>y que \<del style="font-weight: bold; text-decoration: none;">pi_2 </del>\in P ?</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>a) <ins style="font-weight: bold; text-decoration: none;">¿Qué </ins>se puede decir de <ins style="font-weight: bold; text-decoration: none;"><math></ins>\<ins style="font-weight: bold; text-decoration: none;">Pi_1</math> </ins>sabiendo que existe una <ins style="font-weight: bold; text-decoration: none;">reducción </ins>polinomial de <ins style="font-weight: bold; text-decoration: none;"><math></ins>\<ins style="font-weight: bold; text-decoration: none;">Pi_1</math> </ins>a <ins style="font-weight: bold; text-decoration: none;"><math></ins>\<ins style="font-weight: bold; text-decoration: none;">Pi_2</math> </ins>y que <ins style="font-weight: bold; text-decoration: none;"><math></ins>\<ins style="font-weight: bold; text-decoration: none;">Pi_2 </ins>\in P <ins style="font-weight: bold; text-decoration: none;"></math></ins>?</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>b) <del style="font-weight: bold; text-decoration: none;">¿Que </del>se puede decir de \<del style="font-weight: bold; text-decoration: none;">pi_1 </del>sabiendo que existe una <del style="font-weight: bold; text-decoration: none;">reduccion </del>polinomial de \<del style="font-weight: bold; text-decoration: none;">pi_1 </del>a \<del style="font-weight: bold; text-decoration: none;">pi_2 </del>y que \<del style="font-weight: bold; text-decoration: none;">pi_2 </del>\in NP ?</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>c) <del style="font-weight: bold; text-decoration: none;">¿Que </del>se puede decir de \<del style="font-weight: bold; text-decoration: none;">pi_1 </del>sabiendo que existe una <del style="font-weight: bold; text-decoration: none;">reduccion </del>polinomial de \<del style="font-weight: bold; text-decoration: none;">pi_1 </del>a \<del style="font-weight: bold; text-decoration: none;">pi_2 </del>y que \<del style="font-weight: bold; text-decoration: none;">pi_2 </del>\in NP-Completo ?</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>b) <ins style="font-weight: bold; text-decoration: none;">¿Qué </ins>se puede decir de <ins style="font-weight: bold; text-decoration: none;"><math></ins>\<ins style="font-weight: bold; text-decoration: none;">Pi_1</math> </ins>sabiendo que existe una <ins style="font-weight: bold; text-decoration: none;">reducción </ins>polinomial de <ins style="font-weight: bold; text-decoration: none;"><math></ins>\<ins style="font-weight: bold; text-decoration: none;">Pi_1</math> </ins>a <ins style="font-weight: bold; text-decoration: none;"><math></ins>\<ins style="font-weight: bold; text-decoration: none;">Pi_2</math> </ins>y que <ins style="font-weight: bold; text-decoration: none;"><math></ins>\<ins style="font-weight: bold; text-decoration: none;">Pi_2 </ins>\in NP<ins style="font-weight: bold; text-decoration: none;"></math> </ins>?</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>d) <del style="font-weight: bold; text-decoration: none;">¿Que </del>se puede decir de \<del style="font-weight: bold; text-decoration: none;">pi_2 </del>sabiendo que existe una <del style="font-weight: bold; text-decoration: none;">reduccion </del>polinomial de \<del style="font-weight: bold; text-decoration: none;">pi_1 </del>a \<del style="font-weight: bold; text-decoration: none;">pi_2 </del>y que \<del style="font-weight: bold; text-decoration: none;">pi_1 </del>\in NP-Completo ?</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>e) <del style="font-weight: bold; text-decoration: none;">¿Que </del>se puede decir de \<del style="font-weight: bold; text-decoration: none;">pi_2 </del>sabiendo que existe una <del style="font-weight: bold; text-decoration: none;">reduccion </del>polinomial de \<del style="font-weight: bold; text-decoration: none;">pi_1 </del>a \<del style="font-weight: bold; text-decoration: none;">pi_2 </del>y que \<del style="font-weight: bold; text-decoration: none;">pi_1 </del>\in NP-Completo y \<del style="font-weight: bold; text-decoration: none;">pi_2 </del>\in NP?</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>c) <ins style="font-weight: bold; text-decoration: none;">¿Qué </ins>se puede decir de <ins style="font-weight: bold; text-decoration: none;"><math></ins>\<ins style="font-weight: bold; text-decoration: none;">Pi_1</math> </ins>sabiendo que existe una <ins style="font-weight: bold; text-decoration: none;">reducción </ins>polinomial de <ins style="font-weight: bold; text-decoration: none;"><math></ins>\<ins style="font-weight: bold; text-decoration: none;">Pi_1</math> </ins>a <ins style="font-weight: bold; text-decoration: none;"><math></ins>\<ins style="font-weight: bold; text-decoration: none;">Pi_2</math> </ins>y que <ins style="font-weight: bold; text-decoration: none;"><math></ins>\<ins style="font-weight: bold; text-decoration: none;">Pi_2 </ins>\in NP-Completo <ins style="font-weight: bold; text-decoration: none;"></math> </ins>?</div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>d) <ins style="font-weight: bold; text-decoration: none;">¿Qué </ins>se puede decir de <ins style="font-weight: bold; text-decoration: none;"><math></ins>\<ins style="font-weight: bold; text-decoration: none;">Pi_2</math> </ins>sabiendo que existe una <ins style="font-weight: bold; text-decoration: none;">reducción </ins>polinomial de <ins style="font-weight: bold; text-decoration: none;"><math></ins>\<ins style="font-weight: bold; text-decoration: none;">Pi_1</math> </ins>a <ins style="font-weight: bold; text-decoration: none;"><math></ins>\<ins style="font-weight: bold; text-decoration: none;">Pi_2</math> </ins>y que <ins style="font-weight: bold; text-decoration: none;"><math></ins>\<ins style="font-weight: bold; text-decoration: none;">Pi_1 </ins>\in NP-Completo<ins style="font-weight: bold; text-decoration: none;"></math> </ins>?</div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>e) <ins style="font-weight: bold; text-decoration: none;">¿Qué </ins>se puede decir de <ins style="font-weight: bold; text-decoration: none;"><math></ins>\<ins style="font-weight: bold; text-decoration: none;">Pi_2</math> </ins>sabiendo que existe una <ins style="font-weight: bold; text-decoration: none;">reducción </ins>polinomial de <ins style="font-weight: bold; text-decoration: none;"><math></ins>\<ins style="font-weight: bold; text-decoration: none;">Pi_1</math> </ins>a <ins style="font-weight: bold; text-decoration: none;"><math></ins>\<ins style="font-weight: bold; text-decoration: none;">Pi_2</math> </ins>y que <ins style="font-weight: bold; text-decoration: none;"><math></ins>\<ins style="font-weight: bold; text-decoration: none;">Pi_1 </ins>\in NP-Completo<ins style="font-weight: bold; text-decoration: none;"></math> </ins>y <ins style="font-weight: bold; text-decoration: none;"><math></ins>\<ins style="font-weight: bold; text-decoration: none;">Pi_2 </ins>\in NP<ins style="font-weight: bold; text-decoration: none;"></math></ins>?</div></td></tr>
</table>
200.69.58.171
https://www.cubawiki.com.ar/index.php?title=Final_del_12/02/10_(Algoritmos_III)&diff=7592&oldid=prev
200.69.58.171: /* Ejercicio 4 */
2010-02-23T03:39:35Z
<p><span dir="auto"><span class="autocomment">Ejercicio 4</span></span></p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="es">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Revisión anterior</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revisión del 03:39 23 feb 2010</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l16">Línea 16:</td>
<td colspan="2" class="diff-lineno">Línea 16:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Ejercicio 4 ==</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Ejercicio 4 ==</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Dado un flujo máximo que puede circular por una red donde <math>C_e</math> es la capacidad máxima de la arista ''e'' y <math>F_e</math> es el valor del flujo del arco ''e'', decimos que el arco es ''vital máximo'' si al eliminarlo de la red se produce el máximo decrecimiento del valor del flujo (obtenido eliminando un solo arco). Decir si es V o F y justificar<del style="font-weight: bold; text-decoration: none;">-</del></div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Dado un flujo máximo que puede circular por una red donde <math>C_e</math> es la capacidad máxima de la arista ''e'' y <math>F_e</math> es el valor del flujo del arco ''e'', decimos que el arco es ''vital máximo'' si al eliminarlo de la red se produce el máximo decrecimiento del valor del flujo (obtenido eliminando un solo arco). Decir si es V o F y justificar<ins style="font-weight: bold; text-decoration: none;">.</ins></div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>a) Un arco vital máximo es un arco e que tiene valor maximo de <math>C_e</math>.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>a) Un arco vital máximo es un arco <ins style="font-weight: bold; text-decoration: none;">''</ins>e<ins style="font-weight: bold; text-decoration: none;">'' </ins>que tiene valor maximo de <math>C_e</math>.</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>b) Un arco vital máximo es un arco e que tiene valor maximo de <math>F_e</math>.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>b) Un arco vital máximo es un arco <ins style="font-weight: bold; text-decoration: none;">''</ins>e<ins style="font-weight: bold; text-decoration: none;">'' </ins>que tiene valor maximo de <math>F_e</math>.</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>c) Un arco vital máximo es un arco e que tiene valor maximo de <<del style="font-weight: bold; text-decoration: none;">/</del>math>F_e</math> entre los que pertenecen a un corte mínimo.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>c) Un arco vital máximo es un arco <ins style="font-weight: bold; text-decoration: none;">''</ins>e<ins style="font-weight: bold; text-decoration: none;">'' </ins>que tiene valor maximo de <math>F_e</math> entre los que pertenecen a un corte mínimo.</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>d) Un arco que no pertenece a un corte de capacidad mínima no puede ser un arco vital máximo.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>d) Un arco que no pertenece a un corte de capacidad mínima no puede ser un arco vital máximo.</div></td></tr>
</table>
200.69.58.171
https://www.cubawiki.com.ar/index.php?title=Final_del_12/02/10_(Algoritmos_III)&diff=7591&oldid=prev
200.69.58.171: /* Ejercicio 4 */
2010-02-23T03:37:48Z
<p><span dir="auto"><span class="autocomment">Ejercicio 4</span></span></p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="es">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Revisión anterior</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revisión del 03:37 23 feb 2010</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l16">Línea 16:</td>
<td colspan="2" class="diff-lineno">Línea 16:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Ejercicio 4 ==</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Ejercicio 4 ==</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Dado un flujo máximo que puede circular por una red donde <math>C_e</math> es la capacidad máxima de la arista ''e'' y <math>F_e</math> es el valor del flujo del arco ''e'', decimos que el arco es ''vital máximo'' si al eliminarlo de la red se produce el máximo decrecimiento del valor del flujo (obtenido eliminando un solo arco). Decir si es V o F y justificar</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Dado un flujo máximo que puede circular por una red donde <math>C_e</math> es la capacidad máxima de la arista ''e'' y <math>F_e</math> es el valor del flujo del arco ''e'', decimos que el arco es ''vital máximo'' si al eliminarlo de la red se produce el máximo decrecimiento del valor del flujo (obtenido eliminando un solo arco). Decir si es V o F y justificar<ins style="font-weight: bold; text-decoration: none;">-</ins></div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">a) Un arco vital máximo es un arco e que tiene valor maximo de <math>C_e</math>.</ins></div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">b) Un arco vital máximo es un arco e que tiene valor maximo de <math>F_e</math>.</ins></div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">c) Un arco vital máximo es un arco e que tiene valor maximo de </math>F_e</math> entre los que pertenecen a un corte mínimo.</ins></div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">a)Un arco vital máximo es un arco e que tiene valor maximo de C_e.</del></div></td><td colspan="2" class="diff-side-added"></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">b)Un arco vital máximo es un arco e que tiene valor maximo de F_e.</del></div></td><td colspan="2" class="diff-side-added"></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">c)Un arco vital máximo es un arco e que tiene valor maximo de F_e entre los que pertenecen a un corte mínimo.</del></div></td><td colspan="2" class="diff-side-added"></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>d) Un arco que no pertenece a un corte de capacidad mínima no puede ser un arco vital máximo.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>d) Un arco que no pertenece a un corte de capacidad mínima no puede ser un arco vital máximo.</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>e)Una red puede contener varios arcos vitales maximos</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>e) Una red puede contener varios arcos vitales maximos<ins style="font-weight: bold; text-decoration: none;">.</ins></div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Ejercicio 5 ==</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Ejercicio 5 ==</div></td></tr>
</table>
200.69.58.171
https://www.cubawiki.com.ar/index.php?title=Final_del_12/02/10_(Algoritmos_III)&diff=7590&oldid=prev
200.69.58.171: Página nueva: == Ejercicio 1 == a) Si el camino entre ''i'' y ''j'' tiene mas de una camino mínimo ¿Cual elige Floyd?. b) Adaptarlo para que calcule los caminos mas cortos tal que no pasen por un...
2010-02-23T03:36:09Z
<p>Página nueva: == Ejercicio 1 == a) Si el camino entre ''i'' y ''j'' tiene mas de una camino mínimo ¿Cual elige Floyd?. b) Adaptarlo para que calcule los caminos mas cortos tal que no pasen por un...</p>
<p><b>Página nueva</b></p><div>== Ejercicio 1 ==<br />
a) Si el camino entre ''i'' y ''j'' tiene mas de una camino mínimo ¿Cual elige Floyd?.<br />
b) Adaptarlo para que calcule los caminos mas cortos tal que no pasen por un conjunto de nodos dado.<br />
<br />
== Ejercicio 2 ==<br />
''G=''(''V,X'') es Hamiltoniano entonces para todo <math>S \in V, S \neq \empty</math> <br />
<br />
<math> W(G-S) \leq |S|</math> (''W''(''G'') es la cantidad de componentes conexas de ''G'')<br />
<br />
a) Dar un ejemplo de que el teorema no es una condición suficiente para asegurar que el grafo es hamiltoniano.<br />
<br />
b) Mostrar, usando el teorema, que el grafo de la figura no es hamiltoniano.(AGREGO EL DIBUJO DESPUES, NO LO TENGO A MANO)<br />
<br />
== Ejercicio 3 ==<br />
Un grafo G es coloreable en forma única si todo coloreo X(G) induce la misma partición de los vértices. Si G es coloreable de forma única entonces el subgrafo inducido por dos conjuntos cualesquiera de la partición inducida por el X(G)-Coloreo es un subgrafo conexo.<br />
<br />
== Ejercicio 4 ==<br />
Dado un flujo máximo que puede circular por una red donde <math>C_e</math> es la capacidad máxima de la arista ''e'' y <math>F_e</math> es el valor del flujo del arco ''e'', decimos que el arco es ''vital máximo'' si al eliminarlo de la red se produce el máximo decrecimiento del valor del flujo (obtenido eliminando un solo arco). Decir si es V o F y justificar<br />
<br />
a)Un arco vital máximo es un arco e que tiene valor maximo de C_e.<br />
b)Un arco vital máximo es un arco e que tiene valor maximo de F_e.<br />
c)Un arco vital máximo es un arco e que tiene valor maximo de F_e entre los que pertenecen a un corte mínimo.<br />
d) Un arco que no pertenece a un corte de capacidad mínima no puede ser un arco vital máximo.<br />
e)Una red puede contener varios arcos vitales maximos<br />
<br />
== Ejercicio 5 ==<br />
a) ¿Que se puede decir de \pi_1 sabiendo que existe una reduccion polinomial de \pi_1 a \pi_2 y que \pi_2 \in P ?<br />
b) ¿Que se puede decir de \pi_1 sabiendo que existe una reduccion polinomial de \pi_1 a \pi_2 y que \pi_2 \in NP ?<br />
c) ¿Que se puede decir de \pi_1 sabiendo que existe una reduccion polinomial de \pi_1 a \pi_2 y que \pi_2 \in NP-Completo ?<br />
d) ¿Que se puede decir de \pi_2 sabiendo que existe una reduccion polinomial de \pi_1 a \pi_2 y que \pi_1 \in NP-Completo ?<br />
e) ¿Que se puede decir de \pi_2 sabiendo que existe una reduccion polinomial de \pi_1 a \pi_2 y que \pi_1 \in NP-Completo y \pi_2 \in NP?</div>
200.69.58.171