Grafos e RedesIntrodução

Todos os dias estamos cercados por inúmeras conexões e redes: estradas e trilhos, linhas telefônicas, a internet, circuitos eletrônicos e até ligações moleculares. Existem também redes sociais entre amigos e familiares. Todos esses sistemas consistem em certos pontos chamados , alguns dos quais são conectados por . Em matemática, isso é chamado de grafo.

Teoria dos grafos é o estudo dos grafos e suas propriedades. É uma das áreas mais emocionantes e visuais da matemática e tem inúmeras aplicações importantes:

Redes rodoviárias e ferroviárias

Circuitos integrados

Redes de fornecimento

Redes de amizades

Conexões neurais

A Internet

Podemos esboçar o layout de grafos simples usando círculos e linhas. A posição dos círculos e o comprimento das linhas são irrelevantes - apenas nos preocupamos com como eles estão conectados entre si. As linhas podem até se cruzar e não precisam ser retas.

Em alguns grafos, as arestas seguem apenas uma direção. Estes são chamados de grafos direcionados.

Alguns grafos consistem em vários segmentos distintos que não são conectados por arestas. Estes grafos estão desconectados.

Outros grafos podem conter várias arestas entre os mesmos pares de vértices, ou vértices conectados a si mesmos (loops).

Para simplificar, neste curso consideraremos apenas grafos não direcionados, conectados, e sem múltiplas arestas e loops.

Podemos criar novos grafos a partir de um grafo existente removendo alguns dos vértices e arestas. O resultado é chamado de subgrafo. Aqui estão alguns exemplos de grafos e subgrafos:

A ordem de um grafo é o número de vértices. O grau de um vértice em um grafo é o número de arestas que se encontram nesse vértice.

Ordem:

Grau:

Os grafos que consistem em um único anel de vértices são chamados de ciclos. Todos os ciclos têm .

Mudar idioma

Entrar no Mathigon

Compartilhar

Redefinir progresso

Glossário

Grafos e RedesIntrodução