Fundamentos em Teoria da ComputaЗ╞o
303 pág.

Fundamentos em Teoria da ComputaЗ╞o


DisciplinaFundamentos de Teoria da Computação140 materiais530 seguidores
Pré-visualização50 páginas
e
arestas. Existem dois tipos ba´sicos de grafos: os dirigidos e os na\u2dco dirigidos. Nos grafos
dirigidos as arestas (dirigidas) sa\u2dco pares ordenados de ve´rtices, e nos grafos na\u2dco dirigidos
as arestas (na\u2dco dirigidas) sa\u2dco pares na\u2dco ordenados de ve´rtices.
Na representac¸a\u2dco gra´fica de um grafo, um ve´rtice e´, em geral, representado por meio
de uma curva fechada, como um c´\u131rculo, uma oval, etc. Em um grafo dirigido, uma aresta
e´ representada por meio de uma seta ligando as representac¸o\u2dces dos dois ve´rtices da aresta
no sentido do primeiro para o segundo ve´rtice. E em um grafo na\u2dco dirigido, uma aresta
e´ representada por meio de uma linha (reta ou curva) ligando as representac¸o\u2dces dos dois
ve´rtices da aresta. As Figuras 1.8(a) e (b) mostram exemplos de representac¸o\u2dces gra´ficas
de um grafo dirigido e de um grafo na\u2dco dirigido. No grafo na\u2dco dirigido da Figura 1.8(b)
existe uma aresta conectando dois ve´rtices v e v\u2032 se, e somente se, o pa´\u131s v tem fronteira
com o pa´\u131s v\u2032.
Sintetizando, um grafo e´ um par G = (V,A), onde V e´ um conjunto de ve´rtices e A e´
um conjunto de arestas. Se G e´ dirigido, A e´ um conjunto de pares ordenados de elemen-
tos de V ; e se G na\u2dco e´ dirigido, A e´ um conjunto de pares na\u2dco ordenados de elementos de
V . Assim, o grafo dirigido da Figura 1.8(a) e´ um par (V,A), onde V = {A,B,C,D,E,F}
e A = {(B,B), (B,C), (B,D), (C,D), (D,E), (D,F), (E,C), (E,F), (F,D)}. E o
grafo na\u2dco dirigido da Figura 1.8(b) e´ um par (V \u2032, A\u2032), onde V \u2032 = {Argentina, Bol´\u131via,
Brasil, Chile, Paraguai, Uruguai} e A\u2032 = {{Argentina,Bol´\u131via}, {Argentina,Brasil},
{Argentina,Chile}, {Argentina,Paraguai}, {Argentina,Uruguai}, {Bol´\u131via,Brasil}, {Bol´\u131via,Chile},
{Bol´\u131via,Paraguai}, {Brasil,Paraguai}, {Brasil,Uruguai}}.
Ale´m dos dois tipos ba´sicos de grafos exemplificados acima, existem variac¸o\u2dces. Por
exemplo, existem os grafos mistos, que te\u2c6m ambos os tipos de arestas, dirigidas e na\u2dco
32
\ufffd
\ufffd	a -9 -4 \ufffd
\ufffd	b
\ufffd\ufffd
?
3
?
6
\ufffd
\ufffd	d
6
7
\ufffd
\ufffd	e\ufb00 8 -7 -5 \ufffd
\ufffd	f
\ufffd
\ufffd	c
Figura 1.9: Exemplo de grafo dirigido rotulado.
dirigidas. Em alguns contextos, os grafos conte\u2c6m, na\u2dco um conjunto de arestas, mas um
multi-conjunto25. Neste u´ltimo caso, podem existir va´rias arestas para um u´nico par de
ve´rtices.
Um grafo dirigido rotulado e´ uma tripla (V,A,R) em que:
\u2022 V e´ um conjunto finito de ve´rtices;
\u2022 A \u2286 V ×R × V e´ um conjunto arestas (rotuladas); e
\u2022 R e´ um conjunto de ro´tulos.
A representac¸a\u2dco gra´fica e´ similar a` de um grafo na\u2dco rotulado. A diferenc¸a e´ que, para
uma aresta (a, r, b), coloca-se, ale´m da seta de a para b, o ro´tulo r adjacente a` seta, como
mostra o exemplo a seguir. Observe que agora podem existir va´rias arestas que saem do
mesmo ve´rtice e entram em um ve´rtice comum; basta que seus ro´tulos sejam diferentes.
Um grafo na\u2dco dirigido rotulado pode ser definido de forma ana´loga.
Exemplo 38 A Figura 1.9 da´ a representac¸a\u2dco gra´fica de um grafo rotulado (V,A,N) tal
que:
\u2022 V = {a, b, c, d, e, f};
\u2022 A = {(a, 9, b), (a, 4, b), (b, 3, b), (b, 6, e), (d, 7, a), (d, 7, e), (e, 8, d), (e, 5, f)}.
Os ve´rtices de uma aresta sa\u2dco ditos adjacentes . Para uma aresta x = (a, b), em um
grafo dirigido na\u2dco rotulado, ou x = (a, r, b), em um grafo dirigido rotulado, diz-se que
x sai do ve´rtice a e entra em b, e tambe´m que a aresta x e´ uma aresta de a para b. O
grau de um ve´rtice e´ o nu´mero de arestas que o conte\u2c6m. Em um grafo dirigido, o grau
de entrada de um ve´rtice e´ o nu´mero de arestas que entram nele, e o grau de sa´\u131da e´ o
nu´mero de arestas que saem dele.
Exemplo 39 Para o grafo da Figura 1.8(a), os graus de entrada e de sa´\u131da de A sa\u2dco
zero; o grau de entrada de B e´ 1 e o de sa´\u131da de B e´ 3, sendo 4 o grau de B. No grafo
da Figura 1.9, o grau de entrada de b e´ 3 e o grau de sa´\u131da e´ 2, sendo 5 o grau de b. Na
Figura 1.8(b), o ve´rtice Brasil tem grau 4.
25Um multi-conjunto e´ um conjunto que admite repetic¸o\u2dces de elementos. Assim, por exemplo, {a} 6=
{a, a}.
33
Um caminho de tamanho n de a para b, em um grafo dirigido, e´ uma sequ¨e\u2c6ncia de
ve´rtices e arestas v0x1v1x2v2 . . . vn\u22121xnvn tal que a = v0, b = vn e a aresta xi sai de vi\u22121
e entra em vi; v0 e´ o ve´rtice inicial e vn e´ o ve´rtice final do caminho. Neste caso, diz-se
ainda que o caminho passa pelos ve´rtices v0, v1, etc., e pelas arestas x1, x2, etc. Se o
grafo na\u2dco e´ rotulado, pode-se representar um caminho usando-se apenas os ve´rtices, na
forma v0v1v2 . . . vn\u22121vn, assumindo-se que ha´ uma aresta de um ve´rtice de vi para vi+1
para 0 \u2264 i \u2264 n \u2212 1. Quando n = 0, o caminho consta apenas do ve´rtice v0 = a = b,
e e´ dito ser um caminho nulo. Um caminho fechado e´ um caminho na\u2dco nulo em que os
ve´rtices inicial e final sa\u2dco o mesmo, isto e´, v0 = vn. Um ciclo e´ um caminho fechado em
que vi 6= vj para todo 0 \u2264 i < j \u2264 n, exceto para i = 0 e j = n, e em que cada aresta
na\u2dco ocorre mais de uma vez. Um ciclo de tamanho 1 e´ denominado lac¸o. Um caminho
simples e´ um caminho sem ve´rtices repetidos. Define-se caminho, caminho nulo, caminho
fechado, ciclo, lac¸o e caminho simples para grafos na\u2dco dirigidos de forma ana´loga.
Exemplo 40 Seja o grafo da Figura 1.9. Sa\u2dco exemplos de caminhos:
\u2022 a: e´ caminho nulo e e´ caminho simples;
\u2022 a(a, 4, b)b(b, 3, b)b: e´ um caminho de tamanho 2;
\u2022 b(b, 3, b)b: e´ um ciclo de tamanho 1 e, portanto, um lac¸o;
\u2022 a(a, 9, b)b(b, 6, e)e(e, 8, d)d(d, 7, a)a: e´ um ciclo de tamanho 4;
\u2022 d(d, 7, e)e(e, 8, d)d(d, 7, e)e(e, 8, d)d: e´ um caminho fechado de tamanho 4; na\u2dco e´
ciclo.
No grafo da Figura 1.8(b), Brasil Paraguai Argentina Chile e´ um caminho simples de
tamanho 3; Brasil Bol´\u131via Brasil e´ um caminho fechado, mas na\u2dco e´ ciclo. Brasil Bol´\u131via
Argentina Brasil e´ um ciclo.
Note que o tamanho de um caminho e´ o nu´mero arestas do mesmo, que e´ igual ao
nu´mero ve´rtices menos um.
Um grafo que na\u2dco tem ciclos e´ dito ser um grafo ac´\u131clico.
Um grafo na\u2dco dirigido e´ dito conexo se existe caminho de qualquer ve´rtice a qualquer
outro. E um grafo dirigido em que existe caminho de qualquer ve´rtice a qualquer outro
e´ dito ser fortemente conexo. Assim, os grafos das Figura 1.8a e 1.9 na\u2dco sa\u2dco fortemente
conexos, e o da Figura 1.8b e´ conexo.
Um tipo de grafo muito comum em computac¸a\u2dco e´ a a´rvore. Uma a´rvore pode ser
definida como sendo um grafo ac´\u131clico conexo. Na maioria das aplicac¸o\u2dces, existe um
ve´rtice especial denominado raiz . Supondo que os ve´rtices sa\u2dco tomados de um universo
U , pode-se definir recursivamente a´rvore como sendo uma tripla (V,A, r) tal que:
(a) ({v}, \u2205, v) e´ uma a´rvore para qualquer v \u2208 U ;
(b) se (V,A, r) e´ uma a´rvore, v \u2208 V e v\u2032 \u2208 U \u2212 V , enta\u2dco (V \u222a {v\u2032}, A \u222a {{v, v\u2032}}, r) e´
uma a´rvore.
34
\ufffd
\ufffd	a
\ufffd\ufffd
\ufffd\ufffd\ufffd
HH
HHH\ufffd
\ufffd	b
\ufffd
\ufffd
\ufffd
@
@
@\ufffd
\ufffd	d \ufffd
\ufffd	f\ufffd
\ufffd	e
\ufffd
\ufffd
\ufffd
A
A
A\ufffd
\ufffd	i \ufffd
\ufffd	j
\ufffd
\ufffd	g
\ufffd
\ufffd	k
\ufffd
\ufffd	h
\ufffd
\ufffd	c
\ufffd
\ufffd
\ufffd
A
A
A
Figura 1.10: Exemplo de a´rvore com raiz.
Se r e´ a raiz e v um ve´rtice qualquer de uma a´rvore, pode-se mostrar que existe um, e
apenas um, caminho simples de r para v. Se o caminho simples de r para v passa por
um ve´rtice v\u2032 (que pode ser r ou v), diz-se que v\u2032 e´ ancestral de v e que v e´ descendente
de v\u2032. Neste caso, se {v\u2032, v} e´ uma aresta da a´rvore, diz-se ainda que v\u2032 e´ o ancestral
imediato, ou pai , de v e que v e´ um descendente imediato, ou filho, de v\u2032. Os filhos do
mesmo pai sa\u2dco ditos irma\u2dcos. Um ve´rtice sem filhos e´ denominado folha e um ve´rtice que
na\u2dco e´ folha e´ chamado ve´rtice interno. O n´\u131vel de um ve´rtice v de uma a´rvore de raiz r e´
o tamanho do caminho simples de r para v. A altura de uma a´rvore e´ o maior dentre os
n´\u131veis de seus ve´rtices. Se o maior nu´mero de filhos de ve´rtices de uma a´rvore e´ n, diz-se
que a a´rvore e´ n-a´ria (bina´ria, terna´ria, etc.).
Graficamente, uma a´rvore e´, em geral, representada com a raiz no topo, os ve´rtices
adjacentes a` raiz logo abaixo, os filhos destes u´ltimos mais abaixo, etc.
Exemplo 41 A Figura 1.10 apresenta a representac¸a\u2dco gra´fica de uma a´rvore terna´ria
com raiz a e arestas {a, b}, {a,