Skip to content

Grafos

Königsberg (hoje Kaliningrado, Rússia) tinha 7 pontes e acreditava-se que era possível passear por toda a cidade atravessando cada ponte exatamente uma vez.

Figura 1: Motivação. Fonte: [1]

Leonhard Euler, em 1736, modelou o problema como um grafo, provou que tal passeio não é possível e fundou a teoria dos grafos.

Definição

Um grafo é um conjunto de objetos ligados, por arestas, entre si, chamados de vértices.

Figura 2: Representação de um Grafo. Fonte:[1]

Essa estrutura pode ser utilizada para a modelagem de problemas envolvendo redes sociais, mapas, páginas na internet, redes de computadores, circuitos eletrônicos, dentre outros.

Matematicamente, um grafo \(G\) é um par ordenado \(\left (V,E\right)\) onde:

  • V é o conjunto dos vértices do grafo;
  • Exemplo: $V={0, 1, 2, 3, 4, 5}
  • E é o conjunto de arestas do grafo;
  • Representamos uma aresta ligando \(u, v\in V\) como \(\{u,v\}\).
  • Pra toda aresta \(\{u,v\}\) tem-se \(u\neq v\);
  • Existe no máximo uma aresta \(\{u, v\} \in E\);
  • \(E=\{\{0,1\}\, \{0, 4\}, \{5, 3\}, \{1, 2\}, \{2, 5\}, \{4, 5\}, \{3, 2\}, \{1, 4\}\}\)

Dizemos que os vértices 0 e 4 são adjacentes, e 0, 1 e 5 formam a vizinhança (conjunto de adjacência) do vértice 4.

Matriz de Adjacências

Um grafo pode ser representado por uma matriz de adjacências.

Se o grafo tem n vértices, teremos vértices numerados de 0 a n-1 e a matriz com dimensão \(n \times n\).

A matriz forma-se da seguinte maneira:

  • adjacencia[u][v] = (u e v vizinhos)? 1 : 0;

Figura 3: Representação do grafo em uma matriz de adjacências. Fonte: [1]

A matriz de adjacência é simétrica, pois \(A_{i,j} = A_{j,i} \forall i, j \in [0, n-1]\).

Ressalvas ao utilizar matrizes: A representação do grafo em matriz gera um desperdício de memória, pois bastaria guardar metade dos valores. Há um alto consumo de memória, a depender do tamanho do n. A matriz guarda as ligações e não ligações entre os vértices, mas poderia guardar apenas as ligações.

Implementação

A estrutura do grafo com matriz de adjacências adj e n vértices é dada por:

grafo.c
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
typedef struct
{
    int **adj;
    int n;
} Grafo;

typedef Grafo *p_grafo;

p_grafo criar_grafo(int n);
void destruir_grafo(p_grafo g);

void insere_aresta(p_grafo g, int u, int v);
void remove_aresta(p_grafo g, int u, int v);
int tem_aresta(p_grafo g, int u, int v);
void imprime_arestas(p_grafo g);

int grau(p_grafo, int a);
int mais_popular(p_grafo g);

void imprime_recomendacoes(p_grafo g, int u);

Inicialização e destruição

criar.c
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
p_grafo criar_grafo(int n)
{
    p_grafo p = malloc(sizeof(Grafo));
    p->n = n;
    p->adj = malloc(n * sizeof(int *));
    for (int i = 0; i < n; i++)
        p->adj[i] = malloc(n * sizeof(int));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            p->adj[i][j] = 0;
    return p;
}
void destruir_grafo(p_grafo g)
{
    for (int i = 0; i < g->n; i++)
        free(g->adj[i]);
    free(g->adj);
    free(g);
}

Manipulando arestas

