PUERTA | PUERTA-CS-2006 | Pregunta 72

Los 2 ⁿ vértices de un grafo G corresponden a todos los subconjuntos de un conjunto de tamaño n, para n >= 6. Dos vértices de G son adyacentes si y sólo si los conjuntos correspondientes se cortan en exactamente dos elementos.

El grado máximo de un vértice en G es:
(A) (n/2)C2 *2 ^n/2
(B) 2 ^n-2
(C) 2 ^n-3 *3
(D) 2 ^n-1

Respuesta: ( C)
Explicación: max _k (kC2*2 ^(n−k) )=3C2*2 ⁽ⁿ⁻³⁾ =3*2 ⁽ⁿ⁻³⁾ .
Cuestionario de esta pregunta