Ata - Aula do dia 12/08/2002
Dia da digitação: 13/08/2002
Cibele Brunetto
 
Datas das Provas




Fechamos as datas das provas:
02/09 – Prova Individual
02/10 – Prova em Grupo
o4/11 – Prova Individual
04/12 – Prova em Grupo
 
Subgrafos
Sendo o grafo um conjunto de arestas e vértices, um subgrafo é um subconjunto de arestas e de vértices
do grafo, onde uma aresta deve estar ligada a dois vértices.
 
Caminho
É definido como sendo um tipo de grafo cujos vértices são distintos, bem como todas as arestas.
É um passeio onde os vértices são todos distintos.
 
Passeio
Um passeio P em G(V,E) é uma seqüência (v0, e1, v1, e2, v2..., vk-1, ek, vk) onde vi E V e v0 E V e 
ei={vi-1, vi} E E, onde 1 <= i <= k (v0 é origem e vk é destino).
 
Ciclo
É uma trilha fechada cuja origem é igual ao destino e cujos vértices internos são distintos entre si e
também diferem da origem/destino.
 
Trilha
É um passeio cujas arestas são todas distintas.
 
Conexão
Um grafo é conexo quando a partir de um vértice qualquer podemos alcançar todos os outros 
vértices através de um caminho.
O número máximo de arestas para que um grafo possa ser conexo é [(n-1).(n-2)] / 2
Para que um grafo seja conexo, o número de componentes desse grafo deve ser igual a 1.
 
Circuitos Eulerianos
É a trilha que passa por toda aresta de um grafo G, exatamente uma vez.
Um grafo é euleriano se e somente se ele não tem vértice com grau ímpar e, além disso, o grafo não 
pode possuir mais de 1 componente não trivial.
 
Relação entre grafos bipartidos e paridade dos ciclos
Um grafo é bipartido se e somente se ele não contém ciclos de comprimento ímpar.