Teoria dos Grafos - Introdução
No domínio da matemática e da ciência da computação, a teoria dos grafos é o estudo dos grafos que se preocupa com a relação entre arestas e vértices . É um assunto popular com suas aplicações em ciência da computação, tecnologia da informação, biociências, matemática e lingüística, para citar alguns. Sem mais delongas, vamos começar definindo um gráfico.
O que é um gráfico?
Um gráfico é uma representação pictórica de um conjunto de objetos onde alguns pares de objetos são conectados por links. Os objetos interconectados são representados por pontos denominados comovertices, e os links que conectam os vértices são chamados edges.
Formalmente, um gráfico é um par de conjuntos (V, E), Onde Vé o conjunto de vértices e E é o conjunto de arestas, conectando os pares de vértices. Dê uma olhada no gráfico a seguir -
No gráfico acima,
V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}
Aplicações da Teoria dos Grafos
A teoria dos grafos tem suas aplicações em diversos campos da engenharia -
Electrical Engineering- Os conceitos da teoria dos grafos são amplamente usados no projeto de conexões de circuitos. Os tipos ou organização de conexões são nomeados como topologias. Alguns exemplos de topologias são topologias em estrela, ponte, série e paralela.
Computer Science- A teoria dos grafos é usada para o estudo de algoritmos. Por exemplo,
- Algoritmo de Kruskal
- Algoritmo de Prim
- Algoritmo de Dijkstra
Computer Network - As relações entre computadores interligados na rede seguem os princípios da teoria dos grafos.
Science - A estrutura molecular e a estrutura química de uma substância, a estrutura do DNA de um organismo, etc., são representadas por gráficos.
Linguistics - A árvore de análise de um idioma e a gramática de um idioma usa gráficos.
General- As rotas entre as cidades podem ser representadas por meio de gráficos. A representação de informações ordenadas hierárquicas, como a árvore genealógica, pode ser usada como um tipo especial de gráfico chamado árvore.