manipulando_arestas.c
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
void insere_aresta(p_grafo g, int u, int v)
{
    if (u < g->n && v < g->n)
    {
        g->adj[u][v] = 1;
        g->adj[v][u] = 1;
    }
}
void remove_aresta(p_grafo g, int u, int v)
{
    if (u < g->n && v < g->n)
    {
        g->adj[u][v] = 0;
        g->adj[v][u] = 0;
    }
}
int tem_aresta(p_grafo g, int u, int v)
{
    if (u < g->n && v < g->n)
        return g->adj[u][v];
    return -1;
}

Lendo e imprimindo um Grafo

leitura.c
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
p_grafo le_grafo()
{
    p_grafo g;

    int tam, qtd, u, v;
    scanf("%d %d", &tam, &qtd);
    g = criar_grafo(tam);
    for (int i = 0; i < qtd; i++)
    {
        scanf("%d %d", &u, &v);
        insere_aresta(g, u, v);
    }
    return g;
}

void imprime_arestas(p_grafo g)
{
    int u, v;
    for (u = 0; u < g->n; u++)
        for (v = u + 1; v < g->n; v++)
            if (g->adj[u][v])
                printf("{%d, %d}\n", u, v);
}

Grau

O grau de um vértice é a quantidade de arestas que saem dele.

Para calcular o grau de um vértice, basta percorrer a quantidade de 1 na linha (ou coluna) correspondente ao vértice.

grau.c
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int grau(p_grafo g, int u)
{
    int grau = 0;
    for (int i = 0; i < g->n; i++)
        grau += g->adj[u][i];
    return grau;
}

int mais_popular(p_grafo g)
{
    int mais_popular = 0;
    int maior_grau = grau(g, mais_popular);
    int grau_c;
    for (int i = 0; i < g->n; i++)
    {
        grau_c = grau(g, i);
        if (maior_grau < grau_c)
        {
            mais_popular = i;
            maior_grau = grau_c;
        }
    }
    return mais_popular;
}

Recomendações

No contexto das redes sociais, é comum que sejam recomendados amigos para os membros da rede. Por exemplo, podemos sugerir novos amigos para Ana (Figura 2), baseando-nos nas conexões que ela já possui.

Figura 2: Recomendação de amigos. Fonte: [1]

Essa recomendação pode ser feita com o algoritmo a seguir.

recomendacoes.c
1
2
3
4
5
6
7
8
void imprime_recomendacoes(p_grafo g, int u)
{
    for (int i = 0; i < g->n; i++)
        if (tem_aresta(g, u, i))
            for (int j = 0; j < g->n; j++)
                if (tem_aresta(g, i, j) && j != u && !tem_aresta(g, u, j))
                    printf("%d ", j);
}

Grafos Dirigidos

Um grafo dirigido (dígrafo) possui um conjunto de vértices conectados por arcos, que são arestas dirigidas, i. e., arestas que indicam início e fim.

Figura 4: Grafo Dirigidos. Fonte: [1]

Matematicamente, um dígrafo \(G\) é um par \((V,A)\) formado pelos conjuntos de vértices \(V\) e arestas \(A\).

  • Representamos um arco ligando \(u,v\in\ V\) como \((u,v)\), onde \(u\) é a cauda do arco e \(v\) a cabeça.
  • Podemos ter laços da forma \((u,u)\)
  • Existe no máximo um arco \((u,v)\) em \(A\).

Um grafo pode ser visto como um dígrafo se considerarmos cada aresta como dois arcos. A implementação por matriz de adjacências já considera os dois arcos, então nesse caso pode ocorrer: adj[u][v] != adj[v][u], já que adj[u][v] indica um arco de \(u\) para \(v\).

Número de Arestas

Figura 5: Grafo com a quantidade máxima de arestas. Fonte: [1]

Um grafo com \(n\) vértices pode ter no máximo \(\binom{n}{2} = \frac{n(n-1)}{2} = O(n^2)\) arestas. E dizemos que um grafo é esparso quando ele possui bem menos (em outra ordem de grandeza) do que essa quantidade de arestas.

