Buenas, que tal? Tengo una duda sobre este ejercicio. Entiendo bien que separa la resolución en tres casos distintos, pero lo que no me queda claro es por qué al momento de contar los caminos que hay entre dos vértices, considerando que sus extremos pertenecen a V1 y V2, multiplica el resultado por 2? Ya que al pensar en un subgrafo de G, no importa el sentido en el cual recorra el camino.
Hola Alberto. Cuidado, el x2 que mencionás no es por el sentido que se recorre el camino tiene más que ver con la estructura del grafo.
Primero te recomiendo que hagas un dibujo del grafo, dibujá un C4 (con vértices 3, 2', 1, 2 en sentido antihorario ; donde el 3 lo colocás más abajo por ejemplo). Al vértice 3 le cuelga un P7 (con vértices 3,4,5,6,7,8,9).
Luego separa los vértices en 2 tipos V1={2', 1, 2} y V2= {3,4,5,6,7,8,9}.
Como P7 es un árbol, entre cada par de vértices existe dos caminos simples entre ellos (uno de ida y otro de vuelta) pero como estamos considerando subgrafos debemos contarlos como uno, por eso obtiene C(7,2)=21.
Para subgrafos con un extremo en V1 y el otro en V2 fijate bien que como los vértices de V1 forman parte del C4 entonces existen dos formas de llegar al vértice 3 (una recorriendo en sentido horario y la otra en antihorario), luego una única forma de llegar del vértice 3 a cualquier otro vértice de V1. Esa es la razón de la multiplicación por 2.
Por ejemplo subgrafos isomorfos a un camino simple con extremos 2' y 5 tenemos 2 posibilidades:
Recorriendo el C4 en sentido horario: 2' - 3- 4- 5
Recorriendo el C4 en sentido antihorario: 2'-1- 2- 3- 4- 5
Que corresponde a dos subgrafos distintos (involucran diferentes vértices)
Lo mismo ocurre tomando cualquier par de vértices con extremos en V1 y el otro en V2, van a haber dos posibles subgrafos isomorfos a un Pn con esos extremos (que surge de elegir sentido horario o antihorario para recorrer el C4), por eso dice que el total es 2x|V1|x|V2|.
Saludos,
Claudio.