Seguidores e Seguidos

Teoria dos Grafos

A teoria dos grafos é um ramo da matemática que estuda as relações entre os objetos de um determinado conjunto. Para tal são empregadas estruturas chamadas de grafos, G(V,E), onde V é um conjunto não vazio de objetos denominados vértices (ou nós) e E (do inglês Edges - arestas) é um subconjunto de pares não ordenados de V.

Dependendo da aplicação, arestas podem ou não ter direção, pode ser permitido ou não arestas ligarem um vértice a ele próprio e vértices e/ou arestas podem ter um peso (numérico) associado. Se as arestas têm uma direção associada (indicada por uma seta na representação gráfica) temos um digrafo (grafo orientado). Um grafo com um único vértice e sem arestas é conhecido como grafo trivial.

Grafo com 4 vértices e 6 arestas (Fonte: Wikipedia).

Matriz de Adjacência

Uma matriz de adjacência é uma das formas de se representar um grafo.

Dado um grafo G com n vértices, podemos representá-lo em uma matriz n x n A(G)=[a_ij] (ou simplesmente A). A definição precisa das entradas da matriz varia de acordo com as propriedades do grafo que se deseja representar, porém de forma geral o valor a_ij guarda informações sobre como os vértices v_i e v_j estão relacionados (isto é, informações sobre a adjacência de v_i e v_j).

Para representar um grafo não direcionado, simples e sem pesos nas arestas, basta que as entradas a_ij da matriz A contenham 1 se v_i e v_j são adjacentes e 0 caso contrário. Se as arestas do grafo tiverem pesos, a_ij pode conter, ao invés de 1 quando houver uma aresta entre v_i e v_j, o peso dessa mesma aresta.

Por exemplo, o grafo e a matriz correspondente (Fonte: Wikipedia).

Uma rede social pode ser representada por um grafo direcionado onde os vértices representam as pessoas e as arestas representam as ligações entre elas. A direção da aresta indica quem segue quem.

O Programa

Escreva um programa que, dado um grafo direcionado representando uma rede social, monte a respectiva matriz de adjacência e calcule:

• quantidade de seguidores das pessoas mais seguidas acompanhada das respecivas pessoas;
• quantidade de seguidores das pessoas menos seguidas acompanhada das respecivas pessoas;
• quantidade de seguidos das pessoas que mais seguem acompanhada das respecivas pessoas;
• quantidade de seguidos das pessoas que menos seguem acompanhada das respecivas pessoas;

e mostre as pessoas que se seguem mutuamente.