====== Examen Final - 61.07. Matemática Discreta - 17/07/2013 ======

**Cátedra:** Todas\\ 
**Día:** 17/07/2013

===== Enunciado =====

{{:materias:61:07:final_xx_20130717_x.pdf|Enunciado}}

===== Resolución =====

{{:materias:61:07:discreta_2013-07-17_000.jpg?direct&200|}}{{:materias:61:07:discreta_2013-07-17_001.jpg?direct&200|}}
{{:materias:61:07:discreta_2013-07-17_002.jpg?direct&200|}}

====Ejercicio 5====
===b)===

Se tiene un grafo disconexo de <tex>k</tex> componentes (subgrafos conexos) y <tex>n</tex> vértices. La cantidad de aristas se maximiza cuando todas excepto una (k - 1) de las componentes del grafo son vértices aislados (si una de estas componentes tuviese dos vértices, uno de ellos se puede llevar a otra componente con más vértices y generaría más aristas entre estos últimos vértices). La última componente, claramente, sería un grafo K-regular.\\
Entonces se tienen <tex>k-1</tex> vértices aislados y un grafo <tex>(n-k+1)</tex>-regular. Ahora bien, para un grafo genérico k-regular la cantidad de aristas está determinada por\\

<tex>
|A| = \sum_{i=1}^{k-1}i\\
</tex>

Y para el caso, se tiene que

<tex>
|A| = \sum_{i=1}^{n-k+1-1}i = \sum_{i=1}^{n-k}i\\
</tex>

A esta sumatoria le aplicamos Gauss para que finalmente nos quede expresada como

<tex>
(n-k+1) \frac{n-k}{2}
</tex>
■

===== Discusión =====

<note warning>
Si ves algo que te parece incorrecto en la resolución y no te animás a cambiarlo, dejá tu comentario acá.
</note>