Vértices
Arestas
Partes

Um clique
  • Regular
  • Completo

Mais sobre teoria dos grafos

Laboratório de teoria dos grafos

Um grafo é um conjunto de pontos, chamados vértices, unidos por linhas, chamadas arestas. Desenhe um aqui com poucos cliques e o laboratório diz-lhe que tipo de grafo é: quantas partes tem, se é uma árvore, de quantas cores precisa no mínimo, se pode ser desenhado num só traço, e muito mais. Clique numa propriedade para a ver no seu grafo, mude uma aresta e veja as respostas mudarem. Clique num espaço vazio para adicionar um vértice. Clique num vértice e depois noutro para os unir com uma aresta; repita para remover a aresta. Arraste um vértice para o mover. Mude o clique para Apaga e clique num vértice ou numa aresta para o eliminar. Com um vértice selecionado, Delete elimina-o e Esc larga-o. Clique numa propriedade para a ver no grafo. Exemplo carrega um grafo conhecido, Grafo aleatório cria um, Arrumar afasta os vértices uns dos outros e Complemento une exatamente os pares que não estavam unidos. Ctrl+Z desfaz um passo.

Como funciona

  1. Clique num espaço vazio para adicionar um vértice. Clique num vértice e depois noutro para os unir; repita para remover a aresta. Arraste um vértice para o mover.
  2. Leia as propriedades por baixo do grafo e clique numa para a mostrar: uma coloração, os dois lados, um trilho euleriano, uma árvore geradora, o ciclo mais curto ou o diâmetro.
  3. Carregue um exemplo como o grafo de Petersen, crie um grafo aleatório, obtenha o complemento ou mude o clique para Apaga para eliminar vértices e arestas.

O que significam as propriedades

O grau de um vértice é o número de arestas que nele incidem. Um grafo é conexo quando de cada vértice se pode chegar a todos os outros seguindo as arestas, e é uma árvore quando é conexo e não tem ciclos. É bipartido quando os seus vértices se dividem em dois lados e todas as arestas vão de um lado ao outro, o que acontece exatamente quando não tem ciclos de comprimento ímpar. O número cromático é o menor número de cores que permite dar cores diferentes a vértices vizinhos. O comprimento do ciclo mais curto chama-se cintura, e o diâmetro é a maior distância entre dois vértices, contada em arestas.

Desenhar num só traço

Um trilho euleriano usa cada aresta exatamente uma vez. Em 1736, com as sete pontes de Königsberg, Leonhard Euler percebeu qual é o obstáculo: sempre que um trilho passa por um vértice, usa duas das suas arestas. Portanto, ou todos os graus são pares, e o trilho pode terminar onde começou, ou exatamente dois graus são ímpares, e o trilho tem de ir de um desses vértices até ao outro. Mais tarde, Carl Hierholzer provou que isto, com todas as arestas numa só parte, também é suficiente. Carregue o exemplo da casa e descubra onde o traço tem de começar.

Perguntas frequentes

O que é um grafo em teoria dos grafos?

Um conjunto de pontos, chamados vértices ou nós, e linhas entre alguns pares deles, chamadas arestas. Não é o gráfico de uma função: descreve apenas o que está ligado a quê. Mapas de estradas, redes sociais, moléculas e redes de computadores são todos grafos.

Como é calculado o número cromático?

O laboratório tenta colorir o grafo com uma cor, depois com duas, depois com três e assim por diante, e para cada número percorre todas as possibilidades que interessam, colorindo sempre a seguir o vértice cujos vizinhos já usam mais cores. O primeiro número que funciona é o número cromático. Com os grafos que pode desenhar aqui, isso demora no máximo um instante; num grafo muito difícil, a pesquisa para mais cedo e o valor é mostrado como limite superior.

Quando é que um grafo tem um caminho euleriano?

Quando todas as suas arestas estão numa só parte e no máximo dois vértices têm grau ímpar. Sem vértices ímpares, há um circuito euleriano que termina onde começa; com dois, todo o caminho euleriano começa num deles e termina no outro. O número de vértices ímpares é sempre par, por isso nunca é exatamente um.

O que é o complemento de um grafo?

É o grafo com os mesmos vértices cujas arestas são exatamente os pares que antes não estavam unidos. O complemento do complemento é o grafo de partida. O complemento do grafo de Petersen, por exemplo, é 6-regular, porque cada vértice estava unido a 3 dos outros 9.

Porque é que o grafo de Petersen é famoso?

É um grafo pequeno, com 10 vértices e 15 arestas, que serve de contraexemplo a muitas conjeturas otimistas. Todos os vértices têm grau 3, o seu ciclo mais curto tem comprimento 5, quaisquer dois vértices estão no máximo a 2 arestas de distância e não pode ser desenhado sem que as arestas se cruzem. O laboratório começa com ele.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Ir para o editor