Hola a todos! Debo demostrar la siguiente propiedad y no sé cómo
:
Propiedad: Sea \( G = (V, A, \varphi) \) grafo: \( G \) es bosque de \( k \) componentes conexas \( \Rightarrow{} \textrm{#}V = \textrm{#}A + k \).
Notación: \( \textrm{#}V \) indica cantidad de elementos de \( V \).
Recuerdo algunas definiciones:
Def. 1) Sea \( G = (V, A, \varphi) \) grafo. Se define \( R \subset{} V\times{}V \). Sean \( v, w \in{} R \): \( vRw \Leftrightarrow{} (\textrm{existe un camino entre } v \textrm{ y } w) \vee v=w \).
Propiedad de 1) Se prueba que \( R \) es una relación de equivalencia. Cada clase de equivalencia se llama
componente conexa (\( R \) se llama relación de conexión).
Por ejemplo, ¿cuántas componentes conexas hay en el siguiente dibujo?
Respuesta: Hay 2 componentes conexas.
Def. 2) Sea \( G = (V, A, \varphi) \) grafo. \( G \) es un
árbol \( \Leftrightarrow{} G \) es conexo \( \wedge \; G \) no tiene ciclos.
Def. 3) Sea \( G = (V, A, \varphi) \) grafo. \( G \) es
bosque si toda componente conexa es un árbol.
Ejemplo de bosque:
También hay una propiedad que para cada componente conexa se tiene que \( \textrm{#}V = \textrm{#}A + 1 \).
¿Cómo demuestro la primera propiedad? Supongo que deberemos hacer algo con la última propiedad mencionada, siempre en cada componente conexa la cantidad de vértices es la cantidad de aristas más uno, y además \( \displaystyle\sum_{v \in{} V}{}g(v) = 2 \; \textrm{#}A \) (\( g(v) \) indica el grado o valencia de un vértice \( v \))...
Gracias!!
