Enfoques de resolución de problemas en la teoría de grafos

Question

Por mi experiencia con los problemas de la teoría de grafos, estos plantean ciertos obstáculos que a mí me parecen particulares para la matemática discreta, entre ellos están

1) Una solución puede ser obvia a primera vista, pero extremadamente difícil de formular/probar rigurosamente.

2) El planteamiento de un problema es muy difícil de entender, tanto que no sé ni cómo empezar.

3) Rara vez veo una medida de "progreso hacia una solución"; o no llego a ninguna parte o sé desde el principio cómo resolver un problema/qué teorema utilizar

4) La mayoría de los problemas parecen ser "individuales" en el sentido de que no puedo identificar un concepto general que pueda ser útil para un problema al que me enfrente en el futuro. En particular, eso significa que encontrar pistas demasiado fuertes o incluso soluciones completas no ayuda en absoluto. En otros campos de las matemáticas, incluso copiar una solución bien elaborada podría ayudar, ya que aclara en qué escenario se puede utilizar correctamente un teorema/enfoque.

¿Tienes alguna recomendación sobre cómo averiguar elementos conceptuales en la resolución de problemas de teoría de grafos, es decir, cómo averiguar un escenario y una estrategia general que pueda ser aplicable a un determinado estilo de problemas?

¿Hay alguna buena lectura en teoría de grafos que señale estrategias de resolución de problemas/formas de pensar, en lugar de centrarse en los resultados?

Answer 1

Como solucionador de problemas experimentado me permito recomendarles el libro "Mathematical discovery: on understanding, learning and teaching" de George Polya. En este libro el autor esboza las bases de un método general de resolución de problemas matemáticos. En la teoría de grafos también funciona.

También puedo decirte que cuando tu intuición gráfica esté lo suficientemente desarrollada, a veces "verás" las respuestas. La comprobación y la demostración de las mismas es una tarea técnica. Por eso suelo empezar mis respuestas en MSE con la frase "Parece lo siguiente". :-)

Un par de palabras sobre sus obstáculos parciales.

1) Debes ser lo suficientemente hábil en las técnicas, no sólo en la visión intuitiva.

2) Intentar ver un problema desde diferentes puntos de vista, buscar elementos familiares en el problema. Acércate al problema una y otra vez. Poco a poco tu visión del problema se irá aclarando.

3) Esta visión de "una medida de "progreso hacia una solución"" es algo misterioso para mí. Polya afirma que tal sensación existe, pero parece que no la alberga . Por supuesto, cuando se tiene un programa o un plan del proceso de solución (ver el capítulo respectivo de "Descubrimiento matemático" para más detalles) entonces después de la realización de las fases del plan se puede estimar el progreso, pero este es un caso bastante ideal.

4) Este obstáculo está relacionado con la experiencia. Creo que los miles de problemas matemáticos que resolví o vi las soluciones, formaron mi intuición.

Answer 2

Dejemos que $M$ sea la matriz de incidencia y $A$ la matriz de adyacencia de un grafo $G$ .

a. Demuestre que cada suma de columna de $M$ es $2$ .

b. ¿Cuáles son las sumas de las columnas de $A$ ?