Como minha monografia tem o objetivo de estudar a aplicabilidade dos AGraphs em sistemas de transformações de grafos, antes de entrar efetivamente em transformações de grafos, venho aqui dar uma introdução básica a grafos.
Grafos são um dos mais importantes objetos de estudos na ciência da computação. São formados por nós (na figura, os nós são os círculos) e arestas que interligam esses nós. Basicamente, eles são capazes de representar uma informação qualquer. Por exemplo, um mapa de estradas é muito bem representado por um grafo. Nesse caso, os nós seriam as cidades e as arestas seriam as estradas que interligam essas cidades. Outros exemplos podem ser: uma rede de computadores (cpu e cabos de rede), uma estrutura de um site (páginas html e links que ligam a outros html´s), o Orkut (o que seriam os nós e o que seriam as arestas?), enfim, tudo que possui uma dependência entre elementos e dados pode ser representado por um grafo.
Mais formalmente, um grafo consiste de um conjunto de vértices V e um conjunto de arestas E, direcionadas ou não, onde cada aresta 'e' em E tem um vértice origem s(e) e um vértice alvo t(e) em V. Uma aresta não direcionada que sai do vértice A e chega ao vértice B é igual a uma aresta que sai de B e chega em A. Já num grafo direcionado, que chamamos de digrafo, as duas direções são contadas como sendo arestas distintas.
Assim como toda estrutura de dados na ciência da computação, grafos armazenam informações. Se eles armazenam, também tem que ser possível acessar tais informações. A tarefa de acessar um dado se resume em varrer o grafo, nó a nó, enquanto não encontramos o dado buscado.
Enfim, os grafos têm como uma das principais vantagens a representação visual de informações. Eles também já foram estudados em demasiado e já são muito bem compreendidos pelos pesquisadores. Como já disse, fornecem uma abordagem simples e poderosa a uma variedade de problemas típicos na ciência da computação, permitindo manipulações eficientes das informações neles armazenadas.
Provavelmente, o próximo post será sobre transformações de grafos. Na verdade, esse é o principal alvo da minha monografia, mas para chegar aí, eu tive de dar uma introdução básica a grafos.
Até o próximo post!
Nenhum comentário:
Postar um comentário