Algoritmos e Teoria dos GrafosAula 08

Prof. Murilo V. G. da Silva

DINF/UFPR

Material da Disciplina:

Renato J. S. Carmo

Arvores, Florestas e Arborescencias

Arvore

Uma arvore e um grafo acıclico conexo.

Floresta

Uma floresta e um grafo em que cada componente e uma arvore.

Teorema

Um grafo e arvore ⇔ admite um unico caminho entre cada par de seus vertices.

Prova: Consequencia direta de um teorema da aula passada

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Arvore

Uma arvore e um grafo acıclico conexo.

Floresta

Uma floresta e um grafo em que cada componente e uma arvore.

Teorema

Um grafo e arvore ⇔ admite um unico caminho entre cada par de seus vertices.

Prova: Consequencia direta de um teorema da aula passada

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Arvore

Uma arvore e um grafo acıclico conexo.

Floresta

Uma floresta e um grafo em que cada componente e uma arvore.

Teorema

Um grafo e arvore ⇔ admite um unico caminho entre cada par de seus vertices.

Prova: Consequencia direta de um teorema da aula passada

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Arvore

Uma arvore e um grafo acıclico conexo.

Floresta

Uma floresta e um grafo em que cada componente e uma arvore.

Teorema

Um grafo e arvore ⇔ admite um unico caminho entre cada par de seus vertices.

Prova: Consequencia direta de um teorema da aula passada

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Denotamos por uTv o unico caminho de u a v na arvore T .

Se F e uma floresta e os vertices u e v estao no mesmo componente T de F ,usamos uFv como sinonimo de uTv .

Um vertice de grau 1 em uma floresta e chamado de folha.

Teorema

Toda arvore nao trivial tem (pelo menos) duas folhas.

Prova: Em sala de aula

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Denotamos por uTv o unico caminho de u a v na arvore T .

Se F e uma floresta e os vertices u e v estao no mesmo componente T de F ,usamos uFv como sinonimo de uTv .

Um vertice de grau 1 em uma floresta e chamado de folha.

Teorema

Toda arvore nao trivial tem (pelo menos) duas folhas.

Prova: Em sala de aula

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Denotamos por uTv o unico caminho de u a v na arvore T .

Se F e uma floresta e os vertices u e v estao no mesmo componente T de F ,usamos uFv como sinonimo de uTv .

Um vertice de grau 1 em uma floresta e chamado de folha.

Teorema

Toda arvore nao trivial tem (pelo menos) duas folhas.

Prova: Em sala de aula

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Denotamos por uTv o unico caminho de u a v na arvore T .

Se F e uma floresta e os vertices u e v estao no mesmo componente T de F ,usamos uFv como sinonimo de uTv .

Um vertice de grau 1 em uma floresta e chamado de folha.

Teorema

Toda arvore nao trivial tem (pelo menos) duas folhas.

Prova: Em sala de aula

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Teorema

Toda arvore de n vertices tem n − 1 arestas.

Prova: Em sala de aula

Corolario

Todo grafo conexo com n vertices e n − 1 arestas e arvore.

Prova: Exercıcio

Corolario

Um grafo com n vertices e arvore se e somente se e conexo e tem n − 1 arestas.

Corolario

O grafo G e floresta ⇔ |E(G)| = |V (G)| − |C(G)|.

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Teorema

Toda arvore de n vertices tem n − 1 arestas.

Prova: Em sala de aula

Corolario

Todo grafo conexo com n vertices e n − 1 arestas e arvore.

Prova: Exercıcio

Corolario

Um grafo com n vertices e arvore se e somente se e conexo e tem n − 1 arestas.

Corolario

O grafo G e floresta ⇔ |E(G)| = |V (G)| − |C(G)|.

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Teorema

Toda arvore de n vertices tem n − 1 arestas.

Prova: Em sala de aula

Corolario

Todo grafo conexo com n vertices e n − 1 arestas e arvore.

Prova: Exercıcio

Corolario

Um grafo com n vertices e arvore se e somente se e conexo e tem n − 1 arestas.

Corolario

O grafo G e floresta ⇔ |E(G)| = |V (G)| − |C(G)|.

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Teorema

Toda arvore de n vertices tem n − 1 arestas.

Prova: Em sala de aula

Corolario

