INSTITUTO FEDERAL DE EDUCAO CINCIA E TECNOLOGIAACADMICA: THAIANA
GRECIA V. SOUSA PERODO: 8 CURSO: LICENCIATURA EM COMPUTAO
DISCIPLINA: TEORIA DOS GRAFOS PROFESSOR: JNIO CARLOS
IDENTIFIQUE O SIGNIFICADO DOS SEQUINTES CONCEITOS: Ordem de um
grafo Grau de um n Grafo completo Grafo regular Grafo bipartido
Grafo conexoOrdem de um grafo: A ordem de um grafo G dada pela
cardinalidade do conjunto de vrtices, ou seja a ordem de um grafo a
quantidade de vrtices que existe neste grafo. No exemplo a seguir a
ordem de G = 2.
Grau de um n: O grau dado pelo nmero de arestas que lhe so
incidentes. O grau denotado por deg (i) e o nmero |E(i)| de arestas
em i. Um n quando possui um grau 0 um n isolado. No exemplo grfico
abaixo o N 2 possui grau 4, enquanto o n 6 possui grau 2 e o n 4
possui grau 0 por ser um n isolado.
Grafo completo: Um grafo pode ser denominado como um grafo
completo quando existe uma aresta entre cada par de seus vrtices.
Estes grafos so designados por Kn, onde n a ordem do grafo. Um
grafo Kn possui o nmero mximo possvel de arestas para um dado n. Em
outras palavras, um grafo completo um grafo simples que contm o
nmero mximo de arestas.
No exemplo grfico acima, todas as possibilidades de conexo com
os ns esto sendo feitas. Grafo regular: Define-se grafo regular, o
grafo onde cada vrtice tem o mesmo grau ou valncia. Um grafo
direcionado regular tambm possui a caracterstica de satisfazer a
condio mais forte de que o grau de entrada e o grau de sada de cada
vrtice seja iguais uns aos outros. Abaixo, um exemplo grfico de um
grafo regular, pois todas as vrtices possuem grau de valor 3.
Grafo bipartido: Um grafo denominado bipartido quando seu
conjunto de vrtices V puder ser particionado em dois subconjuntos
V1 e V2, tais que todas as arestas do grafo G une um vrtice de V1 a
outra de V2. So dois conjuntos que se relacionam entre si, mas no h
conexo entre os atores dentro de um mesmo conjunto, ou seja, as
relaes so formadas de um grupo para outro e no dentro de um mesmo
grupo. Exemplo: Suponha que o conjunto de atores seja formado por
professores-tutores e que alunos utilizam a ferramenta da tutoria.
Em um dos conjuntos estaro os professores e no outro os alunos, e
as ligaes sero as diversas perguntas e respostas. Nem todos os
alunos estabelecem comunicao com todos os professores, e nem todos
os professores respondem a todos os alunos. Se houvesse ligaes de
todos os atores de um conjunto com todos os atores do outro, seria
um grafo bipartido completo.A seguir o exemplo grfico de grafo
bipartido, e grafo bipartido completo.
Grafo conexo: Um grafo conexo se, para qualquer par de vrtices
existirem um caminho para chegar de uma extremidade a outra. Se no
existir um caminho entre um n X do grafo e qualquer outro n Y desse
mesmo grafo, ento este grafo chamado desconexo. O exemplo grfico a
seguir mostra essa definio.
Para sair de um determinado n para outro n, podemos perceber que
existem caminhos disponveis.
REFERENCIAS BIBLIOGRFICASFEOFLOFF, P. et al. Uma Introduo
Sucinta Teoria dos Grafos. So Paulo, 2004. Conceitos Bsicos da
Teoria dos Grafos. Disponvel em Acesso em 30 de Maro de 2015.
PRESTES, Edilson. Teoria dos Grafos. S/A . Disponvel em Acesso em
30 de Maro de 2015.
