Ata de Aula: 26/08/2002
Redator:
Diogo Ditzel Kropiwiec 991631
Tópicos Discutidos mais importantes:
1- Teorema de Cayley
* Dado um conjunto de n vértices, é possível
construir
nn-2 árvores rotuladas distintas.
Ou ainda,
* Dado um grafo completo de n vértices, ele possui nn-2
árvores geradoras distintas (rotuladas).
2- Número de Grafos com n vértices
| * O número de grafos com n vértices (rotulados) é |
2 |
( | n
2 |
) |
3- Seqüência de graus
* É possível calcular o número de árvores rotuladas distintas obtidas dado uma seqüencia de graus dos vértices.
* Generalização do Teorema de Cayley
4- Cálculo do número de árvores espalhadas a partir da matriz de grafo árvore (Matrix Tree Graph)
* O número de arestas pode ser obtido pelo determinante da matriz obtida pela matriz diagonal de graus dos vértices menos a matriz de incidência do grafo.
5- Centopéia (Caterpillar)
* É um grafo composto por um único caminho (chamado espinha) em que todas as arestas ou pertencem ao caminho ou incidem em algum vértice do caminho.
Ex. * / *--*---*---*--*---* / /|\ / \ * * * * * ** Uma árvore é uma centopéia se e somente se não tiver a estrutura em Y abaixo.
*_ _* `*_ _*´ `*´ | * | *
Tópicos Discutidos menos importantes:
6- Código de Prüfer
* É uma representação compacta de uma árvore (Se a árvore tem n vértices, então o código tem n-2 elementos).
* O grau dos vértices pode ser obtido pelo número de vezes em que aparece no código de Prüfer mais 1.
* Base para a prova do teorma de Cayley
7- Calcúlo do número de árvores espalhadas a partir da Contração de Arestas
* G . e = Grafo gerado a partir do grafo G com a contração da aresta e. Pode conter múltiplas arestas
* t(G) = t(G -
e) + t(G . e)