Todo grafo conexo com n vertices e n − 1 arestas e arvore.

Prova: Exercıcio

Corolario

Um grafo com n vertices e arvore se e somente se e conexo e tem n − 1 arestas.

Corolario

O grafo G e floresta ⇔ |E(G)| = |V (G)| − |C(G)|.

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Teorema

Toda arvore de n vertices tem n − 1 arestas.

Prova: Em sala de aula

Corolario

Todo grafo conexo com n vertices e n − 1 arestas e arvore.

Prova: Exercıcio

Corolario

Um grafo com n vertices e arvore se e somente se e conexo e tem n − 1 arestas.

Corolario

O grafo G e floresta ⇔ |E(G)| = |V (G)| − |C(G)|.

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Teorema

Toda arvore de n vertices tem n − 1 arestas.

Prova: Em sala de aula

Corolario

Todo grafo conexo com n vertices e n − 1 arestas e arvore.

Prova: Exercıcio

Corolario

Um grafo com n vertices e arvore se e somente se e conexo e tem n − 1 arestas.

Corolario

O grafo G e floresta ⇔ |E(G)| = |V (G)| − |C(G)|.

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Teorema

Seja T e uma arvore e u, v ∈ V (G) vertices tal que {u, v} /∈ E(T ). Entao T + {u, v}tem um unico ciclo.

Prova: Em sala de aula

Seja T uma arvore e u, v ∈ V (T ) tal que {u, v} /∈ E(T )

O ciclo T [uTv(v , u)] e o ciclo fundamental de {u, v} com relacao a T .

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Teorema

Seja T e uma arvore e u, v ∈ V (G) vertices tal que {u, v} /∈ E(T ). Entao T + {u, v}tem um unico ciclo.

Prova: Em sala de aula

Seja T uma arvore e u, v ∈ V (T ) tal que {u, v} /∈ E(T )

O ciclo T [uTv(v , u)] e o ciclo fundamental de {u, v} com relacao a T .

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Teorema

Seja T e uma arvore e u, v ∈ V (G) vertices tal que {u, v} /∈ E(T ). Entao T + {u, v}tem um unico ciclo.

Prova: Em sala de aula

Seja T uma arvore e u, v ∈ V (T ) tal que {u, v} /∈ E(T )

O ciclo T [uTv(v , u)] e o ciclo fundamental de {u, v} com relacao a T .

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Se T e um subgrafo de G que e arvore, dizemos que T e uma arvore de G .

(o mesmo vale para floresta)

Arvore Geradora

Uma arvore geradora de G e um subgrafo gerador que e uma arvore

Definicao similar para floresta geradora

Teorema

Um subgrafo do grafo G e arvore geradora de G ⇔ e subgrafo conexo minimal de G .

Prova: Exercıcio

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Se T e um subgrafo de G que e arvore, dizemos que T e uma arvore de G .(o mesmo vale para floresta)

Arvore Geradora

Uma arvore geradora de G e um subgrafo gerador que e uma arvore

Definicao similar para floresta geradora

Teorema

Um subgrafo do grafo G e arvore geradora de G ⇔ e subgrafo conexo minimal de G .

Prova: Exercıcio

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Se T e um subgrafo de G que e arvore, dizemos que T e uma arvore de G .(o mesmo vale para floresta)

Arvore Geradora

Uma arvore geradora de G e um subgrafo gerador que e uma arvore

Definicao similar para floresta geradora

Teorema

Um subgrafo do grafo G e arvore geradora de G ⇔ e subgrafo conexo minimal de G .

Prova: Exercıcio

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Se T e um subgrafo de G que e arvore, dizemos que T e uma arvore de G .(o mesmo vale para floresta)

Arvore Geradora

Uma arvore geradora de G e um subgrafo gerador que e uma arvore

Definicao similar para floresta geradora

Teorema

Um subgrafo do grafo G e arvore geradora de G ⇔ e subgrafo conexo minimal de G .

Prova: Exercıcio

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Se T e um subgrafo de G que e arvore, dizemos que T e uma arvore de G .(o mesmo vale para floresta)

Arvore Geradora

Uma arvore geradora de G e um subgrafo gerador que e uma arvore

Definicao similar para floresta geradora

Teorema

