Teoría de grafos: teoremas y conceptos sobre planaridad, Hamilton y bipartición
Enviado por Chuletator online y clasificado en Matemáticas
Escrito el en
español con un tamaño de 5,21 KB
Ejercicio 1. Verdadero/Falso razonado
a) Si G es un grafo plano con 14 aristas, es regular y tiene un vértice de grado 4, entonces G tiene necesariamente 9 caras.
Respuesta: Cierta.
Por la ley de los emparejamientos de grados (suma de los grados igual a dos veces el número de aristas) se tiene 2|E| = 28. Si G es regular de grado 4, entonces 4n = 28, donde n es el número de vértices. De ello n = 7.
Aplicando el teorema de Euler para grafos planos: n - m + f = 2, donde m = 14 y f es el número de caras. Así, 7 - 14 + f = 2, por lo que f = 9. Por tanto, la afirmación es verdadera.
b) Si n ≥ 3 y K_n es el grafo completo de n vértices, entonces es hamiltoniano siempre y nunca es bipartido.
Respuesta: Cierta.
Si los vértices son v1, v2, …, v_... Continuar leyendo "Teoría de grafos: teoremas y conceptos sobre planaridad, Hamilton y bipartición" »
gallego con un tamaño de 8,72 KB
euskera con un tamaño de 5,81 KB