A teoria dos grafos é um ramo da Matemática Discreta que considera um grafo como sendo uma abstração que permite codificar relacionamentos entre pares de objetos. A respeito da teoria de grafos, analise os itens a seguir. Podemos denotar um grafo como sendo uma estrutura de dados não-linear com um conjunto de nós e suas conexões entre eles. II. Em todo grafo direcionado, a soma dos graus de saída dos vértices é igual à soma dos graus de entrada. III. A propriedade de grafos que relaciona a soma dos graus de todos os vértices com o seu número de arestas não se aplica a árvores. IV. Todo grafo é uma árvore, mas nem toda árvore é um grafo. Estão corretas, apenas:

Alternativa A

A questão trata dos fundamentos da Teoria dos Grafos, essencial para a área de Ciência da Computação e Matemática Discreta. Para encontrar a resposta correta, precisamos avaliar a veracidade de cada afirmação apresentada.

Análise dos Itens:

• Item I (Correto): Um grafo é definido formalmente como um par ordenado (V, E), onde V é um conjunto de vértices (nós) e E é um conjunto de arestas (conexões). Por permitir conexões arbitrárias entre nós, ele é classificado como uma estrutura de dados não-linear.
• Item II (Correto): Em um grafo direcionado, cada aresta possui uma origem e um destino. Logo, ela contribui com 1 para o grau de saída do vértice de origem e com 1 para o grau de entrada do vértice de destino. Assim, a soma total dos graus de saída é sempre igual à soma total dos graus de entrada, ambas iguais ao número total de arestas: \sum \text{grau}_{sai}(v) = \sum \text{grau}_{ent}(v) = |E|
• Item III (Incorreto): Refere-se ao Lema do Aperto de Mão, que diz que a soma dos graus de todos os vértices é igual ao dobro do número de arestas (\sum \deg(v) = 2|E|). Como árvores são um tipo específico de grafo (conexo e sem ciclos), essa propriedade se aplica a elas também.
• Item IV (Incorreto): A definição está invertida. Toda árvore é um grafo, mas nem todo grafo é uma árvore (grafo pode conter ciclos). Árvores são um subconjunto dos grafos.

Resumo da Correção

Para confirmar a escolha, analisamos a validade lógica de cada proposição:

• I: Verdadeiro (Definição de estrutura não-linear).
• II: Verdadeiro (Conservação de fluxo em grafos direcionados).
• III: Falso (Propriedades gerais de grafos valem para árvores).
• IV: Falso (Relação de inclusão está errada).

Portanto, apenas as afirmações I e II estão corretas.

Alternativa A.