Um subgrafo do grafo G e arvore geradora de G ⇔ e subgrafo conexo minimal de G .

Prova: Exercıcio

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Se T e um subgrafo de G que e arvore, dizemos que T e uma arvore de G .(o mesmo vale para floresta)

Arvore Geradora

Uma arvore geradora de G e um subgrafo gerador que e uma arvore

Definicao similar para floresta geradora

Teorema

Um subgrafo do grafo G e arvore geradora de G ⇔ e subgrafo conexo minimal de G .

Prova: Exercıcio

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Arvore enraizada

Uma arvore enraizada e um par (T , r) onde T e uma arvore e r e um verticede T , chamado raız de T .

Nıvel de um vertice

O nıvel do vertice v na arvore enraizada (T , r) e a distancia de r a v em T ,isto e,

LT ,r (v) = dT (r , v).

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Arvore enraizada

Uma arvore enraizada e um par (T , r) onde T e uma arvore e r e um verticede T , chamado raız de T .

Nıvel de um vertice

O nıvel do vertice v na arvore enraizada (T , r) e a distancia de r a v em T ,isto e,

LT ,r (v) = dT (r , v).

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Arborescencia

Uma arborescencia e um grafo direcionado conexo com uma unica fonte em que todosos demais vertices tem grau de entrada 1.

A fonte de uma arborescencia T e chamada de raiz de T e e denotada r(T ).

Definicoes

Seja T uma arborescencia

Se (u, v) ∈ V (T ), entao dizemos que u e pai de v e que v e filho de u em T .

Se existe caminho direcionado de u a v em T , entao dizemos que u e ancestralde v e que v e descendente de u em T . Notacao: u ≤T v . Se u 6= v dizemosainda que u e ancestral proprio de v e que v e descendente proprio de u em T oque e denotado por u <T v .

v ∈ V (T ) nao tem filhos, dizemos que v e uma folha de T .

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Arborescencia

Uma arborescencia e um grafo direcionado conexo com uma unica fonte em que todosos demais vertices tem grau de entrada 1.

A fonte de uma arborescencia T e chamada de raiz de T e e denotada r(T ).

Definicoes

Seja T uma arborescencia

Se (u, v) ∈ V (T ), entao dizemos que u e pai de v e que v e filho de u em T .

Se existe caminho direcionado de u a v em T , entao dizemos que u e ancestralde v e que v e descendente de u em T . Notacao: u ≤T v . Se u 6= v dizemosainda que u e ancestral proprio de v e que v e descendente proprio de u em T oque e denotado por u <T v .

v ∈ V (T ) nao tem filhos, dizemos que v e uma folha de T .

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Arborescencia

Uma arborescencia e um grafo direcionado conexo com uma unica fonte em que todosos demais vertices tem grau de entrada 1.

A fonte de uma arborescencia T e chamada de raiz de T e e denotada r(T ).

Definicoes

Seja T uma arborescencia

Se (u, v) ∈ V (T ), entao dizemos que u e pai de v e que v e filho de u em T .

Se existe caminho direcionado de u a v em T , entao dizemos que u e ancestralde v e que v e descendente de u em T . Notacao: u ≤T v . Se u 6= v dizemosainda que u e ancestral proprio de v e que v e descendente proprio de u em T oque e denotado por u <T v .

v ∈ V (T ) nao tem filhos, dizemos que v e uma folha de T .

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Arborescencia

Uma arborescencia e um grafo direcionado conexo com uma unica fonte em que todosos demais vertices tem grau de entrada 1.

A fonte de uma arborescencia T e chamada de raiz de T e e denotada r(T ).

Definicoes

Seja T uma arborescencia

Se (u, v) ∈ V (T ), entao dizemos que u e pai de v e que v e filho de u em T .

Se existe caminho direcionado de u a v em T , entao dizemos que u e ancestralde v e que v e descendente de u em T . Notacao: u ≤T v . Se u 6= v dizemosainda que u e ancestral proprio de v e que v e descendente proprio de u em T oque e denotado por u <T v .

v ∈ V (T ) nao tem filhos, dizemos que v e uma folha de T .

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Arborescencia

Uma arborescencia e um grafo direcionado conexo com uma unica fonte em que todosos demais vertices tem grau de entrada 1.

A fonte de uma arborescencia T e chamada de raiz de T e e denotada r(T ).

