9. Para compreender o conceito de árvores geradoras, é preciso antes entender as definições de grafos e árvores, saber diferenciar o conjunto das a...

9. Para compreender o conceito de árvores geradoras, é preciso antes entender as definições de grafos e árvores, saber diferenciar o conjunto das arestas e vértices, assim como identificar o contexto de aplicação dessa estrutura de dados, não confundindo com as aplicações da estratégia usadas em caminhos mínimos. Com base nos principais conceitos correlatos às árvores geradoras, analise os itens a seguir: I. Uma árvore geradora é um subgrafo gerador cíclico, não direcionado e com o menor custo possível. II. Uma árvore tem complexidade na ordem de O(N3) e tem ciclo em sua estrutura, por exemplo: ciclo euleriano. III. Um corte C (S, V-S) é uma partição no grafo G = (V, E) que busca auxiliar na expansão das arestas da árvore geradora. IV. Toda árvore geradora mínima é uma árvore geradora, assim como toda árvore geradora é uma árvore geradora mínima. V. Toda árvore é um grafo, porém nem todo grafo pode ser uma árvore, pois este último goza de propriedades mais abrangentes. Quais estão corretos?

Uma árvore geradora é um subgrafo gerador cíclico, não direcionado e com o menor custo possível.
Uma árvore tem complexidade na ordem de O(N3) e tem ciclo em sua estrutura, por exemplo: ciclo euleriano.
Um corte C (S, V-S) é uma partição no grafo G = (V, E) que busca auxiliar na expansão das arestas da árvore geradora.
Toda árvore geradora mínima é uma árvore geradora, assim como toda árvore geradora é uma árvore geradora mínima.
Toda árvore é um grafo, porém nem todo grafo pode ser uma árvore, pois este último goza de propriedades mais abrangentes.
I, III.
III, V.
I, II.
II, III.