Ejercicios:
1) Valerse del Capíulo 6 de Biggs. Comparar el resultado obtenido con el que figura en mi Monografía de Matemática (carpeta Clase1 - confiabilidad).
2) Seguir la lógica de la prueba que el cómputo de DCR es lineal en árboles. Probar que con dos aplicaciones de BFS se logra el diámetro.
3) Ver página 263 del libro Random Graphs de Béla BolloBás
4) Mostrar un algoritmo que opera en una cantidad polinomial de operaciones, y permite hallar un corte no trivial (que no sea toda la palabra de ceros). Es posible encontrar un algoritmo polinomial para encontrar un corte de mínimo cardinal? Si es posible, construirlo. En caso contrario, probar que es NP-Hard el cómputo de corte de mínimo cardinal en un SBS arbitrario.
5) Sabemos ya que la respuesta es afirmativa. Mostrar cómo opera Monte Carlo Crudo (media muestral) en un Sistema Binario Estocástico cualquiera.
6) Leer el artículo de RVR sugerido. Analizar si es necesario agregar coherencia en el Sistema Binario Estocástico para asegurar terminación de la recursión. En caso afirmativo, definir RVR en un Sistema Binario Estocástico coherente.
7) Mostrar primero que m-n-c es siempre mayor que, o igual a -2.
Luego, expresar el polinomio confiabilidad cuando m-n-c es negativo o cero.
Finalmente, señalar grafos que verifican m-n-c<0. Hemos visto varios en clase (árboles, ciclos, Monma). Calcular la confiabilidad all-terminal de estos y otros
8) En el artículo de Cancela & Petingi se captura la complejidad del cálculo de la DCR con dos terminales o más, basándose en la intratabilidad del conteo de cubrimiento de bipartitos. La lógica de esta prueba es una pista para estudiar este problema.
9) Repasar grafos débiles y de co-rango finito.
10) Idem al punto (9). El ejemplo del bipartito completo dado en clase es débil pero no tiene co-rango finito. No sirve como evidencia para este problema porque es crítico (es decir, tras eliminar una arista cualquiera deja de ser d-K-conexo).
Les recuerdo que el documento debe hacerse en latex, prolijo, con algoritmos desarrollados en paquete algorithmic o similar, incluyendo referencias cuando crean conveniente.
Una fuerte recomendación es valerse de la modalidad de "pre-entrega", para tener una devolución previa a la entrega final. También pueden aprovechar el foro, y me pueden hacer llegar consultas cuando crean conveniente.
¡Fuerza, y ojalá que resuelvan todos los problemas y se enganchen a armar algún artículo conjunto! :)
Abrazos,
Pablo.