MD1-1S: Ejercicio 8, práctico 9.

Buenas noches,

Pensé este ejercicio dibujando el grafo y llegue a la conclusión de que solo hay un grafo conexo, sin incluir a los vértices 1, 11 y 13, los cuales son vértices aislados, los cuales conté cada una como una componente conexa distinta. Lo que daría como resultado 4.

¿Este razonamiento es correcto? ¿Está bien tomada la condición para los vértices aislados?

Muchas gracias,

Saludos.

Re: Ejercicio 8, práctico 9.

de Claudio Qureshi - sábado, 6 de junio de 2020, 14:47

Hola Julieta. Tu razonamiento es correcto, hay cuatro componentes conexas (los vértices aislados siempre son componentes conexas). Como hay 3 vértices aislados (1,11 y 13) te queda ver que el grafo inducido por los restantes vértices resulta conexo. Una forma es haciendo el dibujo como lo hicistes tú. Otra forma más analítica sería considerando por ejemplo la componente conexa del vértice 2, llamémosla K. Como los pares mayores que 2 son adyacentes al vértice 2 entonces todos los pares estarán en K. Como v está conectado con 2v para v=3,5 y 7 (y 2v está en K pues es par) entonces los vértices 3,5 y 7 también están en K. El 9 es adyacente al 3 y este último sabemos que está en K, asi que 9 está en K. El 15 es adyacente al 5 y este último sabemos que está en K, asi que 5 está en K. Saludos.