A Teoria dos Grafos é actualmente uma das áreas mais importantes da matemática discreta. Tendo as suas raízes em jogos e recreações matemáticas, atribui-se a sua criação a Euler, ao resolver o problema das pontes de Konigsberg em 1736, mas foram os problemas acerca de fórmulas de estrutura de compostos químicos, que A. Cayley resolveu na segunda metade do século XIX, que a começaram a desenvolver. Hoje, a Teoria dos Grafos tem sido aplicada a muitas áreas (Informática, Investigação Operacional, Economia, Sociologia, Genética, etc.), pois um grafo constitui o modelo matemático ideal para o estudo das relações entre objectos discretos de qualquer tipo.
Em matemática e ciência da computação, o grafo é o objeto básico de estudo da teoria dos grafos. Tipicamente, um grafo é representado como um conjunto de pontos (vértices) ligados por retas (as arestas). Dependendo da aplicação, as arestas podem ser direcionadas, e são representadas por "setas".
Os grafos são muito úteis na representação de problemas da vida real, em vários campos profissionais. Por exemplo, pode-se representar um mapa de estradas através dos grafos e usar algoritmos específicos para determinar o caminho mais curto entre dois pontos, ou o caminho mais económico. Assim, os grafos podem possuir também pesos (ou custo), quer nas arestas quer nos vértices, e o custo total em estudo será calculado a partir destes pesos.
Alguns tipos de Grafos
Em qualquer Grafo simples, existe no máximo uma aresta unindo cada par de vértices. No entanto, muitos resultados envolvendo grafos simples podem ser estendidos a grafos mais gerais nos quais dois vértices podem ter várias arestas (arestas múltiplas) unindo-os. Podemos ainda remover a restrição que impõe que as arestas unam vértices distintos, admitindo lacetes, ou seja, arestas unindo um vértice a ele próprio. O grafo daí resultante, no qual lacetes e arestas multiplas são admitidas, diz-se um pseudografo.
Um Grafo dirigido (ou, abreviadamente, digrafo) consiste num conjunto finito não vazio de elementos chamados vértices, e num conjunto finito de arestas orientadas (eventualmente múltiplas), chamadas aros.
Um Grafo não dirigido é um grafo em que as relações entre os nós são simétricas (se existe um arco (A,B) então também existe um arco (B,A), e ambos são representados apenas por uma linha não orientada ligando A e B. Acesso aos nodos não possui uma direção indicada.
Sem comentários:
Enviar um comentário