Introdução

Bem-vindo ao curso Introdução a Grafos Computacionais.

Neste curso, você aprenderá o que é um grafo, como representá-lo e por que eles são tão importantes para a Ciência da Computação.

Um grafo é composto de nós (ou vértices) e arestas. Os nós são conectados por arestas que podem ser direcionadas ou não direcionadas. Na figura abaixo vemos os dois tipos de gráficos.

Quando um grafo é direcionado significa que quando há um caminho entre os nós a não implica necessariamente que há um caminho entre a . Na Figura 1, podemos ver que existe um caminho do nó 3 para o nó 0, mas não existe um caminho na direção oposta.

Os grafos são usados para modelar diferentes situações, pode-se pensar em uma cidade, com diferentes pontos (nós) e suas ruas (arestas) ou uma rede social com diferentes pessoas (nós) e suas conexões (arestas).

Se a Figura 1 fosse uma rede social, por exemplo, a pessoa 3 estaria seguindo a pessoa 0, 2 e 4. A pessoa 4 teria o maior número de seguidores (2 seguidores: pessoa 0 e 3) e a pessoa 5 não teria nenhuma conexão, não está seguindo ou sendo seguida por ninguém.

Outros conceitos importantes de grafos são:

• O grau de um nó é o número de arestas que chegam ou saem do nó. No caso de grafos direcionados, ele pode ser dividido em grau de entrada e grau de saída. O primeiro é o número de arestas que chegam ao nó e o último é o número de arestas que saem dele. Na Figura 1, o nó 4 tem o grau de entrada 2 e grau de saída 1, por exemplo.
• Diz-se que um gráfico é conexo quando há um caminho entre cada par de nós no gráfico. O gráfico da Figura 1 não é conexo, pois a partir do nó 1 não se pode chegar ao nó 0, por exemplo. Enquanto o gráfico da Figura 2 é conexo.