Gráficas que vienen de contextos geométricos#
Introducción#
Hay algunas gráficas que vienen de contextos geométricos.
Gráficas de intersección de intervalos#
Definición. Una gráfica de intersección consiste de tomar conjuntos \(X_1, X_2,\ldots, X_n\) y ponerlos como vértices de una gráfica, y luego poner aristas entre dos vértices cuando los conjuntos se intersectan.
Ejemplo. (copiar de Xournal)
Definición. Una gráfica de intersección de intervalos es una gráfica de intersección en donde los conjuntos son intervalos \(I_1,I_2,\ldots,I_n\) de \(\mathbb{R}\).
Ejemplo. (copiar de Xournal)
Proposición. El ciclo con \(4\) vértices no se puede poner como gráfica de intersección de intervalos.
¿Cuáles gráficas sí serán de intersección de intervalos? Dada una gráfica, ¿podremos decir algorítmicamente si es de intersección de intervalos?
Agregar interpretación con pelis
Agregar número de independencia
Agregar número cromático
Gráficas de intersección de discos#
Ejemplo con restaurante de pollos a la penca.
Gráficas de proximidad#
Gráficas de Gabriel#
Tarea moral#
Los siguientes problemas te ayudarán a practicar lo visto en esta entrada. Para resolverlos, necesitarás usar herramientas matemáticas, computacionales o ambas.
Problema
Problema
Problema
Problema
Problema