Definicoes

Seja T uma arborescencia

Se (u, v) ∈ V (T ), entao dizemos que u e pai de v e que v e filho de u em T .

Se existe caminho direcionado de u a v em T , entao dizemos que u e ancestralde v e que v e descendente de u em T . Notacao: u ≤T v . Se u 6= v dizemosainda que u e ancestral proprio de v e que v e descendente proprio de u em T oque e denotado por u <T v .

v ∈ V (T ) nao tem filhos, dizemos que v e uma folha de T .

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Arborescencia

Uma arborescencia e um grafo direcionado conexo com uma unica fonte em que todosos demais vertices tem grau de entrada 1.

A fonte de uma arborescencia T e chamada de raiz de T e e denotada r(T ).

Definicoes

Seja T uma arborescencia

Se (u, v) ∈ V (T ), entao dizemos que u e pai de v e que v e filho de u em T .

Se existe caminho direcionado de u a v em T , entao dizemos que u e ancestralde v e que v e descendente de u em T . Notacao: u ≤T v . Se u 6= v dizemosainda que u e ancestral proprio de v e que v e descendente proprio de u em T oque e denotado por u <T v .

v ∈ V (T ) nao tem filhos, dizemos que v e uma folha de T .

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Seja T uma arborescencia, u, v ∈ V (T ) tal que u e ancestral de v

O unico ciclo direcionado de T + (v , u) e chamado de ciclo fundamental de(v , u) com relacao a T .

Floresta direcionada

Uma floresta direcionada e um grafo direcionado em que cada componente e umaarborescencia.

Seja T e uma floresta direcionada geradora de um grafo direcionado G e(u, v) ∈ A(G)− A(T ).

O arco (u, v) pode ser dos seguintes tipos:

laco: se u = v (caso lacos sejam permitidos)

arco de retorno: se u >T v

arco de avanco: se u <T v

arco cruzado: se u 6<T v

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Seja T uma arborescencia, u, v ∈ V (T ) tal que u e ancestral de v

O unico ciclo direcionado de T + (v , u) e chamado de ciclo fundamental de(v , u) com relacao a T .

Floresta direcionada

Uma floresta direcionada e um grafo direcionado em que cada componente e umaarborescencia.

Seja T e uma floresta direcionada geradora de um grafo direcionado G e(u, v) ∈ A(G)− A(T ).

O arco (u, v) pode ser dos seguintes tipos:

laco: se u = v (caso lacos sejam permitidos)

arco de retorno: se u >T v

arco de avanco: se u <T v

arco cruzado: se u 6<T v

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Seja T uma arborescencia, u, v ∈ V (T ) tal que u e ancestral de v

O unico ciclo direcionado de T + (v , u) e chamado de ciclo fundamental de(v , u) com relacao a T .

Floresta direcionada

Uma floresta direcionada e um grafo direcionado em que cada componente e umaarborescencia.

Seja T e uma floresta direcionada geradora de um grafo direcionado G e(u, v) ∈ A(G)− A(T ).

O arco (u, v) pode ser dos seguintes tipos:

laco: se u = v (caso lacos sejam permitidos)

arco de retorno: se u >T v

arco de avanco: se u <T v

arco cruzado: se u 6<T v

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Seja T uma arborescencia, u, v ∈ V (T ) tal que u e ancestral de v

O unico ciclo direcionado de T + (v , u) e chamado de ciclo fundamental de(v , u) com relacao a T .

Floresta direcionada

Uma floresta direcionada e um grafo direcionado em que cada componente e umaarborescencia.

Seja T e uma floresta direcionada geradora de um grafo direcionado G e(u, v) ∈ A(G)− A(T ).

O arco (u, v) pode ser dos seguintes tipos:

laco: se u = v (caso lacos sejam permitidos)

arco de retorno: se u >T v

arco de avanco: se u <T v

arco cruzado: se u 6<T v

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Seja T uma arborescencia, u, v ∈ V (T ) tal que u e ancestral de v

O unico ciclo direcionado de T + (v , u) e chamado de ciclo fundamental de(v , u) com relacao a T .

Floresta direcionada

Uma floresta direcionada e um grafo direcionado em que cada componente e umaarborescencia.

