CICLO EULERIANO E CIRCUITO HAMILTONIANO

INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO PARÁ
PLANO NACIONAL DE FORMAÇÃO DE PROFESSORES
LICENCIATURA EM INFORMÁTICA
MATEMÁTICA PARA COMPUTAÇÃO

PROF. Francisco Robson
CORINA ROCHA DA SILVA
CHRISTIANE ADELE PANTOJA WILHAMS
LEOZETE DO CARMO BATISTA
PEDRO PAULO MOTA FIGUEIRA

CICLO EULERIANO E CIRCUITO HAMILTONIANO

Ciclo Euleriano e Circuito Hamiltoniano
Um ciclo que passa por todas as arestas de um grafo é dito Euleriano e um circuito elementar que passa por todos os vértices é chamado Hamiltoniano.

GRAFO CONEXO
Um Grafo G= (V,E) é CONEXO se para todo par de vértices existe pelo menos uma cadeia entre eles. A figura a seguir mostra um grafo conexo

 
GRAFO DESCONEXO
Um Grafo é desconexo se existir pelo menos um par de vértices que não é unido por nenhuma cadeia como mostra a figura abaixo:

O conceito de conexidade em grafos orientados não exige que haja um caminho ligando qualquer par de vértices, se isto acontecer diz-se que o grafo é FORTEMENTE CONEXO.

Um grafo é fortemente conexo (f-conexo) se todo par de vértices está ligado por pelo menos um caminho em cada sentido, ou seja, se cada par de vértices participa de um circuito. Isto significa que cada vértice pode ser alcançável partindo-se de qualquer outro vértice do grafo. O grafo abaixo é fortemente conexo.

Como aplicação deste conceito, podemos dizer que uma das características mais importantes de uma rede de comunicação (telefonia, por exemplo), é sua conexidade.

RELAÇÃO DE ADJACÊNCIA E INCIDÊNCIA
Dois vértices vєV e wєV de um grafo G= (V,E) são ditos adjacentes se existe a aresta (v,w), ou seja, (v,w)є E.
Duas arestas são ditas adjacentes se possui uma extremidade (vértice) comum.
Uma aresta é incidente a um vértice se este vértice for uma de suas extremidades. É o caso dos vértices Pedro Paulo e Leozete no grafo abaixo.
Assim as arestas (u,v) e (v,w) são incidentes ao vértice “V”.

 CLIQUE
Clique ou grafo completo é um grafo, ou subgrafo, em que seus vértices são interligados ou adjacentes dois a dois; de forma que o caminho mais curto entre quaisquer dois vértices “v” e “w” é a aresta (v,w).
A figura abaixo mostra um grafo com dois cliques:

Qual a importância computacional do uso dos grafos?
É bastante abrangente o uso de grafos na computação em áreas como: Análise de planejamento de projetos; Cibernética; Redes de computadores; Circuitos eletrônicos. Veja as figuras abaixo:

 

Rede de computadores

Circuito Eletrônico

TEORIA DOS GRAFOS

                                                                                                                                      

INSTITUTO FEDERAL, EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO PARÁ-IFPA  CAMPUS SANTARÉM
            LICENCIATURA PLENA EM INFORMÁTICA – PARFOR
MATEMÁTICA PARA COMPUTAÇÃO
PROFESSOR: FRANCISCO ROBSON ALVES

Teoria dos Grafos

Equipe: 07

Adriana Christina Macêdo da Silva, Lindalva da Silva Ferreira, Maria Silvana Ferreira Chaves, Raimunda Cristiane Lira da Silva

Como Surgiu a Teoria dos Grafos?

A teoria dos Grafos surgiu com os trabalhos de L. Euler, G. Kirchhoff e A. Cayley.

¬ Esta teoria tem sido utilizada largamente em diferentes áreas da biologia, química e na matemática aplicada.

¬ O problema das pontes de Königsberg é o primeiro e mais famoso problema em teoria dos grafos resolvido por Euler em 1736.

O problema consiste em determinar se é possível ou não fazer um passeio pela cidade começando e terminando no mesmo lugar, cruzando cada ponte exatamente uma única vez.

1736: Euler foi o primeiro a representar esse problema usando grafos depois desta época pouca coisa foi investigada em teoria dos grafos por quase um século.

• O interesse ressurgiu na década de 20 com os estudos de D. Konig que se transformaram em um livro, publicado em 1936.

O que é um grafo?

