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.
*
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.
O numero
de arestas num caminho é o comprimento desse caminho.
