Introdução à Teoria dos Grafos - Aula 18 - Cortando uma rede de vôlei

Professor Marcos Paulo Ferreira de Araújo
Aula 18 - Cortando uma rede de vôlei
Uma certa rede de vôlei possui 20x50 quadradinhos. Com o passar do tempo, alguns dos barbantes que conectam os vértices dos quadradinhos podem se romper, entretanto, será necessário que vários barbantes arrebentem para que a rede se desfaça em dois ou mais pedaços. Qual é o número máximo de barbantes que podemos cortar de modo que a rede continue em um pedaço após os cortes?
Veremos que este problema tem uma relação muito forte com árvores, isto é, grafos conexos e sem ciclos. A solução apresentada, mais do que simplesmente resolver o problema acima, nos diz que qualquer grafo conexo possui um subgrafo com o mesmo número de vértices e que também é uma árvore.
Os direitos sobre todo o material deste canal pertencem ao Instituto de Matemática Pura e Aplicada, sendo vedada a utilização total ou parcial do conteúdo sem autorização prévia e por escrito do referido titular, salvo nas hipóteses previstas na legislação vigente.
The rights over all the material in this channel belong to the Instituto de Matemática Pura e Aplicada, and it is forbidden to use all or part of it without prior written authorization from the above mentioned holder, except in the cases prescribed in the current legislation.