Al hacer clic en un nodo de un árbol, se activan todas las aristas adyacentes. Calcula el número mínimo de clics para que se activen todas las aristas.
Respuesta
¿Demasiados anuncios?
user299698
Puntos
96
Colorea tu $n$ vértices con dos colores de manera que dos vértices adyacentes cualesquiera tengan colores diferentes (esto es posible porque su gráfico es un árbol, véase gráfico bipartito ). Ahora haz clic en los vértices del color que has utilizado menos entonces todas las aristas se encenderán. Por el principio de caja el número de estos vértices es menor o igual a $\lfloor n/2\rfloor$ .
Tenga en cuenta que para un gráfico de estrellas (que es un árbol), basta con hacer clic en un vértice del centro, pero en general el límite anterior no puede ser menor porque el grafo lineal (que es un árbol) con $n$ los vértices necesitan al menos $\lfloor n/2\rfloor$ clics.
