Conceitos de grafos

Disponível somente no TrabalhosFeitos
  • Páginas : 5 (1162 palavras )
  • Download(s) : 0
  • Publicado : 30 de outubro de 2011
Ler documento completo
Amostra do texto
Engenharia de software
TRABALHO DE CONCEITOS DE GRAFOS
Nome: Marcelo Rosan Silva Vargas
Matricula:111152380
Grafo Completo :
Um grafo é dito ser completo quando há uma aresta entre cada par de seus vértices. Estes grafos são designados por Kn, onde n é a ordem do grafo.
Um grafo Kn possui o número máximo possível de arestas para um dados n. Ele é, também regular-(n-1) pois todos osseus vértices tem grau n-1.

Grafo Bipartido:
É o grafo cujos vértices podem ser divididos em dois conjuntos ,nos quais não há arestas entre vértices de um mesmo conjunto.Para um grafo ser bipartido ele não pode conter circuitos de comprimento ímpar.

1. Se um grafo G é bipartido, todo o circuito de G possui comprimento par.
Sejam V1 e V2 os dois conjuntos em que, de acordo com a definição degrafo bipartido, se particiona V(G). Toda a aresta de G conecta um vértice em V1 com outro em V2. Assim sendo, se X for um vértice de V1, para “voltar” a esse vértice terá de se ir a V2 e voltar a V1 um número indeterminado de vezes, e de cada vez serão percorridas duas arestas, uma de um vértice em V1 para um vértice em V2 e outra de um vértice em V2 para um vértice em V1. Logo, o número dearestas a percorrer será par, ou seja, o comprimento do circuito é par.

2. Se todo o circuito de um grafo G possui comprimento par, então o grafo é bipartido.
Seja G um grafo em que todo o circuito tem comprimento par, e seja X um vértice de G. Denotemos por V1 o conjunto formado por X e por todos os vértices cuja distância a X é par. Seja V2 = V(G)\V1 (isto é, o conjunto formado pelos vértices deG que não pertencem a V1). Pretende mostrar-se que não existe qualquer aresta que conecte vértices de V1 ou vértices de V2. Suponhamos a existência de tal aresta, isto é, suponhamos a existência de dois vértices em V1 (ou V2), digamos Xi e Xj, conectados por uma aresta. Ora existe já um caminho de comprimento par entre Xi e Xj, já que existem caminhos, ambos de comprimento par (ou ímpar, no casode Xi e Xj pertencerem a V2), entre Xi e X e entre X e Xj. Se a esse caminho juntarmos a aresta {Xi;Xj} obtemos um circuito de comprimento ímpar o que contraria a hipótese de apenas existirem circuitos de comprimento par.

Grafo bipartido completo :
é o grafo bipartido, cujo qualquer vértice do primeiro conjunto é adjacente a todos vértices do segundo conjunto.

Subgrafo :
Em teoria dosgrafos, um subgrafo de um grafo G é um grafo cujo conjunto de vértices é um subconjunto do conjunto de vértices G e o conjunto de arestas é um subconjunto do conjunto de arestas de G[1], ou seja, cuja relação de adjacência é um subconjunto de G restrita a esse subconjunto. Dizemos que um grafo G contém um outro grafo H se algum subgrafo de G é H ou é isomorfo a H.
Caminho de um grafo:
Caminho é umasequência de vértices tal que de cada um dos vértices existe uma aresta para o vértice seguinte. Um caminho é chamado simples se nenhum dos vértices no caminho se repete. O comprimento do caminho é o número de arestas que o caminho usa, contando-se arestas múltiplas múltiplas vezes. O custo de um caminho num grafo balanceado é a soma dos custos das arestas atravessadas. Dois caminhos sãoindependentes se não tiverem nenhum vértice em comum, excepto o primeiro e o último.
Tipos de caminho:
Caminho Euleriano:
Em um grafo é o caminho que usa cada aresta exatamente uma vez. Se tal caminho existir, o grafo é chamado traversável. Um ciclo euleriano é um ciclo que usa cada aresta exatamente uma vez.
Caminho Hamiltoniano:
Em um grafo é o caminho que visita cada vertice exatamente uma vez.Um ciclo hamiltoniano é um ciclo que visita cada vértice uma só vez. O grafo do exemplo contém um caminho hamiltoniano. Enquanto determinar se um dado grafo contém um caminho ou ciclo euleriano é trivial, o mesmo problema para caminhos e ciclos hamiltonianos é extremamente árduo.
Ciclo de um grafo:
Um ciclo em teoria de grafos é "um passeio de comprimento mínimo três, em que o primeiro e o...
tracking img