Introdução à Teoria dos Grafos - Aula 10 - Conexidade

Professor Marcos Paulo Ferreira de Araújo
Aula 10 - Conexidade
Suponha que em um país existam 15 cidades e que de cada cidade partam pelo menos 7 estradas. Nesta aula mostramos que para quaisquer das duas cidades escolhidas existe um caminho de estradas ligando estas duas cidades, possivelmente passando
por outras no meio do percurso.
A propriedade que demonstramos é um conceito importante em teoria dos grafos, conhecido como conexidade. Intuitivamente, um grafo é conexo se ele "tem apenas um pedaço", ou seja, se quaisquer dois vértices estão conectados através
de um caminho andando pelas arestas do grafo.
Ao final, generalizamos o problema anterior para um país com um número n de cidades.
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.