Seja T e uma floresta direcionada geradora de um grafo direcionado G e(u, v) ∈ A(G)− A(T ).

O arco (u, v) pode ser dos seguintes tipos:

laco: se u = v

(caso lacos sejam permitidos)

arco de retorno: se u >T v

arco de avanco: se u <T v

arco cruzado: se u 6<T v

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Seja T uma arborescencia, u, v ∈ V (T ) tal que u e ancestral de v

O unico ciclo direcionado de T + (v , u) e chamado de ciclo fundamental de(v , u) com relacao a T .

Floresta direcionada

Uma floresta direcionada e um grafo direcionado em que cada componente e umaarborescencia.

Seja T e uma floresta direcionada geradora de um grafo direcionado G e(u, v) ∈ A(G)− A(T ).

O arco (u, v) pode ser dos seguintes tipos:

laco: se u = v (caso lacos sejam permitidos)

arco de retorno: se u >T v

arco de avanco: se u <T v

arco cruzado: se u 6<T v

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Seja T uma arborescencia, u, v ∈ V (T ) tal que u e ancestral de v

O unico ciclo direcionado de T + (v , u) e chamado de ciclo fundamental de(v , u) com relacao a T .

Floresta direcionada

Uma floresta direcionada e um grafo direcionado em que cada componente e umaarborescencia.

Seja T e uma floresta direcionada geradora de um grafo direcionado G e(u, v) ∈ A(G)− A(T ).

O arco (u, v) pode ser dos seguintes tipos:

laco: se u = v (caso lacos sejam permitidos)

arco de retorno: se u >T v

arco de avanco: se u <T v

arco cruzado: se u 6<T v

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Seja T uma arborescencia, u, v ∈ V (T ) tal que u e ancestral de v

O unico ciclo direcionado de T + (v , u) e chamado de ciclo fundamental de(v , u) com relacao a T .

Floresta direcionada

Uma floresta direcionada e um grafo direcionado em que cada componente e umaarborescencia.

Seja T e uma floresta direcionada geradora de um grafo direcionado G e(u, v) ∈ A(G)− A(T ).

O arco (u, v) pode ser dos seguintes tipos:

laco: se u = v (caso lacos sejam permitidos)

arco de retorno: se u >T v

arco de avanco: se u <T v

arco cruzado: se u 6<T v

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Dizemos que uma arborescencia T e uma arborescencia de um grafo G se o grafoS(T ) e arvore de G .

Uma floresta direcionada F e uma floresta direcionada de um grafo naodirecionado G se o grafo S(F ) e floresta de G .

Neste caso, por convencao E(F ) = E(S(F ))

No caso acima, uma aresta {u, v} /∈ E(F ) pode ser dos seguintes tipos

de retorno se u <T v ou v <T u,

cruzada se u 6<T v .

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Dizemos que uma arborescencia T e uma arborescencia de um grafo G se o grafoS(T ) e arvore de G .

Uma floresta direcionada F e uma floresta direcionada de um grafo naodirecionado G se o grafo S(F ) e floresta de G .

Neste caso, por convencao E(F ) = E(S(F ))

No caso acima, uma aresta {u, v} /∈ E(F ) pode ser dos seguintes tipos

de retorno se u <T v ou v <T u,

cruzada se u 6<T v .

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Dizemos que uma arborescencia T e uma arborescencia de um grafo G se o grafoS(T ) e arvore de G .

Uma floresta direcionada F e uma floresta direcionada de um grafo naodirecionado G se o grafo S(F ) e floresta de G .

Neste caso, por convencao E(F ) = E(S(F ))

No caso acima, uma aresta {u, v} /∈ E(F ) pode ser dos seguintes tipos

de retorno se u <T v ou v <T u,

cruzada se u 6<T v .

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Arvores, Florestas e Arborescencias

Dizemos que uma arborescencia T e uma arborescencia de um grafo G se o grafoS(T ) e arvore de G .

Uma floresta direcionada F e uma floresta direcionada de um grafo naodirecionado G se o grafo S(F ) e floresta de G .

Neste caso, por convencao E(F ) = E(S(F ))

No caso acima, uma aresta {u, v} /∈ E(F ) pode ser dos seguintes tipos

de retorno se u <T v ou v <T u,

cruzada se u 6<T v .

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos