Defina o que é um grafo conexo. E um desconexo?

Passo 1

O enunciado pede para definirmos os conceitos de grafo conexo e grafo desconexo, dentro do tema Teoria dos Grafos, usando noções de vértices, arestas e caminhos.

Passo 2

Um grafo G = (V, E) é dito conexo quando, para todo par de vértices u, v in V, existe pelo menos um caminho em G que vai de u até v. Em outras palavras, não há forma de separar o grafo em pedaços isolados: todos os vértices estão interligados por algum caminho.

Passo 3

Um grafo é chamado de desconexo quando não é conexo, ou seja, existem pelo menos dois vértices u, v in V tais que não há caminho em G ligando u a v. Equivalente a dizer que o grafo tem mais de uma componente conexa.

Resposta

Um grafo G=(V,E) é conexo se, para todo par de vértices u,vin V, existe um caminho entre u e v. É desconexo quando não satisfaz essa condição, isto é, quando existem vértices sem nenhum caminho ligando-os (o grafo tem mais de uma componente conexa).

Exercícios relacionados