"O comprimento do passeio P se dá pelo nº de arestas percorridas (K)". O comprimento de um ciclo é igual a K ou K-1, já que um vértice ele percorreu 2 vezes?
O comprimento de um ciclo que percorre o grafo é igual a k-1, mas como ele percorre 1 vértice duas vezes, então ele percorreu (k-1 + 1), ou seja, percorreu K arestas.
Na teoria dos grafos , um ciclo é um caminho de arestas e vértices em que um vértice é acessível a partir de si mesmo. Existem vários tipos diferentes de ciclos, principalmente uma caminhada fechada e um ciclo simples ; também, por exemplo, um elemento do espaço do ciclo do gráfico. Se um gráfico não contém ciclos, ele é chamado de acíclico.
Um passeio fechado consiste em uma seqüência de pelo menos dois vértices , começando e terminando no mesmo vértice, com cada dois vértices consecutivos na seqüência adjacente um ao outro no gráfico. Em um grafo direcionado, cada aresta deve ser percorrida pela caminhada de forma consistente com sua direção: a aresta deve ser orientada desde o início de dois vértices consecutivos até o último dos dois vértices na seqüência.
A escolha do vértice inicial não é importante: percorrer a mesma seqüência cíclica de arestas a partir de diferentes vértices iniciais produz o mesmo caminho fechado. Assim, o comprimento do ciclo será igual a K+1.
Na teoria dos grafos , um ciclo é um caminho de arestas e vértices em que um vértice é acessível a partir de si mesmo. Existem vários tipos diferentes de ciclos, principalmente uma caminhada fechada e um ciclo simples ; também, por exemplo, um elemento do espaço do ciclo do gráfico. Se um gráfico não contém ciclos, ele é chamado de acíclico.
Um passeio fechado consiste em uma seqüência de pelo menos dois vértices , começando e terminando no mesmo vértice, com cada dois vértices consecutivos na seqüência adjacente um ao outro no gráfico. Em um grafo direcionado, cada aresta deve ser percorrida pela caminhada de forma consistente com sua direção: a aresta deve ser orientada desde o início de dois vértices consecutivos até o último dos dois vértices na seqüência.
A escolha do vértice inicial não é importante: percorrer a mesma seqüência cíclica de arestas a partir de diferentes vértices iniciais produz o mesmo caminho fechado. Assim, o comprimento do ciclo será igual a K+1.
Para escrever sua resposta aqui, entre ou crie uma conta
Fundamentos de Algoritmos para Computação
•ESTÁCIO
Fundamentos de Algoritmos para Computação
•ESTÁCIO
Fundamentos de Algoritmos para Computação
Compartilhar