Matematica Discreta

Assuntos relacionados: Grafos, grafos simples, caminhos, ciclos e conectividade. Caminhos Eulerianos e circuitos hamiltonianos. Isomorfismos. Árvores. Dígrafos, caminhos em dígrafos. Aplicações em computação. (Cap 5 biblio 1).
Grafos
1) Faça uma lista de todos os grafos que tenham {a; b; c} por conjunto de vértices.4 Faça a lista de modo que cada grafo apareça ao lado do seu complemento.
Resposta: V = a,b,c |E = {(ab) , (ac) e (bc) }

2) Faça uma figura de um e outra de um . Quantas arestas tem um ? E um ?

2a) Decida se pode existir um grafo G com vértices que tem graus 2; 3; 3; 4; 4; 5. E graus 2; 3; 4; 4; 5?

3) O grafo dos movimentos da dama, ou simplesmente grafo da dama, dama é definido assim: os vértices do grafo são as casas de um tabuleiro de xadrez com t linhas e t colunas;7 dois vértices são adjacentes se uma dama (= queen) do jogo de xadrez pode saltar de um deles para o outro em um só movimento.
Para deixar claro o número de linhas e colunas do tabuleiro, podemos dizer que esse é o grafo da dama t-por-t. Faça uma figura do grafo da dama 4-por-4. Escreva as matrizes de adjacência e incidência do grafo da dama 4-por-4. Quantas arestas tem o grafo da dama 8-por-8? Quantas arestas tem o grafo da dama t-por-t?
Tabuleiros de xadrez 8-por-8. A figura indica todos os vizinhos do vértice no grafo da dama

4) O grafo das palavras é definido assim: cada vértices é uma palavra da língua portuguesa e duas palavras são adjacentes se diferem em exatamente uma posição. Por exemplo, rato e ralo são adjacentes, enquanto ralo e rota não são. Faça uma figura da parte do grafo definida pelas palavras abaixo: caiado cavado cavalo girafa girava ralo ramo rata rato remo reta reto rota vaiado varado virada virado virava
Escreva as matrizes de adjacência e incidência do grafo.
Obs: Esse grafo é uma adaptação do ladders do Stanford GraphBase: http://www.ime.usp.br/~pf/SGB/
5) Seja X o conjunto {1; 2; 3; 4; 5} e V o conjunto X(2) (portanto, V é o