Maestro En Artes Oscuras

TEORIA DE GRAFOS
1. En un grafo completo Kn, en el que cada uno de los n vértices tiene una arista que incide en todos los demás vértices, entonces cada vértice tiene n-1 aristas. Si se aplica elteorema de apretones de manos, teniendo en cuenta las afirmaciones anteriores :
vϵVδv=2e Sustituyendo tenemos n*(n-1)=2e, siendo e el número total de aristas del grafo. Despejando concluye que elnúmero de aristas de un grafo completo se obtiene mediante la ecuacion:
e=n*(n-1)2

2. En un Grafo Qn existen 2n cadenas de bits de longitud n que representan los vértices del grafo. Si cadavértice tiene longitud n, entonces existirán n cadenas de bits que tienen un bit de diferencia con la cadena de dicho vertice
3. En un Grafo Qn existen 2n cadenas de bits que representan losvértices del grafo, y para cada vértice existen exactamente n cadenas de bit distintas que difieren de su valor en un bit diferente. Si se aplicase el teorema de apretón de manos se obtiene:
vϵVδv=2eSustituyendo tenemos 2n *(n-1)=2e, siendo e el número total de aristas del grafo. Se puede concluir que el número total de aristas de un grafo n-cubo responde a la ecuación:
e=2n*(n-1)2
4. El grafo dela figura es bipartito y los 2 subconjuntos de vértices son:
V1={ v1,v2,v5} y V2={v3,v4}
5. El grafo de precedencia correspondiente al conjunto de sentencias es el siguiente:
S8
S8
S1
S1S7
S7
S5
S5
S6
S6
S4

S4

S3
S3
S2
S2

6. A. si es posible porque la sumatoria de aristas de todos los vértices del grafo es un número par.
b. No es posible porque la sumatoria dearistas de todos los vértices del grafo no es un número par.
c. Si es posible, porque la sumatoria de aristas de todos los vértices seria par, además sería un grafo ciclo.
d. Si es posible pero en larepresentación gráfica del grafo se distinguirían vértices aislados
e. No es posible porque si solo existen 4 aristas y un vértice de grado 4 pueden existir a lo sumo vértices de grado 1, y...