Introdução à Teoria dos Grafos - Aula 1 - O que é um grafo?

Introdução à Teoria dos Grafos

Contexto e Importância

• A aula aborda uma parte da matemática pouco vista nas escolas, mas que é útil para modelar situações complexas.

• O foco da aula é a teoria dos grafos, que permite simplificar problemas através de representações gráficas.

Problema das Pontes de Königsberg

• Introduz-se o famoso problema das pontes de Königsberg, onde se questiona se é possível atravessar as sete pontes sem passar duas vezes pela mesma.

• Um esquema da cidade é apresentado, mostrando as margens do rio e as ilhotas conectadas por pontes.

Abstração e Representação

• A abstração dos elementos do problema (cidades e pontes) ajuda a encontrar soluções ou demonstrar impossibilidades.

• Um segundo problema é introduzido: em um grupo de pessoas, sempre há duas com o mesmo número de amigos.

Conexão entre os Problemas

• Apesar das diferenças aparentes entre os problemas, ambos podem ser representados na teoria dos grafos.

• Elementos são representados como vértices (pontos), enquanto relações são representadas como arestas (linhas).

Construindo o Grafo

• Cada região ligada por pontes no primeiro problema será um vértice; as ligações serão arestas.

• Exemplo prático: ao representar pessoas como vértices e suas amizades como arestas, a estrutura gráfica se torna mais clara.

Simplificação do Problema

• A representação gráfica reduz a complexidade visual do problema original, facilitando a análise.

Introdução aos Grafos e Problemas de Conexão

Conceitos Básicos sobre Grafos

• O primeiro problema discutido envolve a conexão entre duas partes de uma cidade através de pontes, representando um grafo onde as cidades são vértices e as pontes são arestas.

• A relação entre pessoas é comparada à amizade: se a pessoa 1 é amiga da pessoa 2, existe uma única ligação (aresta) entre elas. Se não houver amizade, não há ligação.

• Em situações onde apenas uma ligação existe entre dois vértices ou nenhuma, estamos lidando com um "grafo simples", que será o foco inicial do estudo.

Tipos de Grafos

• Quando existem múltiplas ligações (arestas) entre os mesmos vértices, como no caso das pontes, isso caracteriza um "multigrafo", útil para representar essas situações complexas.

• Um exemplo adicional apresentado é a possibilidade de conectar uma cidade a ela mesma por meio de uma ponte, ilustrando a ideia de laços em grafos.

Laços e Representação Gráfica

• A representação gráfica de um laço ocorre quando um vértice está ligado a ele mesmo. Essa configuração pode ser relevante para problemas futuros na teoria dos grafos.

• Embora o conceito de laço tenha sido introduzido, o foco atual permanece nos grafos simples e multigrafos.

Encerramento e Expectativas Futuras