Um dos principais problemas na enumeração de gráfico é determinar a 'forma' de um gráfico, por exemplo, a classe de isomorfismo de qualquer gráfico específico. Estou perfeitamente ciente de que todo gráfico pode ser representado como uma matriz simétrica. No entanto, para obter sua forma, você precisará de uma coleção de permutações de linha / coluna, o que torna uma matriz um pouco menos adequada. Também é um pouco mais difícil 'ver' o gráfico, uma vez que está nessa forma.
Minha pergunta é: Existe alguma álgebra 'gráfica' que possa descrever a 'forma' dos gráficos?
O que estou pensando é em que tipos de sistemas formais os topologistas algébricos tendem a criar. Em particular, coisas como a álgebra para invariantes de nós ou sistemas notacionais, como operadas ou polígrafos . Esse tipo de 'álgebra de doodle' não é tão bem desenvolvido, então talvez haja uma razão para acreditar que essa álgebra não exista para gráficos, mas eu gostaria de perguntar antes de assumir o contrário.
ATUALIZAR:
Minha pergunta provavelmente é muito estreita e não responde imediatamente com um 'sim'; portanto, se os moderadores não se importarem, eu a expandirei perguntando:
Existem sistemas existentes (do tipo que descrevi acima) que poderiam ser adaptados (facilmente ou não) para criar esse sistema? Se houver mais de um, fique à vontade para mencionar todos eles. E jogue os já mencionados também.
Motivação
Minha motivação para essa pergunta é realmente sobre a classificação de gráficos assimétricos. Como sou apenas um graduado, minha análise do estado atual da teoria dos grafos algébricos é bem pequena. Mas ainda tenho muito trabalho para tentar descrever sistematicamente todos os gráficos de maneira algébrica e, em particular, um que use metáforas visuais sobre simbólicas.
Exemplo prático em que esse sistema seria útil
Suponha que se queira descrever uma prova de que todos os gráficos eulerianos devem ter vértices de grau par. Uma prova padrão geralmente usa argumentos sobre graus pares e ímpares, sem mencionar as arestas reais usadas. Um estudante típico encontraria essa prova pela primeira vez e provavelmente começaria a desenhar gráficos, tentando se convencer do argumento. Mas talvez uma ferramenta melhor do que o argumento "lógico" puro, seria mostrar que qualquer coleção de "símbolos" dessa linguagem não poderia satisfazer alguma condição de "completude".
Sim, eu sei, estou acenando com as mãos nesta última parte ... Se não estivesse, provavelmente provavelmente começaria a criar esse sistema!
Mas, ignorando minha imprecisão por um momento, sinto que muitos dos antigos e bem conhecidos teoremas da teoria dos grafos não são difíceis, mas exigem alguma conceituação de que uma estrutura realmente boa poderia 'amarrar' e 'empacotar' em uma visão unificada.
fonte
Respostas:
Muitas pessoas tentaram encontrar uma linguagem algébrica para descrever a forma de um gráfico. Esta questão é essencialmente a que motiva a teoria dos grafos estruturais .
No coração desta área da matemática discreta está o estudo das decomposições de grafos. Algumas das pessoas que trabalham nesta área são Neil Robertson, Paul Seymour, Robin Thomas, Maria Chudnovsky, Kristina Vušković e seus colaboradores, embora essa lista seja influenciada por meus próprios interesses de pesquisa.
Tipos particulares de decomposição de grafos levaram a alguns dos resultados mais gerais da teoria dos grafos. Por exemplo, uma das principais ferramentas técnicas desenvolvidas para o projeto de menores de gráfico, que levou ao teorema de Robertson-Seymour , é o teorema da estrutura de grafos . Isso mostra que classes de gráficos que excluem alguns menores podem ser construídas a partir de gráficos mais simples.
As decomposições estudadas até o momento são, em certo sentido, não algébricas. Minha intuição pessoal é que há indicações de que não existe um sistema "agradável" como o que você procura. Tornar precisa essa afirmação simplificada provavelmente exigiria uma empresa não trivial na teoria dos modelos finitos, mas suspeito que isso também poderia levar a novos resultados interessantes na teoria dos grafos (bem-sucedida ou não).
fonte
Essa questão é importante na programação funcional, pois a representação usual de gráficos é deselegante e ineficiente para uso em linguagens puramente funcionais.
Uma boa abordagem foi apresentada no ICFP no ano passado: "Gráficos Algébricos com Classe (Pérola Funcional)" , de Andrey Mokhov.
Não sei se ele atende totalmente às suas necessidades, mas pode representar algebricamente uma ampla variedade de tipos diferentes de gráficos direcionados e não direcionados.
fonte