Pesquisa em teoria de grafos versus algoritmos de grafos

Eu tenho uma pergunta muito genérica a fazer. Está relacionado à pesquisa. Estou interessado na teoria dos grafos. Eu fiz um curso nele. Fiz alguns tópicos relacionados à teoria dos grafos como ponto de vista de fazê-lo como estudante de matemática e também estudei alguns algoritmos de grafos. Vou para um estágio de pesquisa em teoria dos grafos. Mas há alguma falha na minha mente que não consigo resolver sobre o meu interesse real em gráficos devido à falta de idéias distintas apropriadas sobre a diferença real em fazer pesquisas em algoritmo de grafos ou em teoria dos grafos como estudante de matemática . Eu gostaria de saber o seguinte:

1. Qual é a diferença real em fazer teoria dos grafos como estudante de matemática ou em algoritmos de grafos? Os dois têm alguma diferença real?
2. Alguém pode me dizer uma boa fonte para obter trabalhos de pesquisa sobre teoria de grafos e algoritmos de grafos.
3. É bom começar a fazer gráficos como estudante de matemática?

Não sei se é o lugar certo para apresentar esse tipo de problema. Por favor, deixe-me saber se não se encaixa aqui.

Questão 1

Eu diria que as duas áreas definitivamente não são idênticas, no entanto, há uma enorme sobreposição. Em parte, depende de onde você desenha algumas linhas muito confusas. Vamos começar com:

• A teoria dos grafos trata das propriedades dos gráficos como objetos matemáticos
• Algoritmos de gráfico como área de pesquisa são sobre a resolução de problemas computacionais representados usando gráficos.

É claro que a teoria dos grafos é surpreendentemente muito útil no desenvolvimento de algoritmos de grafos, e os algoritmos de grafos podem responder perguntas na teoria dos grafos. De fato, como você obviamente percebeu, muitos problemas na Teoria dos Grafos podem ser expressos como problemas computacionais e respondidos com um algoritmo (em certo sentido, esse é um aspecto da Correspondência Curry-Howard ), especialmente no nível introdutório. é pouco mais que o estilo de apresentação que os separa.

Apenas para tornar as coisas ainda mais confusas, a maioria dos pesquisadores em um campo tem pelo menos algum interesse e experiência no outro, mas há alguns pontos em que podemos traçar certas linhas de distinção:

• A teoria dos grafos (como um campo) lidará alegremente com gráficos infinitos, que não são tão interessantes do ponto de vista algorítmico.
• Os teóricos dos grafos tenderão a se interessar mais pelas afirmações existenciais ("o número cromático de uma classe de gráficos é no máximo blá"), enquanto as pessoas com algoritmos gráficos procurarão o melhor algoritmo para resolver um problema ("como calculamos o valor real do número cromático o mais rápido possível? ").
• Os algoritmos de gráfico incluem / se sobrepõem à aplicação e adaptação de algoritmos de gráfico para resolver problemas que não são realmente sobre gráficos (por exemplo, desenvolver um bom algoritmo para agrupar redes de interação de proteínas), nos quais um teórico gráfico não estaria interessado (pelo menos como um gráfico) teórico).

Questão 2

Se você tiver acesso a inscrições em universidades ou similares (isso não é exaustivo):

• Revista de Teoria dos Grafos
• Revista SIAM de Matemática Discreta
• Revista de Teoria Combinatória: Série B
• Matemática Aplicada Discreta
• Journal of Graph Algorithms and Applications

Para coisas mais confusas, muitas delas incluem exemplos de teoria pura de grafos e algoritmos de grafos.

Algumas listas para exploração adicional:

• Uma lista de revistas de teoria de grafos
• Por razões não relacionadas, John Lamp tem várias listas que têm diários interessantes, mas você precisará pesquisar algumas palavras-chave: Matemática Pura , Matemática Aplicada , Ciência da Computação Teórica

Existe o servidor de pré-impressão arXiv , que possui versões pré-impressas de trabalhos de pesquisa, mas, novamente, você precisará gastar um pouco de tempo para explorar e encontrar o que deseja (é mais configurado para encontrar um artigo que você já sabe que existe) )

Questão 3

Esta questão não pode realmente ser respondida objetivamente. Depende inteiramente de coisas que você não tem como saber (ou seja, o futuro), e eu não tenho como saber (quão boas as pessoas são na sua universidade, que oportunidades você ganhará ou perderá ao fazer esse estágio).

Se você quer minha opinião geral subjetiva , eu diria que sim. A teoria dos grafos é uma parte importante da matemática e da ciência da computação (eu pessoalmente afirmo que não são coisas diferentes de qualquer maneira), e a versatilidade e a amplitude do conhecimento são características importantes de um bom pesquisador, mesmo que mais tarde você decida que não tem intenção de ser um teórico dos grafos - isso não impedirá que você faça análises ou topologias complexas.

Novamente, é sobre se um aluno arbitrário se beneficiaria de trabalhar em gráficos (algoritmos ou teoria) - você pode estar pessoalmente em uma situação específica em que isso não seria benéfico, e não podemos responder aqui. Por exemplo, se fazer o estágio significa que você não consegue fazer o estágio na Teoria da Categoria que é realmente o que você quer fazer, então isso pode atrasá-lo. No início de uma carreira de pesquisa, é difícil escapar de um caminho específico, sem voltar ao primeiro passo. Mais tarde, é mais fácil fazer a transição, mas, para o bem ou para o mal, há um período efetivamente como o aprendizado, no qual você não pode saltar facilmente para qualquer trabalho em que esteja interessado, mas essa é uma pergunta para a Academia.SE.