Ata de Aula:     19/08/2002
Redator:             Cleber V. G. Mira
 

Tópicos Discutidos:
 

1- Grafos Orientados ( Passeios, Trilhas, Caminhos,... )
 

* Grafo Orientado:
Um grafo G=(V,E) é orientado se consiste de dois conjuntos, um conjunto de vértices e outro de arestas, onde cada aresta é associada a um par ordenado de vértices.

*Orientação de um Grafo Simples:
É o grafo orientado obtido a partir da especificação de sentido em todas as arestas de um grafo simples.
 

* Passeio Orientado:
Um passeio orientado em G=(V,E) é uma seqüência finita de vértices v_0,v_1,.....,v_k tal que  (v_i-1,  v_i),   1<= i <=k,   é uma aresta de G.

* Trilha Orientada:
Uma trilha orientada é um passeio orientado cujas arestas são distintas. A trilha será fechada sse seus vértices terminais forem idênticos.

*Caminho Orientado:
Uma trilha orientada aberta será um caminho se todos os seus vértices são distintos.

*Ciclo Orientado:
Uma trilha orientada fechada é um ciclo orientado se, exceto pelos vértices terminais, todos os demais vértices são distintos.
 
 

2- Conexão Forte

* Grafo Orientado Fortemente Conexo:
Um grafo orientado é fortemente conexo quando para quaisquer pares de vértices v e w houver um caminho orientado de v para w e de  w  para v .
 

*Componente Fortemente Conexo:
Um subgrafo H de G é um componente fortemente conexo de G sse H é um subgrafo fortemente conexo maximal.
 
 

3- Torneios

Definição: Orientação de um Grafo Completo

É possível fazer uma analogia com campeonatos de jogos onde não ocorrem empates. Cada vértice do torneio seria um time (ou competidor) e a orientação da aresta incidindo em dois vértices determinaria quem seria o vencedor no confronto.

*Score (pontuação):
A pontuação de um time em um torneio é o número de times vencidos por ele.

*Seqüência de Pontuação:
A seqüência de pontuações de um torneio de n vértices é a seqüência (s_1, s_2, s_3,.....,s_n) tal que cada s_i é o grau de arestas divergentes (saindo) de um vértice do torneio.
 

Resultado Importante:
Teorema: Um Torneio sempre possui um caminho hamiltoniano orientado.
 
 

4- Contração
 

*Contração de Vértices: A contração de vértices é o processo de identificar em um único vértice novo um conjunto de vértices P. Nesse processo são eliminadas as arestas cujos extremos estejam em P e mantidas as arestas restantes.
Ex.:
A contração dos componentes conexos ou dos vértices de mesmo grau em um grafo.
 

*Contração de Subgrafos: A contração de um subgrafo G' de um grafo G é a contração do conjunto V(G').

Ex.:
A contração dos componentes fortemente conexos em um grafo orientado gera um novo grafo orientado acíclico.