Jump to content
carlos.p

Teoria de Grafos - Diferença entre caminho e cadeia

Recommended Posts

carlos.p

Boas,

Estou a ter alguma dificuldade em diferenciar o conceito de "caminho" e "cadeia" em multigrafos orientados.

As definições simplesmente parecem-me iguais.. =/

Alguém podia iluminar-me?

Cumprimentos,

Carlos

Share this post


Link to post
Share on other sites
jamirooo

Boa tarde,

Aqui parece que está a explicar de forma simples a diferença entre ambos: http://www.inf.ufsc.br/grafos/definicoes/definicao.html.

Passo a citar:

"CADEIA

    Uma cadeia é uma sequência qualquer de arestas adjacentes que ligam dois vértices. O conceito de cadeia vale também para grafos orientados, bastando que se ignore o sentido da orientação dos arcos. (...)

    Uma cadeia é dita ser elementar se não passa duas vezes pelo mesmo vértice.

    É dita ser simples se não passa duas vezes pela mesma aresta (arco).

    O comprimento de uma cadeia é o número de arestas (arcos) que a compõe.

CAMINHO

    Um caminho é uma cadeia na qual todos os arcos possuem a mesma orientação. Aplica-se, portanto, somente a grafos orientados..."

Share this post


Link to post
Share on other sites
carlos.p

Obrigado jamirooo. Isso torna tudo mais claro. Tenho um exemplo teórico de cadeia que realmente não percebia, e olhando para as coisas assim já faz sentido. :)

Então uma cadeia sob um multigrafo orientado é como se fosse uma cadeia sob o seu subjacente.

Gratzi novamente. :)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.