O que é a Teoria dos Grafos e como um grafo é definido como tal?

Em 1736, com base no trabalho do físico-matemático suíço Leonhard Euler (1707-1783), observou-se que uma sucessão de vértices define um caminho, no entanto, se o referido caminho consiste em diferentes vértices sem repetição de arestas, é chamado de caminho ou caminho euleriano; se, adicionalmente, chegarmos ao ponto de partida, percorrendo cada aresta apenas uma vez, teremos um ciclo (circuito) euleriano.

Cotação (APA)

alexander barraza | Julho 2022
Graduação em física

Por sua vez, definimos um grafo como um par ordenado (VAI) Onde v designa o conjunto (não vazio) de todos os vértices ou nós de um grafo, enquanto UMA designa o conjunto (pode ser vazio) de todas as arestas ou linhas que unem os vértices de um grafo. Os elementos do conjunto UMA pode ser designado como um par não ordenado {v, w} onde v e w são elementos (nós ou vértices) de v, desta forma diz-se então que v e w são vértices adjacentes (são ligados por uma aresta).

A teoria dos grafos surge da resposta dada por Euler a um problema de engenho popular que questionava como atravessar as sete pontes que juntou duas ilhas da comunidade de Königsberg (parte da Alemanha na época, e atualmente Kaliningrado, na Rússia), entre elas e com o continente sem usar dois vezes a mesma ponte e chegando ao ponto de partida (localizado no continente) seja ele qual for, determinando que neste caso, em última instância, não poderia.

O problema das sete pontes de Königsberg

Euler modelou Königsberg como um gráfico onde cada ponto (vértice ou nó) representa uma ponte e cada linha (borda) um caminho em terra:

Qual é a solução para este problema?

não há um solução que atende às condições impostas, pois, como mostrou Euler, os vértices não são de grau par, ou seja, um número par de linhas não afeta cada ponto _[3]. Não parece que podemos fazer muito com uma estrutura definida tão simplesmente como esta, no entanto, como é frequentemente o caso em matemática, Às vezes as coisas não são o que parecem. Assim, uma das áreas mais prolíficas, transversais e interdisciplinares _[4] do conhecimento humano, teoria dos grafos.

Gráficos eulerianos ou com trajetória euleriana?

Todos os grafos a seguir têm caminhos eulerianos _[5]. Todos eles têm ciclos eulerianos?

Vamos ao terceiro gráfico:

Vamos numerar os vértices:

Vemos então que o caminho definido pela sequência {3,4,6,2,1,3,7,6,5,4,2} é um caminho euleriano, pois ele percorre todo o grafo sem repetir arestas, mas não é um ciclo euleriano, pois não atinge o ponto de partida. O que teria acontecido se numerássemos os vértices de forma diferente? Não muito, exceto que agora o caminho seria definido por uma sucessão diferente. O que teria acontecido se tivéssemos seguido caminhos diferentes do proposto em nossa solução inicial? Essa pergunta é um pouco mais complexa de responder e envolve algoritmos com os quais os engenheiros de software geralmente ficam satisfeitos. programação.

Para uma prova mais rigorosa do que é exposto aqui temos que nos referir ao seguinte resultado:

"Ser G um gráfico conectado _[6]. Então sim G tem um o circuito Euler, o grau de cada vértice é par, enquanto se G tem um caminho de Euler, G tem exatamente dois vértices de grau ímpar _[7] (exatamente os vértices onde o caminho começa e termina)".

Podemos então verificar que, de fato, no grafo que tomamos, apenas os vértices 3 e 6 têm grau ímpar (este ocorreria mesmo que a numeração dos vértices fosse diferente), portanto o referido grafo tem um caminho euleriano _[8]. Para os restantes grafos podemos proceder de forma análoga e verificar se de facto têm caminhos e Ciclos eulerianos, ou dito de outra forma, podemos desenhar esses gráficos sem pegar o lápis e repetir linhas? A resposta a esta questão pode ser deduzida do que já foi explicado até agora, no entanto, constitui um exercício interessante em termos de motricidade fina, engenhosidade e paciência, convido o leitor a encontrar e desenhar gráficos de 6 ou mais vértices com trajetória Euleriano.

Existem outros tipos de gráficos? A teoria dos grafos tem aplicações no mundo 'real'?

Esses gráficos que revisamos muito brevemente são apenas um dos muitos tipos de gráficos que encontramos na teoria dos grafos. Também podemos encontrar grafos como árvores, muito representativos em conjuntos onde seus elementos podem ser classificados em hierarquias e em cálculos de contagem e probabilidade_[9], dígrafos, gráficos hamiltonianos _[10], etc

Imagem de Modelos Gráficos e Redes em Psycho., de Ruiz, Ana María.

Esses enigmas, se quisermos chamá-los assim, têm enorme aplicabilidade no mundo atual, em situações tão diversas como: biologia molecular _[11], Informática_[12], telecomunicações _[13] e analise de rede _[14]. Vale perguntar então: não é pelo menos curioso que um problema de ordem quase banal acabará sendo um dos resultados mais interessantes e conspícuos da matemática? Talvez, para isso, fosse necessária a contribuição de uma das mentes mais ilustres da humanidade.