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.