Antes de mais nada, vamos tentar entender o que é um grafo. Um grafo é uma estrutura matemática usada para representar as relações entre as coisas. Imagine:
Um mapa rodoviário: nele, as cidades se relacionam entre si através das várias estradas.
O relacionamento social entre pessoas: nele, as pessoas se interligam entre si atráves da amizade. Se A é amigo de B e B é amigo de C, indiretamente, A está "conectado" a C. O Twitter é um exemplo de rede social que, no fim das contas, é um grafo. Você possui amigos e está "conectado" a eles. Estes, eventualmente estão conectados a outras pessoas. Já notou quando você entra no perfil de alguém que você não conhece (diretamente) e o Twitter mostra um "caminho" de pessoas, de você até aquela pessoa? Aquilo é um clássico problema de grafos! Devemos partir de uma pessoa (você) e, percorrendo seus relacionamentos, encontrar um "caminho" até outra pessoa.
De acordo os nossos exemplos acima, vamos agora visualizar com será um grafo em uma final de campeonato de futebol, em que ficou acordado entre os times finalistas A e B que, o primeiro que vencer dois jogos consecutivos ou três jogos será campeão.Vamos exibir através de um grafo, como esta decisão pode ocorrer.
1º) Dois jogos: vitórias só de A ou só de B;
2º) Três jogos : A perde o primeiro jogo e ganha o segundo e terceiro ou, B perde o primeiro jogo e ganha o segundo e terceiro;
3º) Quatro jogos: B ganha o segundo e perde os restantes, ou ganha o segundo e perde os restantes;
4º) Cinco jogos : A ganha o primeiro, perde o segundo, ganha o terceiro, perde o quarto e ganha o quinto. O mesmo para B.
Temos também, A ganha o primeiro, perde o segundo, ganha o terceiro, perde o quarto e o quinto. O mesmo ocorre para B.
Note que o grafo facilita o entendimento da solução por leigos, facilitando a preparação dos times para a competição.
