Grafos, matrizes, isomorfismo

Questões-guia:

1. O que é um grafo?  E um grafo simples?
2. O complemento de um grafo bipartido será sempre bipartido?
3. O que se pode dizer do número cromático de um grafo k-partite?
4. Um subgrafo de um grafo conexo será sempre conexo?  Mesma questão para um grafo desconexo.
5. Como obter a matrix de adjacência A(G) a partir da matriz de incidência M(G) de um grafo sem laços?  E se o grafo tiver laços?
6. Como se relacionam as matrizes de adjacência de dois grafos isomorfos?  E as de incidência?
7. O que é um n-ciclo?  E um grafo completo?  E um biclique?  Quais são as notações para estes grafos?
8. Desenhe os seguintes grafos: triângulo, garra, pata, pipa, casa, touro, gravata-borboleta, dardo.
9. Qual a cintura do grafo de Petersen?  E de seu complemento?
10. Quais dos grafos em (8) são vértice-transitivos?  Quais tem maior número de automorfismos?

Exercícios:

1. Exercício 1.1.11 do West.
2. Exercício 1.1.15 do West.
3. Exercício 1.1.27 do West.