“Um grafo é um conjunto de pontos, chamados vértices, conectados por linhas, chamadas de arestas”

Formação dos Grafos

• Os grafos são formados por:

– Vértices - conjunto V;

– Arestas – conjunto A;

• Formalmente descrito como:

– G=(V,A)

Grafo Direcionado ou Dígrafos

     Um dígrafo (= um grafo direcionado) consiste em dois conjuntos: um conjunto vértices e outro de arcos. Cada arco é um par ordenado de vértices. O primeiro vértice é o início e o segundo é o fim do arco.
     Um arco com início em v e final em w será denotado por v-w (isto não é uma subtração). Existir um arco que liga o vértice v ao vértice w não significa que existe um arco que liga o vértice w ao vértice v.

     Se v-w existe então dizemos que w é vizinho (ou adjacente) de v.

Um dígrafo é simétrico se cada um de seus arcos é anti-paralelo* a algum outro arco.
*arcos anti-paralelos: Para um arco v-w temos também um arco w-v, estes dois arcos são anti-paralelos.

Grau de entrada e de saída
O grau de saída de um vértice v em um dígrafo é o número de arcos que começam em v. O grau de entrada de um vértice v em um dígrafo é o número de arcos que terminam em v.
Uma fonte é um vértice que tem grau de entrada nulo (= 0) e um sorvedouro é um vértice que tem grau de saída nulo (= 0).
Um vértice é isolado se seu grau de entrada e seu grau de saída são ambos nulos.

Grau de entrada e de saída
O grau de saída de um vértice v em um dígrafo é o número de arcos que começam em v. O grau de entrada de um vértice v em um dígrafo é o número de arcos que terminam em v.
Uma fonte é um vértice que tem grau de entrada nulo (= 0) e um sorvedouro é um vértice que tem grau de saída nulo (= 0).

Um vértice é isolado se seu grau de entrada e seu grau de saída são ambos nulos.

Grafos valorados (Redes ≡ Networks)

Em grafos valorados, a cada arco (ou nó) de G é associado um valor numérico, ou peso.

               Uma Rede é um grafo não-direcionado (ou um dígrafo) no qual um número real é associado os vértices e/ou ligações. Este número é freqüentemente referido como o peso da ligação. Essa classificação é dada de acordo com a necessidade, ou não, da indicação do fluxo entre os vértices.

Em grafos valorados, a cada arco (ou nó) de G é associado um valor numérico, ou peso.

               GRAFO VALORADO

Um grafo  G(V,A) é dito ser valorado quando existe uma ou mais funções relacionando V e/ou A com um conjunto de números. Para exemplificar (ver o grafo G₇), seja G(V,A) onde:

•        V = {v | v é uma cidade com aeroporto}

•        A = {(v,w,t) | <há linha aérea ligando v a w, sendo t o tempo esperado de voo>} 

TIPOS DE RELAÇÃO

Os elementos de um conjunto ou os elementos de conjuntos diferentes frequentemente apresentam ligações entre si que podem ser descritas como uma relação. Tais relações apresentam quatro tipos distintos. São elas a Relação Funcional, a Injetora, a Total e a Sobrejetora.        

A equipe formada pelos acadêmicos do Curso de Licenciatura Plena em Informática do Instituto Federal de Educação, Ciência e Tecnologia do Pará- IFPA,    Maria Angélica, Jose Ribamar, Marcos Moda, Marilda Silva e Carlos Cesar, produziram um material de apoio como pré requisito para obtenção de nota na disciplina Matemática para Computação, ministrada pelo Prof. Msc. Francisco Robson

Acreditamos que o referido material pode auxiliar outros acadêmicos de cursos afins a compreenderem melhor como os tipos de ralação se apresentam no diagrama de Venn . 

Convidamos os alunos do curso de Licenciatura em Informática a acessarem o material através do link abaixo e fazerem comentários sobre nosso trabalho.                                                                   

Clic aqui para ter acesso ao material completo

RELAÇÕES

NSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO PARÁ

CAMPUS SANTARÉM

PROGRAMA NACIONAL DE FORMAÇÃO DE PROFESSORES

LICENCIATURA EM INFORMÁTICA

MATEMÁTICA PARA COMPUTAÇÃO

Prof. Francisco Robson

Alunos:

Clea de Andrade Mato

Noely Ramos

Reizivaldo Lima

RELAÇÕES 

Uma relação é uma correspondência existente entre dois conjuntos não vazios. Por exemplo, dois conjuntos A e B. O conjunto A denominado conjunto origem e o conjunto B é denominado conjunto destino.

                                                 CONJUNTO ORIGEM            CONJUNTO DESTINO

PAR ORDENADO   

 

Chamamos de par todo conjunto formado por dois elementos.

Par ordenado é todo conjunto com dois elementos distintos, onde para cada elemento a e cada elemento b, admite-se a existência de um terceiro elemento (a,b), de modo que se tenha:

(a,b) = (c,d) <=> a = c e b = d

 

Indicamos por (x, y) o par ordenado formado pelos elementos x e y, onde x é o 1º elemento (abscissa) e y é o 2º elemento (ordenada).

 

Observações:

 

1. De um modo geral, sendo x e y dois números racionais quaisquer, temos:

(x, y) ≠ (y, x)

2.   Dois pares ordenados (x,  y) e (r, s) são iguais somente se    x = r   e    y = s.

PRODUTO CARTESIANO

 

O produto cartesiano de dois conjuntos A e B são todos os pares ordenados (x, y) sendo que x pertence ao conjunto A e y ao conjunto B.

 

Vamos tomar como exemplo os seguintes conjuntos A e B:

 

A= {1,2} B={3,5,7}

 

O produto cartesiano de A por B, representado por A x B é igual a:

 

A x B= {(1,3), (1,5), (1,7), (2,3), (2,5), (2,7),}. Representação através do diagrama de flechas. 

 

RELAÇÃO BINÁRIA

 

Dados dois conjuntos A e B, chama-se relação binária de A em B todo subconjunto R de A e B.

Uma relação binária em um conjunto S é formalmente um subconjunto de s x s, tal relação é chamada de auto-relação.

Exemplos:

1. Se A={1,2,3,4,5} e B={1,2,3,4,}, quais são os elementos da relação R={(x,y)│x<y} de A em B?

R={(1,2,), (1,3), (1,4), (2,3),(2,4), (3,4)} .

 

Em outras palavras, uma relação binária é definida como sendo um subconjunto do produto cartesianoentre os conjuntos A e conjunto B. Isto é, uma relação R é um conjunto de pares ordenados. 

 

DOMÍNIO E IMAGEM  

Seja R uma relação de A em B.

 

Chama-se Domínio de R o conjunto D de todos os primeiros elementos dos pares ordenados pertencentes a R.

 

Chama-se Imagem de R o conjunto IM de todos os segundos elementos dos pares ordenados pertencentes a R.

Referências Bibliográficas

BACCARO, Nelson.matemática volume 1.São Paulo: Atica,s/d

 

Disponível em: http://www.somatematica.com.br/fundam/paresord.php, acesso em 15 de fevereiro de 12.

 

Disponível em : http://pt.wikipedia.org/wki/Relacao_(matematica),acesso em 15 de fevereiro de 2012

GRAFOS PLANARES E ÁRVORE

 

GRAFOS PLANARES E ÁRVORE
Teoria dos grafos
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
Grafo com 4 vértices e 6 arestas. É um grafo completo, conexo e planar.
.



    Um grafo diz-se planar se for possível desenhá-lo de tal forma que duas arestas não se intersectem à excepção nos vértices inicial e final. Por exemplo, o cubo é um grafo planar já que pode ser desenhado como:
   


•    Na teoria dos grafos, uma árvore é um grafo conexo (existe caminho entre quaisquer dois de seus vértices) e acíclico (não possui ciclos). Caso o grafo seja acíclico mas não conexo, ele é dito uma floresta. Uma floresta também é definida como uma união disjunta de árvores.
•    Árvores e Grafos são compostos essencialmente por nós e arestas (ou conexões, se assim preferir chamar) entre eles.
•    Um grafo pode conter ciclos (ou seja, há um caminho saindo de um nó que leva, por meio de outros nós, até ele novamente) ou não. Quando um grafo é conexo e acíclico (isto é, sem ciclos), diz-se que se tem uma árvore.


Uma árvore contendo nove nós, sendo o nó 1 o nó-raiz e os nós 3, 5, 6, 7, 8 e 9 nós-folhas
•    Na imagem anterior, podemos dizer que há três níveis: o primeiro, onde se encontra o nó-raiz 1; o segundo, onde se encontram os nós 2, 3 e 4, filhos do nó-raiz; e o terceiro, onde se encontram os nós 5, 6, 7, 8 e 9, filhos dos filhos do nó-raiz.

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.