Investigación en teoría de grafos versus algoritmos de grafos

Tengo una pregunta muy genérica que hacer. Está relacionado con la investigación. Estoy interesado en la teoría de grafos. He hecho un curso al respecto. He hecho algunos temas relacionados con la teoría de grafos como un punto de vista para hacerlo como estudiante de matemáticas y también estudié algunos algoritmos de grafos. Voy a realizar prácticas de investigación en teoría de grafos. Pero hay un problema en mi mente que no puedo solucionar acerca de mi interés real en los gráficos debido a la falta de ideas distintivas adecuadas sobre la diferencia real en la investigación en algoritmos de gráficos o en la teoría de gráficos como estudiante de matemáticas . Me gustaría saber lo siguiente:

1. ¿Cuál es la verdadera diferencia al hacer teoría de grafos como estudiante de matemáticas o al hacer algoritmos de grafos? ¿Ambos tienen alguna diferencia real?
2. ¿Puede alguien decirme alguna buena fuente para obtener trabajos de investigación sobre teoría de grafos y algoritmos de grafos?
3. ¿Es bueno comenzar a hacer gráficos como estudiante de matemáticas?

No sé si es un lugar adecuado para presentar este tipo de problemas. Por favor, avíseme si no cabe aquí.

Pregunta 1

Diría que las dos áreas definitivamente no son idénticas, sin embargo, hay una gran superposición. En parte, depende de dónde dibujes algunas líneas muy difusas. Empecemos con:

• La teoría de gráficos trata sobre las propiedades de los gráficos como objetos matemáticos
• Los algoritmos gráficos como un área de investigación se trata de resolver problemas computacionales que se representan mediante gráficos.

Por supuesto, la teoría de gráficos es sorprendentemente muy útil en el desarrollo de algoritmos de gráficos, y los algoritmos de gráficos pueden responder preguntas en la teoría de gráficos. De hecho, como obviamente ha notado, muchos problemas en la teoría de grafos se pueden convertir en problemas computacionales y se pueden responder dando un algoritmo (en cierto sentido, este es un aspecto de la correspondencia de Curry-Howard ), por lo que, especialmente a nivel introductorio, existe es poco más que el estilo de presentación que los separa.

Para hacer las cosas aún más confusas, la mayoría de los investigadores en un campo tienen al menos algo de interés y experiencia en el otro, pero hay un par de puntos en los que podemos trazar ciertas líneas de distinción:

• La teoría de grafos (como un campo) se ocupará felizmente de gráficos infinitos, que no son tan interesantes desde una perspectiva algorítmica.
• Los teóricos de gráficos tenderán a estar más interesados ​​en enunciados existenciales ("el número cromático de una clase de gráficos es como máximo bla"), mientras que los algoritmos de gráficos buscarán el mejor algoritmo para resolver un problema ("¿cómo calculamos el valor real del número cromático lo más rápido posible? ").
• Los algoritmos de gráficos incluyen / se superponen con la aplicación y la adaptación de algoritmos de gráficos para resolver problemas que no son realmente gráficos (por ejemplo, desarrollar un buen algoritmo para agrupar redes de interacción de proteínas), en lo que un teórico de gráficos no estaría interesado (al menos como un gráfico teórico).

Pregunta 2

Si tiene acceso a suscripciones universitarias o similares (esto no es exhaustivo):

• Journal of Graph Theory
• Revista SIAM sobre Matemáticas Discretas
• Revista de Teoría Combinatoria: Serie B
• Matemática Aplicada Discreta
• Journal of Graph Algorithms and Applications

Para complicar aún más las cosas, muchos de estos incluyen ejemplos de teoría de gráficos puros y algoritmos de gráficos.

Un par de listas para una mayor exploración:

• Una lista de revistas de teoría de grafos
• Por razones no relacionadas, John Lamp tiene varias listas que tienen revistas interesantes allí, pero tendrá que hacer algunas búsquedas de palabras clave: Matemáticas puras , Matemáticas aplicadas , Informática teórica

Existe el servidor de preimpresión arXiv , que tiene versiones de preimpresión de trabajos de investigación, pero nuevamente, tendrá que pasar una pequeña cantidad de tiempo para explorar y encontrar algo que desee (está más preparado para encontrar un papel que ya sabe que está allí). )

Pregunta 3

Esta pregunta no puede ser respondida objetivamente. Depende completamente de cosas que no tienes forma de saber (es decir, el futuro), y yo no tengo forma de saber (qué tan buena es la gente en tu universidad, qué oportunidades ganarás o perderás al hacer esa pasantía).

Si quieres mi opinión general subjetiva , diría que sí. La teoría de grafos es una parte importante de las matemáticas y la informática (personalmente considero que no son cosas diferentes de todos modos), y la versatilidad y la amplitud de conocimiento son características importantes de un buen investigador, incluso si luego decide que no tiene intención de ser un teórico de gráficos: no le impedirá poder realizar análisis o topologías complejas.

Nuevamente, se trata de si un estudiante arbitrario se beneficiaría de trabajar en gráficos (algoritmos o teoría): usted personalmente puede estar en una situación particular en la que no sería beneficioso, y no podemos responder eso aquí. Por ejemplo, si tomar la pasantía significa que no puedes hacer la pasantía en la Teoría de la categoría que realmente es lo que quieres hacer, entonces esto podría retrasarlo. Al principio de una carrera de investigación, es difícil escapar de un camino en particular, sin volver al paso uno. Más adelante, es más fácil hacer la transición, pero para bien o para mal, hay un período efectivo como el aprendizaje en el que no puedes saltar fácilmente a cualquier trabajo que te interese, pero esa es una pregunta para Academia.SE.