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
-
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 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
-
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 X de vértices
fique evidente?