Exemplos de grafos esparsos:

  • Grafos cujos vértices tem o mesmo grau \(d\) constante, possuem \(\frac{nd}{2} = O(n)\) arestas.
  • Grafos com \(O(n\ log\ n)\) arestas.

Listas de Adjacências

Figura 6: Representação do grafo por lista de adjacências. Fonte: [1]

header.c
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
typedef struct No
{
    int v;
    struct No *prox;
} No;

typedef No *p_no;

typedef struct
{
    p_no *adjacencia;
    int n;
} Grafo;

typedef Grafo *p_grafo;
p_grafo criar_grafo(int n);
void destroi_grafo(p_grafo g);

void insere_aresta(p_grafo g, int u, int v);
void remove_aresta(p_grafo g, int u, int v);
int tem_aresta(p_grafo g, int u, int v);

void imprime_arestas(p_grafo g);

Inicialização

inicializacao.c
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
p_grafo criar_grafo(int n)
{
    int i;
    p_grafo g = malloc(sizeof(Grafo));
    g->n = n;
    g->adjacencia = malloc(n * sizeof(p_no));
    for (i = 0; i < n; i++)
        g->adjacencia[i] = NULL;
    return g;
}

void libera_lista(p_no lista)
{
    if (lista != NULL)
    {
        libera_lista(lista->prox);
        free(lista);
    }
}

void destroi_grafo(p_grafo g)
{
    int i;
    for (i = 0; i < g->n; i++)
        libera_lista(g->adjacencia[i]);
    free(g->adjacencia);
    free(g);
}

Manipulação de Arestas

arestas.c
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
p_no insere_na_lista(p_no lista, int v)
{

    p_no novo = malloc(sizeof(No));
    novo->v = v;
    novo->prox = lista;
    return novo;
}

void insere_aresta(p_grafo g, int u, int v)
{
    g->adjacencia[v] = insere_na_lista(g->adjacencia[v], u);
    g->adjacencia[u] = insere_na_lista(g->adjacencia[u], v);
}

p_no remove_da_lista(p_no lista, int v)
{
    p_no proximo;
    if (lista == NULL)
        return NULL;
    else if (lista->v == v)
    {
        proximo = lista->prox;
        free(lista);
        return proximo;
    }
    else
    {
        lista->prox = remove_da_lista(lista->prox, v);
        return lista;
    }
}

void remove_aresta(p_grafo g, int u, int v)
{
    g->adjacencia[u] = remove_da_lista(g->adjacencia[u], v);
    g->adjacencia[v] = remove_da_lista(g->adjacencia[v], u);
}

int tem_aresta(p_grafo g, int u, int v)
{
    p_no t;
    for (t = g->adjacencia[u]; t != NULL; t = t->prox)
        if (t->v == v)
            return 1;
    return 0;
}
void imprime_arestas(p_grafo g)
{
    int u;
    p_no t;
    for (u = 0; u < g->n; u++)
        for (t = g->adjacencia[u]; t != NULL; t = t->prox)
            printf("{%d,%d}\n", u, t->v);
}

Comparação Listas vs Matrizes

Espaço necessário para o armazenamento:

  • Matriz: \(O(n^2)\)
  • Listas: \(O(n + |E|)\)

\(n=|V|\), onde V é o conjunto das arestas (ou arcos).

Comparativo de tempo:

Operação Matriz Listas
Inserir \(O(1)\) \(O(1)\)
Remover \(O(1)\) \(O(d(v))\)
Aresta Existe? \(O(1)\) \(O(d(v))\)
Percorrer Vizinhança \(O(n)\) \(O(d(v))\)

O problema das Pontes de Königsberg

Figura 7: Grafos para o problema das Pontes. Fonte: [1]

A estrutura da Figura 1 é chamada de multigrafo, nela é possível ter arestas paralelas (ou múltiplas), existe um multiconjunto de arestas e pode ser representada por listas de adjacência.

Referências

[1] Grafos (Estrutura) - Notas de aula do professor Rafael C. S. Schouery, disponíveis no link.