No meu post optei por falar dos grafos, porque acho que é uma matéria importante para demonstrar que no fundo hoje em dia esta vertente está muito presente no nosso quotidiano. Pois um grafo está sempre relacionado com uma rede, seja rede de amigos ou uma rede de um transporte público.
Podemos dizer que os grafos são utilizados para demonstrar uma rede e são constituídos por nós que por sua vez estão ligados aos arcos. Uma rede é como um padrão de ligações que estão ligados entre si e temos como um exemplo geral, o nosso grupo de amigos.
Os grafos estão divididos em: Vizinhos, que é quando estão ligados directamente por nós; e por Não Vizinhos, que é quando não estão ligados directamente; e ainda por Grafos Dirigidos, que é quando parte informação de um nó para outro; e por fim por Grafos Não Dirigidos, que é quando não parte a informação de um nó para os outros.
Para percebermos melhor os grafos podemos distinguir vários conceitos importantes:
- Caminho: Pode cruzar-se com ele próprio ou não. Quando não há cruzamento diz-se caminho.
- Ciclo: Quando há cruzamento diz-se ciclo. Não pode haver repetição. O primeiro nó é igual ao último.
- Conectividade – Os nós não estão todos ligados entre si.
- Comprimento de um caminho – É a soma de um número de arestas do caminho.
- Distância entre dois nós – É a distância do caminho mais curto que existe entre dois nós.
- Distância de um grafo – É a maior distância que existe entre qualquer dois pares de nós. > Diâmetro.
Como exemplos reais de grafos na vida quotidiana temos o Metro de Lisboa:
http://www.youtube.com/watch?v=KZoIrCxB9ek
http://www.youtube.com/watch?v=PXYT3opZIyc
http://www.metrolisboa.pt/Default.aspx?tabid=79
Com base nestas hiperligações podemos concluir que muitos problemas podem ser modelados por grafos cujas arestas têm associadas a si uma determinada ponderação. Por exemplo, considere-se uma linha de metro, onde o grafo básico tem como vértices os locais de cada cidade por onde o metro passa e essas paragens são as arestas. A ponderação nas arestas pode ser feita de variadas formas, nomeadamente, atendendo às distâncias entre os locais da cidade, o tempo de uma viagem do metro ou o custo de cada viagem.
Um grafo que tenha associado a cada aresta um número é um grafo ponderado. Um caso análogo ao da linha do metro é a de uma rede de computadores em várias cidades; a cada aresta pode ser associado a distância entre os computadores, o tempo de resposta ou o custo da comunicação.
Podemos dizer que os grafos são utilizados para demonstrar uma rede e são constituídos por nós que por sua vez estão ligados aos arcos. Uma rede é como um padrão de ligações que estão ligados entre si e temos como um exemplo geral, o nosso grupo de amigos.
Os grafos estão divididos em: Vizinhos, que é quando estão ligados directamente por nós; e por Não Vizinhos, que é quando não estão ligados directamente; e ainda por Grafos Dirigidos, que é quando parte informação de um nó para outro; e por fim por Grafos Não Dirigidos, que é quando não parte a informação de um nó para os outros.
Para percebermos melhor os grafos podemos distinguir vários conceitos importantes:
- Caminho: Pode cruzar-se com ele próprio ou não. Quando não há cruzamento diz-se caminho.
- Ciclo: Quando há cruzamento diz-se ciclo. Não pode haver repetição. O primeiro nó é igual ao último.
- Conectividade – Os nós não estão todos ligados entre si.
- Comprimento de um caminho – É a soma de um número de arestas do caminho.
- Distância entre dois nós – É a distância do caminho mais curto que existe entre dois nós.
- Distância de um grafo – É a maior distância que existe entre qualquer dois pares de nós. > Diâmetro.
Como exemplos reais de grafos na vida quotidiana temos o Metro de Lisboa:
http://www.youtube.com/watch?v=KZoIrCxB9ek
http://www.youtube.com/watch?v=PXYT3opZIyc
http://www.metrolisboa.pt/Default.aspx?tabid=79
Com base nestas hiperligações podemos concluir que muitos problemas podem ser modelados por grafos cujas arestas têm associadas a si uma determinada ponderação. Por exemplo, considere-se uma linha de metro, onde o grafo básico tem como vértices os locais de cada cidade por onde o metro passa e essas paragens são as arestas. A ponderação nas arestas pode ser feita de variadas formas, nomeadamente, atendendo às distâncias entre os locais da cidade, o tempo de uma viagem do metro ou o custo de cada viagem.
Sem comentários:
Enviar um comentário