Caminho de Euler e Circuito Hamiltoniano em Grafos

        para cada vértice v:
            grau[v] = soma da linha v da matriz de adjacência
            se grau[v] for ímpar: contadorImpares++
        se contadorImpares == 0 ou 2 → caminho de Euler existe
        senão → não existe
        

Texto original

O texto original pode conter falhas de gramática ou de concordância, isso ocorre porque ele foi obtido por um processo de extração de texto automático.

Texto extraído do video Fundamentos Matemáticos para Computação - Caminho de Euler e Circuito Hamiltoniano

Olá, alunas e alunos do curso de Fundamentos Matemáticos para a Computação.
Nesta videoaula, eu vou falar sobre o caminho de Oiler e circuito amuntaneado.
Eu vou estabelecer o problema do caminho de Oiler e, em seguida, um problema do circuito amuntaneado.
No caso do caminho de Oiler, essa situação é uma pequena cidade chamada de Coinsberde, mas não tive a aprocia.
Onde o matemático Leonardo Oiler foi convocado para tentar encontrar uma solução onde estaria possível.
Visitar todos os pontos da cidade, a travesção do cada uno das fontes, uma única vez, no caso 7 pontos.
E, olha, na época de desenvolver o que foi chamado de geometria da posição, para justificar a inrebilidade de se fazer tal pravesse, de se percorrer, usar-vos uma única vez para visitar cada ponto da cidade.
E ele estabeleceu, então, que foi conhecido como caminho de Oiler em um gravo, que é um caminho que usa cada ar com o inger exatamente uma vez.
Por exemplo, se observamos aqui, eu consigo ouvir desse ponto para esse, atravessando esse ar para essa ponte daqui para cá também.
E eu poderia usar essa ponte para chegar aqui.
Eu poderia também prosseguir para cá, só que eu estou deixando de visitar, para atravessar essa ponte.
Se eu e eu tenho que visitar para avisar cada ponto pelo menos uma vez.
Se eu tentar fazer isso agora, eu volto para cá e só tenho como continuar o percurso.
Por essa, atravessia que eu já fiz, ou é isso aqui.
Então, ou eu venho para cá, deixando de visitar aqui, ou eu visito aqui, mas eu vou ter que atravessar novamente uma ponte que eu já, vou tirar um ar, porque eu já passei.
Então, a gente observa que nesse gráfico isso não é possível.
Nesse aqui, isso já é viável, porque eu tenho, eu posso seguir um caminho como esse.
Só que aí eu tenho que tomar cuidado, que em determinado momento, eu estou usando uma abordagem aqui de percorrer primeiro, atravessar primeiro os arcos mais estérgicos.
Em determinado momento, eu tenho que começar a percorrer esses arcos mais internos aqui.
Então, por exemplo, faça uma volta aqui, o que é possível, porque eu não estou repetindo arco, eu estou repetindo, não, isso pode.
Então, eu agora atravesso esse outro arco e assim eu continuo percorrendo apenas os arcos internos, apesar de estar repetindo nós, isso não tem problema.
E consigo concluir o meu caminho passando por cada arco, cada ponte nesse caso, uma única vez.
Bom, para a gente poder começar a decidir se um gráfico tem um caminho de poile, é interessante estar no fim, a parte de alguns resultados.
Por exemplo, o número de nós, em qualquer gráfico, é para.
Então, eu vou colocar aqui uma pequena demonstração um pouco mais informal para que a gente sai de essa ideia.
Então, vamos supor um gráfico connexo, porque se não for connexo, não vai ter o caminho de poile.
Onde NI representa o número de nós com grau e, essa é a sora de todos os graus, de todos os graus, de todos os nós no grau.
Então, eu teria basicamente isso aqui.
A quantidade de nós com grau 1, a quantidade de nós com grau 2, a quantidade de nós com grau I, é ser sucessivamente.
Como estou interessado na quantidade de nós com grau impar, o número de nós impar, eu vou fazer uma separação entre aqueles com grau par e aqueles com grau impar, os nós pares e os nós impais.
Bom, em seguida é interessante observar os que aquela soma que estou fazendo, ela conta o número total de extremidades, porque cada grau de um morto é o número de extremidades que tocam aquele nó.
Então, como o marco tem duas extremidades, eu sei que essa soma na verdade ela vai me dar o número total de extremidades no ar, que eu obtei o passarmente multiplicando, duas vezes a quantidade de arcos do esse grau.
Vamos observar isso.
Nesse exemplo aqui, nós temos o morto 13 e 5 com grau 2.
Então, nós temos 2 nós com grau 2.
E os demais 5 nós têm grau 4.
Ao fazer essa conta, então, essa soma usando essa forma aqui, nós observamos que temos s igual a 24, que seria mesmo uma coisa de multiplicar por 2, o total de arcos que existem aqui, o total de arcos dessa estrutura, que são 12.
Que é 12, então, nesse caso eu tenho 24 também.
Bom, então essa soma é o número par.
Se essa soma é um número par, eu também observe o que é o desmembrar em graus, nós pares e impares.
Eu sei que essa soma aqui, esse primeiro termo, é um número par, porque eu estou chamando de 2x.
Passando esse 2x para o outro lado que também é um número par, eu chego a diferença de 2, número par, a besface é um número par.
Isso faz com que a soma dos meus nós de grau 3, tem que ser um resultado par.
E para que a soma dos números impares seja um número par, precisamos ter um número par de números impares.
Por que, para eu somar a 2 números, se eu som 3 números impares, eu não vou ter um número par.
Então eu preciso ter um número par de números impares.
Então, a soma dos números impares, para que ela seja par, precisamos ter um número par de números impares.
Ou seja, essa quantidade de nós impares, ela tem que ser par.
Então, o número de nós impares, não qual que é grafo, é par.
Assim, nós temos o resultado que nos permite identificar.
Acho que fica mais fácil agora compreender o resultado que nos permite identificar a existência onde vão caminhos de põe.
Eu vou falar que existirão um caminho de óleo em um grafo, connexo, se não tiver nós impares.
Então, o grafo, ele tem que ir a composta apenas por nós par, ou seja, nós com grau par.
Se tiver nós impares, tem que ocorrer dois nós impares apenas.
E o caminho deve começar em um no impar e terminar no outro.
Dessa forma, nós observamos aqui, por exemplo, nesse grafo, esse nó aqui tem grau 3.
Esse aqui tem grau 3, esse aqui tem grau 3, já não tem caminho de óleo.
Não conta aquele outro, porque nós vinhos que existe, está o caminho, só tem nós com grau par.
Então, eu não consigo comam de vocês, de engenharia de compropação, uma coisa bastante interessante, e a gente vai, então, como implementar o algoritmo que solucione esse caminho de óleo.
Então, aqui nós temos um píssego do código, representando isso onde você fornece uma matriz de adjacência do que representa o grafo em estudo.
E aí, o que você vai fazer? Você vai percorrer cada linha dessa matriz que seria o íunice, e aqui, até que você identifique, se realmente, aquela questão dos nós clúmpares, é violada.
Se você vai ter, por exemplo, mais que dois nós ímpares de grau ímpa, então, você já vai parar.
Se esse total então for maior, que dois, você vai escrever que não há caminho de poela, certo? Mas, enquanto for menor ou igual a dois, você vai percorrendo, porque está satisfazendo a propriedade.
Aí, você tem que calcular o grau, o grau para cada nó, é o que é, você somar os valores nas linhas dessa matriz.
Então, o que você faz para cada coluna da matriz? Você vai para cada linha percorre cada coluna, se fazendo a soma, né? E obtendo o grau daquela, daquele nó, naquela linha.
Se o grau for ímpa, você contabiliza nesse total e vai fazendo isso, e o que vai acontecer? Você vai ter esse total violado, quando o grau não possui o caminho, esse total trapaçando dois, e aí você cai nessa situação, ou não, você pode até ter os dois aqui, menor ou igual a dois, terminar o percurso, então, nesse caso, você cai no senão, aqui escreve que há um caminho de poica.
Bom, então, vamos te terá isso aqui, né? Considerando essa parte mais interna, o que vai acontecer? Nós temos essa matriz, ela é passada, essa matriz de adjacência, nós vamos processá-la para esse grafo aqui, o que vai acontecer? Na primeira linha, a gente vai somar aqui, vai ver que é o 2 com 3, e aí o meu total já vai para 1.
Vou para a segunda linha.
Som 3 de novo, o meu total vai para 2.
Vou na terceira linha, 4, o meu total não é atualizado, isso é atualizado se o grava impo.
Vou para a próxima linha, novamente 3.
Nesse caso, o meu total é atualizado, e aí eu saio da linha, quando, do meu quanto, e escrevo que não há caminho de óilha nesse caso.
Bom, o problema do circuito, a meu Tonyano, ele faz uma sutil diferença, ele faz uma sutil mudança na abordagem do caminho do.
.
.
do caminho do óilha, que deixa o problema bem mais difícil, no sentido de que o circuito, ao meu Tonyano, em grava, é um ciclo contendo todos os nós do grava.
Então eu tenho que fazer um ciclo, eu não preciso mais percorrir todos os arcos, mas eu tenho que fazer um ciclo que contém a todos os nós do grava.
Então o que acontece aqui? Todos no caminho do óilha, todos os arcos são usados exatamente uma vez, mas os nós podem ser repetidos.
Então isso tem que ficar claro para vocês.
No circuito, ao meu Tonyano, todos os nós são visitados exatamente uma vez, exceto pelo no inicial e podemos ter arcos não usados.
Então claro, só estou criando um ciclo, o meu no inicial vai ser o meu no final, certo? E aí eu quero passar, por cada no, uma única vez.
Eu tenho que percorrer todos os nós desse grava, com todos os nós, são visitados exatamente uma vez, exceto pelo no inicial.
E podemos ter arcos que não são utilizados, porque o meu intuito aqui é fazer um circuito, o ciclo.
Bom, nenhum arco é usado mais de uma vez, se não algum nó, a seria visitado novamente, e nós não queremos isso.
Então nesse caso aqui, a gente observa para esse gravo aqui, que nós não vamos conseguir fazer isso.
Se eu venho daqui, para por quê? Esse entrou o caminho, aqui já deixa ver isso bem claro.
Eu venho daqui para cá, aqui para cá, aqui para cá.
E aí eu vou voltar.
Então já não dá.
Então eu chegado a esse lado aqui, para eu poder fazer um caminho contendo esses dois nós e esses aqui.
Eu vou ter que passar por esse cara aqui, mais desse do meio, mais que uma vez.
Esse nó do meio mais que uma vez.
Bom, aqui, a gente já consegue estar de ser o circuito, né? Eu escolhi esse nó aqui de início, e aí vou fazer as conexões.
Repare que nesse caso eu não preciso passar por todos os arcos, mas eu não posso repetir o nó.
E eu tenho que visitar todos os nós.
Então aqui, está bem tranquilo.
Da gente conseguir ter o circuito, certo? Então, eu falo mencioneiro, eu tinha mencionado, o circuito é muito onyano, ele é semelhante ao caminho de óleo, mas ele tem uma diferença básica, né? Que, além da questão de que estamos considerando os mois, isso já modifica bem o contexto, porque você não consegue ter um algoritmo eficiente para determinar isso, para determinar se existe tal caminho ou não, né? É diferente, só pela mudança agora, da gente está considerando um ciclo envolvendo todos os nós.
A gente deixa de ter uma maneira mais um algoritmo eficiente de dizer se há ou não uma solução envolvendo todos aqueles nós.
Tá? E vocês provavelmente vão ver mais disso na parte de análise de algoritmos, aí no decorrido curso de vocês.
Bom, aqui foram então apresentados os conceitos básicos, tá? Eu espero que vocês façam a leitura da 677.
2 do material base, tá? E enserramos o nosso curso com esta visual.
Boa sorte, sucesso no curso de vocês.