Um gráfico
Os gráficos que você vê na teoria dos gráficos, o estudo dos gráficos, se parecem muito com um jogo de conectar os pontos. No entanto, você nem sempre terá uma boa imagem no final. Em vez disso, você obterá muitos pontos com várias linhas conectando os pontos. E, ao contrário do jogo conecte os pontos, alguns dos pontos podem ter mais de uma linha conectando-os a outros. Os gráficos serão mais ou menos assim:
 |
Este é um exemplo de gráfico simples. Parece um jogo de ligar os pontos, não é? Mas o produto acabado não parece um animal bonito ou um objeto interessante. Parece apenas um monte de pontos com linhas conectando-os. O estudo de como essas linhas conectam os pontos é o objetivo da teoria dos grafos.
Pode parecer chato e sem sentido, mas se você pensar sobre uma cidade, seus muitos cruzamentos e estradas, e então pensar em planejar a melhor rota para ir do ponto A ao ponto B, então você verá como a teoria dos gráficos entra em jogo. A teoria dos grafos permite encontrar a melhor rota, dadas as estradas que conectam os vários cruzamentos. Olhe o gráfico novamente e talvez você consiga ver uma pequena aldeia agora. Os círculos são casas e as linhas são estradas que conectam as casas. Esta é apenas uma aplicação da teoria dos grafos, e existem outras. Mas mostra como a teoria dos grafos é importante. É por isso que existe todo um campo da matemática dedicado a este estudo.
Vértices
Ao se aprofundar na teoria dos grafos, você encontrará alguns termos-chave muito importantes, que abordaremos nesta vídeo-aula. Começamos com os termos relacionados aos nossos vértices , nossos pontos.
Podemos ter vários estilos diferentes de vértices. Podemos ter um vértice isolado , que é um vértice sem linhas conectando-o a outros. Um vértice isolado em um gráfico será por si só. Não terá nenhuma conexão.
 |
O vértice à extrema direita neste gráfico é um vértice isolado. Veja como ele não tem linhas conectando-o a outras pessoas? Parece bastante solitário. Se nosso gráfico representa uma pequena aldeia, então esse vértice isolado pode ser uma casa sem estradas até ele. Você teria que caminhar pelo deserto para chegar até ele.
Outro termo que você provavelmente verá são vértices adjacentes . Isso se refere a vértices conectados que estão próximos um do outro. Por exemplo, olhando para o nosso último gráfico, os dois vértices no topo do nosso gráfico são vértices adjacentes porque estão conectados e próximos um do outro.
Em seguida, temos o grau de um vértice . Isso nos diz quantas linhas estão conectadas ao vértice. Por exemplo, o vértice isolado tem grau 0. O vértice mais à esquerda tem grau 2 porque tem duas retas. O vértice no topo tem grau 3 porque tem três linhas conectando-o a outros. Se nosso grau for par, chamamos o vértice de vértice par . Se o grau for ímpar, então o chamamos de vértice ímpar . Isso é muito fácil de lembrar. Ímpar para um número ímpar de conexões e par para um número par de conexões.
Arestas
Agora, vamos repassar os termos para arestas , nossas linhas. Podemos ter arestas múltiplas se tivermos estradas paralelas entre si ou linhas que conectem os mesmos vértices. Também temos arestas adjacentes , que, como um vértice adjacente, são arestas próximas umas das outras. Olhando para o nosso gráfico, as arestas na extremidade esquerda do gráfico são adjacentes porque estão próximas uma da outra.
Caminhos e outros
Agora que cobrimos os termos para vértices e arestas, vamos falar sobre os termos para outros aspectos de nosso gráfico. Aqui, temos o que é chamado de caminho , uma rota que leva você de um vértice a outro. Por exemplo, podemos querer ir da casa na extrema esquerda, ponto A, até a casa na parte inferior do caminho, ponto B.
 |
As arestas que pegamos e os vértices pelos quais passamos fazem parte do nosso caminho. O número de arestas que pegamos é conhecido como o comprimento do caminho . Então, por exemplo, se começarmos a descer do ponto A e continuarmos pegando as arestas mais baixas, teremos um comprimento de caminho de 3, pois usamos três arestas para ir do ponto A ao ponto B. Se nosso caminho nos levar de um ponto , digamos ponto A, e nos leva de volta ao mesmo ponto A, então chamamos esse caminho de circuito.
 |
Neste exemplo, como todos os nossos vértices estão conectados, podemos chamar isso de grafo conectado . Se tivermos um gráfico que não esteja totalmente conectado, como o mostrado abaixo, teremos um gráfico desconectado . Você pode pensar em um gráfico desconectado como vizinhos ou casas que não estão conectadas a outros vizinhos ou casas. Se você morasse em um bairro, não seria capaz de chegar ao outro bairro, pois não há estradas ligando os dois.
 |
Agora, dê uma olhada neste gráfico:
 |
Este gráfico possui dois componentes ou dois subgráficos. Esses subgráficos são gráficos em si, mas não estão conectados ao resto do gráfico. Se adicionássemos uma conexão como esta, teríamos apenas um gráfico com um componente:
 |
Essa conexão entre os componentes é chamada de ponte . Assim como uma ponte na vida real, se você a quebrasse ou se livrasse dela, não seria capaz de chegar ao outro lado. Na teoria dos grafos, uma ponte é o único caminho que você pode seguir de um componente a outro. Então, é como ter apenas uma ponte do continente para uma ilha. Se a ponte quebrasse, não haveria como chegar à ilha. E aí temos nossos termos-chave importantes.
Resumo da lição
Vamos revisar o que aprendemos. Aprendemos que a teoria dos grafos é o estudo dos grafos. Os vértices são os pontos em nosso gráfico. Um vértice isolado é um vértice sem linhas ou conexões com ele. Os vértices adjacentes são vértices conectados que estão próximos um do outro. O grau de um vértice informa quantas linhas estão conectando este vértice a outros vértices. Se o grau for ímpar, podemos chamar o vértice de vértice ímpar . Se o grau for par, podemos chamá-lo de vértice par .
Nossas bordas são nossas linhas. Arestas múltiplas são linhas que conectam os mesmos vértices. As bordas adjacentes são bordas próximas umas das outras. Um caminho é uma rota de um vértice a outro. O comprimento do caminho é o número de arestas necessárias para ir de um vértice a outro.
Se todos os vértices do gráfico estiverem conectados, então temos um gráfico conectado . Isso significa que temos caminhos que podemos seguir de qualquer ponto do gráfico a qualquer outro ponto do gráfico. Se nem todos os vértices estiverem conectados uns aos outros, então temos um gráfico desconectado . Em um gráfico desconectado, os subgráficos são chamados de componentes . Esses subgráficos são gráficos em si, mas não estão conectados com o resto do gráfico. Uma ponte conecta dois componentes. Retire a ponte e teremos dois componentes separados novamente.
Resultados de Aprendizagem
Após esta lição, você será capaz de:
- Defina a teoria dos grafos
- Identifique os tipos de vértices e arestas usados na teoria dos grafos
- Descreva um caminho e o comprimento do caminho na teoria dos grafos
- Diferencie entre gráficos conectados e desconectados
- Explique quais componentes e uma ponte estão na teoria dos grafos