— Grafos - Uma Breve Definição —
A teoria dos grafos é um assunto antigo com muitas aplicações modernas. As idéias básicas de grafos foram introduzidas no século XVIII , pelo famoso matemático suíço Leonhard Euler. Ele usou grafos para resolver o problema hoje conhecido como As sete pontes de Königsberg.
Grafos são estruturas muito usadas para representar a existência ou não de relações entre elementos de um dado conjunto. Assim, redes de comunicação, fluxos em rede de transporte, análise de redes sociais e relações binárias em geral podem ser representadas por grafos, e nesse caso várias questões de interesse podem ser investigadas. Um grafo é o conjunto não vazio de nós (vértices) e um conjunto de arcos (arestas) tais que cada arco conecta-se a dois nós.
O que interessa num grafo é: Quem são os vértices ?. Que pares de vértices estão ligados e quais não estão ? (isto é, quem são as arestas se houver, pois também pode-se ter um grafo nulo). Existe a possibilidade dos arcos de um grafo comecem em um nó e terminem em outro, neste caso tem-se um grafo direcionado.
De
modo geral um grafo é isso: um conjunto finito de pontos, chamado de vértices
do grafo, e um conjunto finito de arcos, chamado de arestas do grafo. As
extremidades de cada aresta devem ser vértices.
Nas figuras abaixo, temos a repersentação gráfica do problema das sete pontes de Königsberg. O problema consiste em achar um caminho, ao longo do qual um pedestre, partindo de uma das margens ou de qualquer das ilhas percorra todas as pontes, sem passar mais de uma vez por qualquer uma delas. Euler fez a observação fundamental que, para efeito da questão proposta, as margens e as ilhas são como se fossem pontos . As pontes são como arcos que tem esses pontos como extremidades.
Ao realizarmos a contagem,temos as seguintes possibilidades:
A é atingível por 5 pontes - A deve ocorrer 3 vezes;
B é atingível por 3 pontes - B deve ocorrer 2 vezes;
C é atingível por 3 pontes - C deve ocorrer 2 vezes;
D é atingível por 3 pontes - D deve ocorrer 2 vezes;
Mas para atravessar as sete pontes do problema, precisamos de oito letras, ou seja não existe a trilha desejada.
Baseado nesse marco teórico (grafos) , comentarei sobre as medidas de centralidade de uma rede de relacionamentos.
