O algoritmo de busca em profundidade é amplamente usado para detectar ciclos, encontrar componentes ...

Alternativa B - Em um grafo direcionado, pode haver vértices sem arestas de entrada ou de saída.

Introdução

Um grafo direcionado, ou dígrafo, é uma estrutura composta por vértices e arestas com uma direção definida (arcos). Diferente dos grafos não direcionados, a relação entre os nós possui um sentido único.

Desenvolvimento

Em dígrafos, as arestas são pares ordenados (u, v), indicando que o caminho vai de u para v. Isso introduz os conceitos de grau de entrada (quantidade de arestas chegando) e grau de saída (quantidade de arestas saindo).

Análise

• A incorreta: Nem todo dígrafo é conexo; ele pode possuir componentes isolados.
• B correta: É perfeitamente possível ter um vértice isolado (grau 0) ou um vértice que seja apenas fonte (sem entrada) ou apenas ralo (sem saída).
• C incorreta: Dígrafos podem conter laços (um arco que sai e volta para o mesmo vértice).
• D incorreta: Os graus de entrada e saída são independentes para cada vértice, exceto se o grafo for regular nesse aspecto específico.
• E incorreta: Existem os DAGs (Grafos Direcionados Acíclicos), que por definição não possuem ciclos.

Conclusão

A flexibilidade estrutural dos grafos direcionados permite a existência de vértices sem fluxos de entrada ou saída.

Alternativa B.