Graus e cortes em grafos

O conjunto dos arcos que saem de um vértice v é o leque de saída (= fan-out) de v. (Esta terminologia não é padrão.) O conceito de leque de entrada é análogo.

Exemplo: No exemplo 1 do capítulo O que é um grafo?, o leque de saída do vértice 6 é { d, e, f }. E o leque de entrada do vértice 0 é { a, d }.

Graus de um vértice

O grau de saída (= out-degree) de um vértice v é o tamanho do leque de saída de v, ou seja, o número de arcos que saem de v. O grau de entrada (= in-degree) de v é o número de arcos que entram em v. Não há notação padrão para esses números, mas podemos denotar o primeiro por gs(v) e o segundo por ge(v). (A letra g nas expressões gs e ge é a inicial de grau e não tem relação com o nome do grafo.)

Um vértice v é um sorvedouro (= sink) se gs(v) ≡ 0 e é uma fonte (= source) se ge(v) ≡ 0. Um vértice v é isolado se for, ao mesmo tempo, uma fonte e um sorvedouro.

Exercícios 1

  1. Calcule os graus de entrada e saída de um vértice a partir da matriz de adjacências do grafo.
  2. Quanto vale v gs(v), ou seja, a soma dos graus de saída de todos os vértices de um grafo? Quanto vale a soma dos graus de entrada?
  3. Digamos que d(v) = gs(v) − ge(v). Quanto vale a soma v d(v) sobre todos os vértices do grafo?
  4. Suponha dados números inteiros não negativos s[0], s[1], … , s[n−1] e e[0], e[1], … , e[n−1]. Problema: Construir um grafo com vértices v[0], v[1], … , v[n−1] tal que gs(v[i]) = s[i] e ge(v[i]) = e[i] para cada i. Esboce um algoritmo que resolva o problema. Repita o problema de modo que o grafo não tenha laços. Repita o problema de modo que o grafo não tenha arcos paralelos. Repita o problema de modo que o grafo não tenha arcos antiparalelos.
  5. Considere o grafo que representa os movimentos de uma dama sobre um tabuleiro de xadrez (cada uma das 64 casas do tabuleiro é um vértice e há um arco de um vértice x a um vértice y se e só se uma dama pode ir de x a y em um só movimento). Quantos arcos tem o grafo?
  6. Um cubo de dimensão k (ou k-cubo) é o grafo definido da seguinte maneira: os vértices do grafo são todas as sequências de k bits; dois vértices são adjacentes se e só se diferem em exatamente um bit. (Por exemplo, os vértices do 3-cubo são 000, 001, 010, 011, 100, 101, 110, 111; o vértice 000 é adjacente aos vértices 001, 010, 100 e a nenhum outro.) Quantas arestas tem o cubo de dimensão k?

Graus de um conjunto de vértices

Digamos que X é um conjunto de vértices de um grafo. Um arco (x, y) sai de X se x está em X e y está fora de X. Reciprocamente, um arco entra em X se x está fora de X e y está em X.

O conjunto de todos os arcos que saem de X é o corte de saída (= fan-out) de X. O tamanho desse conjunto é o grau de saída de X. Vamos denotar esse número por gs(X). O corte de entrada de X e o grau de entrada de X são definidos de maneira análoga.

Um conjunto X de vértices é um sorvedouro se gs(X) ≡ 0 e uma fonte se ge(X) ≡ 0.

Cuidado: os termos fonte e sorvedouro referem-se às vezes a um vértice e outras vezes a um conjunto de vértices; espero que isso não fique confuso.

Exercícios 2

  1. Dado um conjunto X de vértices, qual a relação entre gs(X) e a soma xX gs(x)? Qual a relação entre ge(X) e xX ge(x)?
  2. Suponha que nosso grafo é simétrico e que ge(X) ≡ 0 para um certo conjunto X de vértices. Quanto vale gs(X)?
  3. Seja V o conjunto de todos os vértices de um grafo e X uma parte de V. Mostre que X é uma fonte se e só se VX é um sorvedouro.
  4. Como devemos organizar a matriz de adjacências do grafo para o grau de entrada e o grau de saída de um conjunto X de vértices fique evidente?