O que é um grafo: nós, arestas e graus

O que é um grafo

Um grafo é um conjunto de vértices (também chamados de nós) ligados por arestas. Ele não se preocupa com distâncias nem com formas: só importa quem está ligado a quem. Por isso o mesmo grafo pode ser desenhado de muitos jeitos.

Use a figura para criar um grafo. Clique no vazio para criar um vértice, arraste de um vértice até outro para criar uma aresta, arraste um vértice para movê-lo e clique numa aresta para selecioná-la. Duplo clique renomeia um vértice ou muda o peso de uma aresta. A tecla Delete apaga o que estiver selecionado.

Vocabulário

• Grau de um vértice: quantas arestas chegam nele. Um laço (aresta de um vértice a ele mesmo) conta duas vezes.
• Grafo dirigido: as arestas têm sentido (setas). Um vértice tem grau de entrada e grau de saída.
• Grafo ponderado: cada aresta tem um número, o peso (distância, custo, capacidade).
• Conexo: dá para ir de qualquer vértice a qualquer outro seguindo arestas. Um grafo desconexo tem partes separadas, chamadas componentes.
• Caminho: sequência de vértices ligados por arestas, sem repetir vértices.
• Ciclo: caminho que volta ao vértice inicial. Um grafo sem ciclos é uma floresta; se for conexo, é uma árvore.
• Bipartido: dá para separar os vértices em dois grupos de modo que toda aresta ligue grupos diferentes. Um ciclo de comprimento ímpar nunca é bipartido.

Duas contas que valem sempre

Em um grafo não dirigido, a soma dos graus é igual a duas vezes o número de arestas, porque cada aresta tem duas pontas. Por isso o número de vértices de grau ímpar é sempre par.

Num grafo simples com n vértices, o número máximo de arestas é n(n − 1)/2, que é o caso do grafo completo.

Formato de texto

O painel e a URL usam um formato curto: A-B:3 é uma aresta entre A e B com peso 3, A>B é uma seta de A para B, e C sozinho é um vértice isolado. Você pode colar esse texto no campo acima da figura.