Teoria de grafos

Teoria de grafos

1. O que são grafos?

   • http://www.evernote.com/l/AEsoscaYKtBFWoewgcCKR7-KiN0UsL9rJaY/
   • Vértices
     • V(G) = { 0, 1, 2, 3, 4, 5, 6, 7, 8 }
   • Arestas
     • E(G) = {a, b, c, e f, g, h, i, j}
   • Função de incidencia
   • Relações
     • Incidentes
       • Os vertices 0 e 2 são incidentes a b.
     • Adjacentes
       • Os vertices 0 e 2 são adjacentes Os vertices 0 e 6 são adjacentes
     • Laços
       • A aresta "a" é um laço sobre o vertice 0.
     • Arestas paralelas
       • As arestas s e h são paralelas.

2. Classificações

   • Simples
     • http://www.evernote.com/l/AEsw5QUaw7lBxZg6ouj8WK0HS4M3z-T9lL4/
     • Completo
       • http://www.evernote.com/l/AEt6UCGktYlFLKzSvboa6OxM2myKgiC_l00/
     • Bipartido
       • http://www.evernote.com/l/AEtCC4GSab9DrLxfU4T_Hm-XeyW-ROvyTpI/
       • Bipartido Completo
         • http://www.evernote.com/l/AEvqf_bujvlIu5om1OiYIkPxuZzvQ110hIo/
   • Conexo
     • http://www.evernote.com/l/AEu9qWCmM3JMe7EwehwDaTekLV5OhPVLBfw/

3. Relações

   • Isomorfismo
     • http://www.evernote.com/l/AEuP6elyRDpA_bf0cj-QTPXpzin9o-AFQ3w/
     • Como verificar?
       • http://www.evernote.com/l/AEsCJsEb4kxEZYALzNe_AH7d9Ocj51yFMV0/

4. Conceitos

   • Vizinhaça
     • http://www.evernote.com/l/AEslNBcSKbtAu66irN4zRuoOm-WLjPPHIbw/
   • Matriz
     • Incidencia
       • http://www.evernote.com/l/AEtGV6XRTmBNnoMtM0aA9APIZeMnf5bGpgc/
     • Adjacencias
       • http://www.evernote.com/l/AEt54GXJK_dA2ZcTbR6w0VmthfWJsFoD0P0/
   • Grau do vértice
     • http://www.evernote.com/l/AEuhpc_NwYhLM4jL9A1xqp-z2-miWO6i_dQ/
     • Somatorio dos graus
       • http://www.evernote.com/l/AEtQh3qhVVpE851WTYPDr5E1eiV1BqBJq_U/
     • Número de vertices de grau ímpar é par
       • http://www.evernote.com/l/AEsTmSazZihChbcTuhK9GuueG_TftZAiF5g/
   • deleção
     • http://www.evernote.com/l/AEtrMQIhRftH37IAlL8YlvoqvAJ6ZHCJhKg/
   • Subgrafos
     • http://www.evernote.com/l/AEu-J1kmhv9OvbBfFJj7JkZHoBRoIO6HkuI/
   • Partição
     • http://www.evernote.com/l/AEvIr-TO-OhIQqscYzBjNjeQk4qNyQkFQUg/

5. Rotas

   • Caminho
     • http://www.evernote.com/l/AEt5h1BUspZH55uKC3dUOC3IGlBhWjR79b8/
   • Ciclos
     • http://www.evernote.com/l/AEsYQ-CwwR1HbKEcWmL1CrEfzFR2RVmo3-w/
     • Teorema do ciclo pelo grau
       • http://www.evernote.com/l/AEvYW3MX_edH5YQ6hUXTAa_p3wbA8WEdPzc/
     • Acíclico
       • http://www.evernote.com/l/AEvk2rE-8mlAfpUWFch9Op_NLO4tYFjpZyg/
   • Comprimento
     • http://www.evernote.com/l/AEsGxK1p7QdHRL4YOI5v361Zp1WNxjc-dhY/

6. Dígrafo

   • http://www.evernote.com/l/AEu460vUReFKHpEvHHXm0iLtoRHhNBJekcI/
   • Restrito
     • http://www.evernote.com/l/AEs7hjU_xT5Eq6rfH8MDhHe9diL1wzsoyXI/
   • Grau do vértice
     • http://www.evernote.com/l/AEs6R03zbJ9GCLU2TVpDDg55NB2jnm3BhVA/
   • K-regular
     • http://www.evernote.com/l/AEt2Svn3yjxNGqAFIWcCeMZcIWl3hgJcOD8/