{"id":23953,"date":"2023-09-10T11:29:25","date_gmt":"2023-09-10T14:29:25","guid":{"rendered":"https:\/\/maurinsoft.com.br\/?p=23953"},"modified":"2023-09-11T10:01:07","modified_gmt":"2023-09-11T13:01:07","slug":"grafos-teoria-e-pratica","status":"publish","type":"post","link":"https:\/\/maurinsoft.com.br\/wp\/grafos-teoria-e-pratica\/","title":{"rendered":"Grafos Teoria e Pr\u00e1tica"},"content":{"rendered":"\n
\n

Parte do material deste tutorial veio do CHATGPT4.<\/p>\n<\/blockquote>\n\n\n\n

Origem<\/h1>\n\n\n
\n
\"\"<\/figure>\n<\/div>\n\n\n
    \n
  • Problema das Pontes de K\u00f6nigsberg (1736)<\/strong>: Leonhard Euler demonstrou ser imposs\u00edvel caminhar pela cidade de K\u00f6nigsberg, passando por cada uma das sete pontes exatamente uma vez e retornando ao ponto de partida. Este problema \u00e9 a origem da teoria dos grafos.<\/li>\n<\/ul>\n\n\n\n
    grafo = {\n    \"A\": [\"B\", \"C\"],\n    \"B\": [\"A\", \"D\", \"E\"],\n    \"C\": [\"A\", \"F\"],\n    \"D\": [\"B\"],\n    \"E\": [\"B\", \"F\"],\n    \"F\": [\"C\", \"E\"]\n}\n<\/code><\/pre>\n\n\n\n
    Desenvolvimento e Conceitos Chave<\/h2>\n\n\n\n
      \n
    • Gustav Kirchhoff<\/strong>: Introduziu a matriz de incid\u00eancia e estudou \u00e1rvores abrangentes.<\/li>\n\n\n\n
    • James Joseph Sylvester<\/strong>: Investigou grafos planares.<\/li>\n<\/ul>\n\n\n\n
      Teoremas e Problemas Not\u00e1veis<\/h2>\n\n\n\n
        \n
      • Teorema das quatro cores<\/strong>: Qualquer mapa em um plano pode ser colorido com no m\u00e1ximo quatro cores distintas, de modo que regi\u00f5es adjacentes n\u00e3o tenham a mesma cor. Provado em 1976.<\/li>\n\n\n\n
      • Problema do caixeiro-viajante<\/strong>: Busca o caminho mais curto que visita cada cidade exatamente uma vez, retornando \u00e0 origem.<\/li>\n\n\n\n
      • Algoritmos de Dijkstra e Floyd-Warshall<\/strong>: Encontram caminhos mais curtos em grafos.<\/li>\n<\/ul>\n\n\n\n
        Aplica\u00e7\u00f5es Modernas<\/h2>\n\n\n\n
          \n
        • S\u00e9culo XXI<\/strong>: Uso extensivo da teoria dos grafos em redes sociais, internet das coisas e sistemas complexos.<\/li>\n<\/ul>\n\n\n\n
          Essa s\u00edntese destaca os marcos e conceitos mais relevantes na evolu\u00e7\u00e3o da teoria dos grafos.<\/p>\n\n\n\n
          Elementos dos Grafos<\/h1>\n\n\n\n
          Os grafos s\u00e3o rela\u00e7\u00f5es entre partes, e podemos entender seus elementos como se segue:<\/p>\n\n\n\n
          Elementos B\u00e1sicos de Grafos<\/h3>\n\n\n\n
            \n
          1. V\u00e9rtices (ou N\u00f3s)<\/strong>: S\u00e3o as entidades do grafo. Em contextos pr\u00e1ticos, podem representar cidades, computadores em uma rede, pessoas em uma rede social, entre outros.<\/li>\n\n\n\n
          2. Arestas (ou Liga\u00e7\u00f5es)<\/strong>: S\u00e3o as conex\u00f5es entre os v\u00e9rtices. Em um mapa, por exemplo, uma aresta pode representar uma estrada conectando duas cidades.<\/li>\n\n\n\n
          3. Grafos Dirigidos vs. N\u00e3o Dirigidos<\/strong>: Em um grafo dirigido (ou digrafo), as arestas t\u00eam uma dire\u00e7\u00e3o, indo de um v\u00e9rtice para outro. Em grafos n\u00e3o dirigidos, as arestas n\u00e3o t\u00eam dire\u00e7\u00e3o.<\/li>\n\n\n\n
          4. Peso<\/strong>: As arestas podem ter um peso associado, que pode representar dist\u00e2ncias, custos, etc.<\/li>\n<\/ol>\n\n\n\n
            Implementa\u00e7\u00f5es<\/h2>\n\n\n\n
            A implementa\u00e7\u00e3o de um grafo pode ser feita de v\u00e1rias formas, pois \u00e9 um conceito.<\/p>\n\n\n\n
            Porem as formas mais comuns s\u00e3o descritos a seguir:<\/p>\n\n\n\n
            Lista de Adjac\u00eancia<\/strong><\/h3>\n\n\n\n
            \u00c9 uma lista onde, para cada v\u00e9rtice do grafo, armazenamos uma lista de seus v\u00e9rtices adjacentes. \u00c9 uma forma eficiente de armazenar grafos esparso.<\/p>\n\n\n\n
            Exemplo em python:<\/p>\n\n\n\n
            Matriz de Adjac\u00eancia<\/strong><\/h3>\n\n\n\n
            A matriz de adjac\u00eancia \u00e9 uma das formas mais comuns de representar um grafo em termos de estrutura de dados. Ela utiliza uma matriz bidimensional (um array de arrays) para expressar as rela\u00e7\u00f5es entre os v\u00e9rtices de um grafo.<\/p>\n\n\n\n
            Caracter\u00edsticas B\u00e1sicas<\/h3>\n\n\n\n
              \n
            1. Tamanho da Matriz<\/strong>: Se um grafo tem V<\/em> v\u00e9rtices, sua matriz de adjac\u00eancia ser\u00e1 de tamanho V<\/em>\u00d7V<\/em>.<\/li>\n\n\n\n
            2. Grafos N\u00e3o Dirigidos<\/strong>:\n
                \n
              • Se o v\u00e9rtice i<\/em> estiver conectado ao v\u00e9rtice j<\/em>, ent\u00e3o matriz[i][j] = 1 (ou o peso da aresta, em grafos ponderados).<\/li>\n\n\n\n
              • Como o grafo \u00e9 n\u00e3o dirigido, matriz[j][i] tamb\u00e9m ser\u00e1 1.<\/li>\n\n\n\n
              • Em outras palavras, a matriz \u00e9 sim\u00e9trica em rela\u00e7\u00e3o \u00e0 sua diagonal principal.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
              • Grafos Dirigidos (Digrafos)<\/strong>:\n
                  \n
                • Se existir uma aresta dirigida do v\u00e9rtice i<\/em> para o v\u00e9rtice j<\/em>, ent\u00e3o matriz[i][j] = 1 (ou o peso da aresta).<\/li>\n\n\n\n
                • Neste caso, a matriz n\u00e3o \u00e9 necessariamente sim\u00e9trica.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                • Grafos Ponderados<\/strong>:\n
                    \n
                  • Em vez de conter apenas valores bin\u00e1rios (0 ou 1), a matriz cont\u00e9m os pesos das arestas. Se n\u00e3o houver conex\u00e3o entre dois v\u00e9rtices, um valor padr\u00e3o (geralmente 0 ou infinito) \u00e9 usado.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                  • Diagonal Principal<\/strong>: Em muitos grafos, a diagonal principal (matriz[i][i] para todos os i<\/em>) cont\u00e9m zeros, porque muitos grafos n\u00e3o t\u00eam la\u00e7os (uma aresta que conecta um v\u00e9rtice a si mesmo). Se o grafo permitir la\u00e7os, o valor na diagonal principal representar\u00e1 a presen\u00e7a (ou o peso) de tal la\u00e7o.<\/li>\n<\/ol>\n\n\n\n
                    Vantagens e Desvantagens da Matriz de Adjac\u00eancia<\/h3>\n\n\n\n
                    Vantagens<\/strong>:<\/p>\n\n\n\n
                      \n
                    • Acesso direto: A verifica\u00e7\u00e3o da exist\u00eancia de uma aresta entre dois v\u00e9rtices \u00e9 realizada em tempo constante.<\/li>\n\n\n\n
                    • Representa\u00e7\u00e3o intuitiva: \u00c9 f\u00e1cil visualizar e entender, especialmente para grafos pequenos.<\/li>\n<\/ul>\n\n\n\n
                      Desvantagens<\/strong>:<\/p>\n\n\n\n
                        \n
                      • Uso de espa\u00e7o: Para um grafo com V<\/em> v\u00e9rtices, \u00e9 necess\u00e1rio V\u00b2<\/em> espa\u00e7o, o que pode ser ineficiente para grafos grandes e esparsos.<\/li>\n\n\n\n
                      • Iterar sobre os vizinhos: Em um grafo esparso, descobrir os vizinhos de um v\u00e9rtice exige que se verifique toda uma linha ou coluna, o que pode ser ineficiente.<\/li>\n<\/ul>\n\n\n\n
                        Exemplo<\/h3>\n\n\n\n
                        Para o grafo com v\u00e9rtices A<\/em>,B<\/em>,C<\/em> e arestas (A<\/em>,B<\/em>),(B<\/em>,C<\/em>):<\/p>\n\n\n\n
                        A matriz de adjac\u00eancia (n\u00e3o ponderada) seria:<\/p>\n\n\n\n
                           A  B  C\nA [0, 1, 0]\nB [1, 0, 1]\nC [0, 1, 0]<\/code><\/pre>\n\n\n\n
                        Se este fosse um grafo ponderado, onde a aresta (A<\/em>,B<\/em>) tem peso 3 e (B<\/em>,C<\/em>) tem peso 2, a matriz seria:<\/p>\n\n\n\n
                           A  B  C\nA [0, 3, 0]\nB [3, 0, 2]\nC [0, 2, 0]\n<\/code><\/pre>\n\n\n\n
                        Exemplo de Solu\u00e7\u00e3o de Problema de Rota<\/h2>\n\n\n\n
                        Apresentaremos um problema de Rota, onde teremos apenas 5 pontes para ir do ponto A ao ponto C.<\/p>\n\n\n\n
                        Nele apresentaremos uma proposta descritiva e depois uma proposta em Python.<\/p>\n\n\n\n
                        Vamos ao grafo dado:<\/p>\n\n\n\n
                        V\u00e9rtices:A<\/em>,B<\/em>,C<\/em>,D<\/em>,E<\/em> Liga\u00e7\u00f5es: A<\/em>\u2212B<\/em>,B<\/em>\u2212E<\/em>,E<\/em>\u2212C<\/em>,D<\/em>\u2212A<\/em>,B<\/em>\u2212C<\/em><\/p>\n\n\n\n
                        A matriz de adjac\u00eancia \u00e9 uma matriz n<\/em>\u00d7n<\/em> onde n<\/em> \u00e9 o n\u00famero de v\u00e9rtices. A entrada M(<\/em>i,j)<\/em>\u200b ser\u00e1 1 se o v\u00e9rtice i<\/em> estiver ligado ao v\u00e9rtice j<\/em> e 0 caso contr\u00e1rio.<\/p>\n\n\n
                        \n
                        \"\"<\/figure>\n<\/div>\n\n\n
                        Resolvendo o problema com python<\/h2>\n\n\n\n
                        Uma maneira simples de fazer isso \u00e9 usando uma busca em largura (BFS). Vamos criar um exemplo em Python para isso:<\/p>\n\n\n\n
                        import heapq\n\ndef heuristic(node, goal):\n    # Como um grafo n\u00e3o possui coordenadas espaciais, podemos usar uma heur\u00edstica trivial.\n    return 0\n\ndef a_star(graph, start, goal):\n    open_list = [(0, start)]\n    g_costs = {node: float('inf') for node in range(len(graph))}\n    g_costs[start] = 0\n\n    came_from = {}\n\n    while open_list:\n        current_cost, current_node = heapq.heappop(open_list)\n\n        if current_node == goal:\n            path = []\n            while current_node in came_from:\n                path.insert(0, current_node)\n                current_node = came_from[current_node]\n            path.insert(0, start)\n            return path\n\n        for neighbor, cost in enumerate(graph[current_node]):\n            if cost == 1:  # Existe uma aresta\n                tentative_g_cost = g_costs[current_node] + 1\n                if tentative_g_cost < g_costs[neighbor]:\n                    came_from[neighbor] = current_node\n                    g_costs[neighbor] = tentative_g_cost\n                    f_cost = tentative_g_cost + heuristic(neighbor, goal)\n                    heapq.heappush(open_list, (f_cost, neighbor))\n\n    return None\n\ngraph = [\n    [0, 1, 0, 1, 0],  # A\n    [1, 0, 1, 0, 1],  # B\n    [0, 1, 0, 0, 1],  # C\n    [1, 0, 0, 0, 0],  # D\n    [0, 1, 1, 0, 0]   # E\n]\n\npath = a_star(graph, 0, 2)\nif path:\n    print(\" -> \".join(chr(65 + node) for node in path))\nelse:\n    print(\"N\u00e3o foi encontrado um caminho de A para C.\")<\/code><\/pre>\n\n\n\n
                        Resultado:<\/strong><\/p>\n\n\n\n
                        A -> B -> C<\/p>\n\n\n\n
                        Outros usos de Grafo:<\/p>\n\n\n\n
                        Outro problema complexo<\/h2>\n\n\n\n
                        Agora teremos como objetivo desenvolver um NLP que ir\u00e1 analisar de comandos dados de forma textual, utilizando grafos como base de tomada de decis\u00e3o.<\/p>\n\n\n\n
                        Para isso temos duas tabelas:<\/p>\n\n\n\n
                        Palavras<\/strong>: Contem uma lista de palavras usadas nos textos.<\/p>\n\n\n\n
                        Comandos<\/strong>: Contem uma lista de comandos poss\u00edveis.<\/p>\n\n\n\n
                        Usaremos como exemplo de v\u00e9rtice apenas quando duas palavras em sequencia estiverem atendidas em determinado grafo, ai ligaremos estes aos comandos.<\/p>\n\n\n\n
                        Tabela Palavras:<\/h3>\n\n\n\n
                        Esta tabela cont\u00e9m uma lista de palavras chave que podem ser usadas para determinar a\u00e7\u00f5es.<\/p>\n\n\n\n
                        Palavras<\/th><\/tr><\/thead>
                        Grave<\/td><\/tr>
                        Di\u00e1rio<\/td><\/tr>
                        Reproduza<\/td><\/tr>
                        M\u00fasica<\/td><\/tr>
                        Ligue<\/td><\/tr>
                        Luz<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
                        Tabela A\u00e7\u00f5es:<\/h3>\n\n\n\n
                        Esta tabela associa sequ\u00eancias de palavras a a\u00e7\u00f5es espec\u00edficas.<\/p>\n\n\n\n
                        Sequ\u00eancia de Palavras<\/th>A\u00e7\u00e3o<\/th><\/tr><\/thead>
                        Grave Di\u00e1rio<\/td>Grava\u00e7\u00e3o de entradas no di\u00e1rio<\/td><\/tr>
                        Reproduza M\u00fasica<\/td>Tocar m\u00fasica<\/td><\/tr>
                        Ligue Luz<\/td>Acender a luz<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
                        Neste caso, o grafo seria algo assim:<\/p>\n\n\n\n
                          \n
                        1. O v\u00e9rtice “Grave” tem uma aresta direcionada para “Di\u00e1rio”, que representa a a\u00e7\u00e3o “Grava\u00e7\u00e3o de entradas no di\u00e1rio”.<\/li>\n\n\n\n
                        2. O v\u00e9rtice “Reproduza” tem uma aresta direcionada para “M\u00fasica”, representando a a\u00e7\u00e3o “Tocar m\u00fasica”.<\/li>\n\n\n\n
                        3. O v\u00e9rtice “Ligue” tem uma aresta direcionada para “Luz”, representando a a\u00e7\u00e3o “Acender a luz”.<\/li>\n<\/ol>\n\n\n\n
                          A ideia aqui \u00e9 que, se algu\u00e9m dissesse “Grave meu Di\u00e1rio”, o sistema reconheceria a sequ\u00eancia “Grave Di\u00e1rio” e acionaria a fun\u00e7\u00e3o correspondente de “Grava\u00e7\u00e3o de entradas no di\u00e1rio”. As stop words, como “meu”, seriam ignoradas pelo sistema.<\/p>\n\n\n\n
                          Para implementar isso, voc\u00ea poderia criar um dicion\u00e1rio em Python que mapeia sequ\u00eancias de palavras (arestas) a a\u00e7\u00f5es, e ent\u00e3o usar esse dicion\u00e1rio para determinar a a\u00e7\u00e3o apropriada com base na entrada do usu\u00e1rio.<\/p>\n\n\n\n
                          Passos:<\/h3>\n\n\n\n
                            \n
                          1. Instalar as bibliotecas necess\u00e1rias<\/li>\n\n\n\n
                          2. Configurar o banco de dados<\/li>\n\n\n\n
                          3. Criar a tabela de arestas no banco de dados<\/li>\n\n\n\n
                          4. Implementar fun\u00e7\u00f5es em Python para interagir com o banco de dados<\/li>\n<\/ol>\n\n\n\n
                            1. Instalar as bibliotecas necess\u00e1rias<\/h3>\n\n\n\n
                            Certifique-se de que voc\u00ea tem o MySQL instalado e em execu\u00e7\u00e3o. Depois, voc\u00ea pode instalar o conector MySQL para Python:<\/p>\n\n\n\n
                            pip install mysql-connector-python\npip install nltk\n<\/code><\/pre>\n\n\n\n
                            2. Configurar o banco de dados<\/h3>\n\n\n\n
                            Crie um novo banco de dados chamado graph_db<\/code> e um usu\u00e1rio para esse banco de dados. Voc\u00ea pode fazer isso usando a interface de linha de comando do MySQL ou um cliente GUI como o MySQL Workbench.<\/p>\n\n\n\n
                            Cria\u00e7\u00e3o do Banco<\/h2>\n\n\n\n
                            Aqui est\u00e1 uma sugest\u00e3o de estrutura:<\/p>\n\n\n\n
                              \n
                            1. words<\/code>: Guarda os v\u00e9rtices do tipo palavra.<\/li>\n\n\n\n
                            2. commands<\/code>: Guarda os v\u00e9rtices do tipo comando.<\/li>\n\n\n\n
                            3. edges<\/code>: Guarda as arestas, referenciando palavras e comandos.<\/li>\n<\/ol>\n\n\n\n
                              SQL para cria\u00e7\u00e3o das tabelas:<\/h3>\n\n\n\n
                              CREATE DATABASE graph_db;\nUSE graph_db;\n\n-- Tabela de palavras\nCREATE TABLE words (\n    word_id INT AUTO_INCREMENT PRIMARY KEY,\n    word_name VARCHAR(50) UNIQUE NOT NULL\n);\n\n-- Tabela de comandos\nCREATE TABLE commands (\n    command_id INT AUTO_INCREMENT PRIMARY KEY,\n    command_name VARCHAR(50) UNIQUE NOT NULL\n);\n\n-- Tabela de arestas\nCREATE TABLE edges (\n    edge_id INT AUTO_INCREMENT PRIMARY KEY,\n    word_id1 INT,\n    word_id2 INT,\n    command_id INT,\n    FOREIGN KEY (word_id1) REFERENCES words(word_id),\n    FOREIGN KEY (word_id2) REFERENCES words(word_id),\n    FOREIGN KEY (command_id) REFERENCES commands(command_id)\n);\n<\/code><\/pre>\n\n\n\n
                              Nesta estrutura:<\/p>\n\n\n\n