MO417 - Questão para a prova oral
Número:
Enunciado: Em uma representação de conjuntos disjuntos através de grafos não orientado, suponha que é dado um grafo com n vértices.
Determine a quantidade mínima e máxima, respectivamente, de arestas que o grafo pode possuir para obtermos k conjuntos disjuntos.
Considere que não há mais de uma aresta entre dois vértices e que não há laços, ou seja, arestas com vértices idênticos nas extremidades.
a) n-k e (n-k+1)(n-k)/2
b) n e (n-k)²
c) n-k e n(n-1)/2
d) n+k e nk
e) NDA
Ideia original de: Jacqueline Midlej do Espírito Santo
Enunciado: Em uma representação de conjuntos disjuntos através de grafos não orientado, suponha que é dado um grafo com n vértices.
Determine a quantidade mínima e máxima, respectivamente, de arestas que o grafo pode possuir para obtermos k conjuntos disjuntos.
Considere que não há mais de uma aresta entre dois vértices e que não há laços, ou seja, arestas com vértices idênticos nas extremidades.
a) n-k e (n-k+1)(n-k)/2
b) n e (n-k)²
c) n-k e n(n-1)/2
d) n+k e nk
e) NDA
Ideia original de: Jacqueline Midlej do Espírito Santo
Nenhum comentário:
Postar um comentário