search

IIC1253 / IIC1253-2024-1

103 stars 1 forks source link

Pregunta k-coloración #213

Closed solebravo closed 2 months ago

solebravo commented 3 months ago

Hola! estoy haciendo la pregunta de k-coloración del exámen 2022-2 y no entiendo muy bien el primer caso inductivo. Lo que entiendo es que si ninguna arista de v tiene coloración (o significa que ninguna tiene un color c especifico?) , entonces la sacamos del grafo. Puede que este entendiendo mal a lo que se refiere, pero me cuesta cachar la lógica

SmartSelect_20240707_131206_Samsung Notes SmartSelect_20240707_131220_Samsung Notes

PaulaGrune commented 3 months ago

Hola! Se refiere a que si el nuevo vértice ingresado al grafo no tiene ninguna arista adyacente que sea del color c específico, entonces se mantiene que la cantidad de aristas coloreadas con el color c es |V|/2. Como estamos analizando esto para un color c cualquiera, podemos asumir que se cumple para todos los k colores