Teoria dos grafos

TEORIA DOS GRAFOS

1.GRAFO PARCIAL

2. SUBGRAFO

3.GRAFO COMPLETO

4.GRAFO BIPARTIDO

5. CAMINHO,PERCURSO,CICLO,CIRCUITO E COMPRIMENTO

ANA CLAUDIA  BERNANDES MONTEIRO

EUSIANE MARIA  NUNES DE SOUZA

ZELIETE SOCORRO DOS SANTOS PARINTINS

A teoria dos grafos é um ramo da matemática que estuda as relações entre os objetos de um determinado conjunto.

Grafo é uma estrutura G(V,A) onde V é um conjunto não vazio de objetos denominados vértices e A é um conjunto de pares não ordenados de V, chamado arestas.

É uma noção simples, abstrata e intuitiva, usada para representar a idéia de alguma espécie de relação entre os “objetos”. Graficamente, aparece representado por uma figura com nós ou vértices, significando o objetos, unidos por um traço denominado aresta configurando a relação imaginada.

Assim, o nó ou vértice é a unidade fundamental da qual os grafos são formados e a aresta serve para conectar os vértices.Sendo que a cada elemento de uma rede é associado um nó (ou vértice) e a ligação entre os nós se dá por meio de uma aresta. 

 Um Grafo é representado

matematicamente por:G=(V,E) 

Onde V é o conjunto de vértices e E é o 

conjuntos de arestas ou ligações entre os 

vértices. (V= n , E= m )

 

 

1.GRAFO PARCIAL 

Grafo parcial de um grafo G é um subgrafo com o mesmo conjunto de vértices que G. Uma árvore parcial é um grafo parcial que é árvore. Todo grafo tem pelo menos uma árvore parcial.

 

 

   

 

2.SUBGRAFO

 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, 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. Dois grafos são isomorfos se um pode se transformar em outro simplesmente renomeando-se os vértices.

3.GRAFO COMPLETO

 

 Um grafo completo é um grafo simples em que todo vértice é adjacente a todos os outros vértices. O grafo completo de n vértices é frequentemente denotado por Kn.

 O grafo Kn tem arestas (correspondendo a todas as possíveis escolhas de pares de vértices).

 

4.GRAFO BIPARTIDO

 Um grafo bipartido ou bigrafo é um grafo cujos vértices podem ser divididos em dois conjuntos disjuntos U e V tais que toda aresta conecta um vértice em U a um vértice em V;ou seja, U e V são conjuntos independentes. Equivalentemente, um grafo bipartido é um grafo que não contém qualquer ciclo de comprimento ímpar.

 

5.CAMINHO, PERCURSO, CICLO, CIRCUITO E COMPRIMENTO 

Caminho é uma sequência de vértices onde em cada um dos vértice existe uma aresta para o vértice seguinte. O termo  percurso serve para denominar genericamente um caminho.

 

O numero de arestas num caminho é o comprimento desse caminho.

 

 

  * Este é o resultado de uma pesquisa socializada na Disciplina de Matematática para a Computação, no Curso de Licenciatura em Informática, no IFPA (Institututo Federal DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO PARÁ/CAMPUS SANTARÉM/PROGRAMA NACIONAL DE FORMAÇÃO DE PROFESSORES, sob a orientação do Prof. Francisco Robson Alves.