GRAFOS: Graus e cortes

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.

Graus de um vértice

O grau de saída (= out-degree) de um vértice v é o número de arcos que saem de v, ou seja, o tamanho do leque de saída 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).

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

Calcule os graus de entrada e saída de um vértice a partir da matriz de adjacências do grafo.
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?
Digamos que d(v) = gs(v) – ge(v). Quanto vale a soma ∑_v d(v) sobre todos os vértices do grafo?
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.
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?
Um cubo de dimensão k (ou k-cubo) é o grafo definido da seguinte maneira: os vértices do grafo são todas as seqüências 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. 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

Dado um conjunto X de vértices, qual a relação entre gs(X) e a soma ∑_xεX gs(x) ? Qual a relação entre ge(X) e ∑_xεX ge(x) ?
Suponha que nosso grafo é simétrico e que ge(X) = 0 para um certo conjunto X de vértices. Quanto vale gs(X)?
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 V–X é um sorvedouro.
Como devemos organizar a matriz de adjacências do grafo para o grau de entrada e o grau de saída de um conjunto de vértices fique evidente?