Considere el gráfico no dirigido G definido de la siguiente manera. Los vértices de G son strings de bits de longitud n. Tenemos una arista entre el vértice u y el vértice v si y solo si u y v difieren exactamente en una posición de bit (en otras palabras, v se puede obtener de u cambiando un solo bit). La razón del número cromático de G al diámetro de G es
(A) 1/(2 n-a )
(B) 1/n
(C) 2/n
(D) 3/n
Respuesta: (C)
Explicación:
Gráfico bipartito: un gráfico bipartito es un gráfico G (V, E) donde los vértices se pueden descomponer en dos conjuntos disjuntos, de modo que no hay dos vértices adyacentes dentro del mismo conjunto.
Diámetro de un gráfico: – El camino más corto más largo entre dos vértices cualesquiera de un gráfico El gráfico dado es un gráfico bipartito => el número cromático es igual a 2 El diámetro del gráfico es igual a n porque como máximo necesitamos atravesar n- 1 bordes.
La relación = 2/n
Referencia: https://en.wikipedia.org/wiki/Hypercube_graph
Esta solución es aportada por Anil Saikrishna Devarasetty
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA