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 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
Carlos Cesar
ResponderExcluirParabéns para cada componente desta equipe, pois vocês conseguiram transmitir esse conteúdo de maneira simples e eficiente levando seus ouvintes ao entendimento.
Nossa equipe realmente trabalhou em equipe para transmitir o assunto de maneira objetiva. Parabéns ao quarteto.Leo.
ResponderExcluirColegas, vcs foram eficientes na explanação do assunto que lhes foi proposto. Parabéns em especial a vc Christiane vc foi nota dez ao transmitir sobre CICLO EULERIANO E CIRCUITO HAMILTONIANO.
ResponderExcluirColegas, vcs foram eficientes na explanação do assunto que lhes foi proposto. Parabéns em especial a vc Christiane vc foi nota dez ao transmitir sobre CICLO EULERIANO E CIRCUITO HAMILTONIANO.
ExcluirVocês estão de parabéns pois,a equipe repassou o conteúdo de fácil entendimento por parte da turma.
ResponderExcluirÉ necessário que se façam algumas correções nas definições. Por exemplo, grafo fortemente conexo.
ResponderExcluirAngélica
ResponderExcluirParabéns para todos, pois vocês demonstraram domínio de conteúdo, além de apresentar o Ciclo Euleriano e circuito Hamiltoniano de forma bastante clara.
A apresentação dos ciclos pela componente merece notas de louvor, pois o entendimento quanto as diferenças no tema foi conciso. Os demais membros também demonstraram segurança no assunto, estabelecendo parâmetros entre a Matemática e a Informática. Parabéns pelo refrão!!!
ResponderExcluirMaria Zenilce
ResponderExcluirO grupo apresentou o trabalho com segurança deixando bem claro a parte da conexidade e clique, estabelecendo parâmetros entre a matemática e a informática. Parabéns!
Esta equipe assim a dos grafos nos fez perceber a importância e o uso dos grafos, só desta vez, formando ciclos, achei muito interessante os exemplos colocados na apresentação, pois nos fez compreender melhor como a internet, por exemplo usa os ciclos para estabelecer conexão entre computadores.
ResponderExcluirNEUCILENE
ResponderExcluirA apresentação do ciclo pelo componente merece nota de louvor pois o entendimento quanto as diferenças do tema foi conciso. Os demais membros também demonstraram segurança no assunto, estabelecendo parâmetros entre a matemática e a informática. Parabéns .
A apresentaçao do grupo foi muito boa, pois quando estava lendo a apostila, nao entendi nada. Mas após a explicação comecei a entender e a gostar.
ResponderExcluirA equipe foi muito eficiente na sua explicação fazendo com que entendessemos o assunto, que parecia um tanto complexo.
ResponderExcluirMARILDA.
ResponderExcluirA EQUIPE LIDERADA PELA CORINA, APRESENTOU DE FORMA EFICIENTE O TRABALHO, UMA VEZ QUE NOS FEZ PERCEBER QUE OS CICLOS EULERIANO E CIRCUITO HAMILTONIANO ESTÃO PRESENTES NOS MAIS DIVERSOS GRAFOS COM OS QUAIS NOS DEPARAMOS HOJE. COMO POR EXEMPLO A ROTA DE UM AVIÃO DE PASSAGEIROS QUE SAI DO SUDESTE DO PAÍS, VEM ATÉ O EXTREMO NORTE A RETORNA AO SUDESTE ESCALANDO DE CAPITAL EM CAPITAL SEM QUE NECESSARIAMENTE TENHA QUE PASSAR DUAS VEZES PELO MESMO AEROPORTO.
A equipe da Corina explanou muito bem o assunto,pois falar de ciclos euleriano e circuito Hamiltoniano com a segurança com que falaram só mesmo para quem é do ramo da matemática e os exemplos dado pela equipe facilitou o entendimento,principalmente quando explicaram da rota de um avião que passa por diferentes rotas sem ter que passar várias vezes pelo mesmo aeroporto. Adriana
ResponderExcluirQuando a colega Cris começõu a falar sobre o Ciclo Euleriano e Circuito Hamiltoniano e que o mesmo é 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, imaginei que jamais entenderia sobre este assunto, mas através de suas expliações as minhas dúvidas foram exclarecidas. Parabéns pela atuação.
ResponderExcluirpaulo rogerio melo e silva
ResponderExcluirO trabalho de ciclo euleriano e circuito hamiltoniano relacionou muito bem suas explicações com dados relacionados a seu assunto e com clareza parabéns
EUSIANE MARIA NUNES SOUZA
ResponderExcluirPARABÉNS A EQUIPE, CONSEGUI ENTENDER MUITO BEM O ASSUNTO EXPLICADO, PRINCIPALMENTE QUANDO O ASSUNTO FOI RELACIONADO A EXEMPLOS PRÁTICOS. FACILITOU MUITO O ENTENDIMENTO.
A equipe conseguiu repassar o conteúdo de forma simples e objetiva utilizando como exemplo os componentes da equipe o que facilitou o entendimento.
Excluir