Vértices ou nós
São os pontos que representam objetos ou entidades dentro de um grafo. Eles são as "paradas" conectadas por linhas (arestas).
Exemplo: se estiver viajando pelo Brasil, podemos considerar que o estado de chegada e o estado de partida são vértices.
Arestas ou conexões
São as linhas que conectam dois vértices, representando uma relação, caminho ou ligação entre eles. Elas podem ser direcionadas (com sentido) ou não direcionadas.
Exemplo: a estrada que conecta dois locais.
Clique
Um clique é um conjunto de vértices em que todos estão conectados uns aos outros. Em um clique, não há vértices "isolados".
Exemplo: comunidades virtuais, onde os usuários se adicionam e formam conexões entre si.
Valência ou graus de vértices
O grau de um vértice é o número de arestas conectadas a ele. Em grafos direcionados, distinguimos entre grau de entrada (arestas que chegam) e grau de saída (arestas que saem).
Exemplo: em uma plataforma de vídeos, o grau de um vídeo seria o número de links (recomendações) para outros vídeos. Caso o vídeo indique 3 outros vídeos, o grau é 3.
Diâmetro
O diâmetro é a maior distância entre dois vértices em um grafo, medida pelo número mínimo de arestas que você deve atravessar para ir de um vértice ao outro.
Exemplo: em uma rede de entrega de pacotes, o diâmetro seria o número máximo de armazéns pelos quais um pacote precisa passar para chegar ao seu destino.
Pontes
Uma ponte é uma aresta que, se removida, separa o grafo em duas partes distintas, ou seja, desconecta parte dos vértices. Elas são importantes para manter a conectividade do grafo.
Exemplo: ao organizarmos pessoas de dois grupos diferentes, a ponte será a conexão que determinada pessoa tem com alguém de ambos os grupos – se removê-lo, os grupos passam a não ter nada em comum. Na imagem a seguir, a ponte está em vermelho.
Agora é sua vez!
Que tal procurar por outros grafos no seu cotidiano e tentar identificar as propriedades que você acabou de conhecer? Compartilhe suas descobertas com seus colegas!