martes, 10 de julio de 2012

Grafos

UNLaM
Y más grafos....

1) ¿Es posible Construir un Grafo 3-regular con 5 Vértices?

No puede ser ya que si es 3 regular, cada vértice tendrá grado 3, y si tuviera 5 vértices, la suma de los vértices da 15, y esto es imposible, ya que la suma de los grados de un grafo siempre es par.


2) ¿Es posible Construir un Grafo completo con 25 aristas?

No es posible.
Un grafo completo de n vértices tiene  n.(n - 1)/ 2  aristas.
En nuestro caso sería:
n(n-1)/20= 50
n(n-1)=100
Resolviendo nos queda una cuadrática:
n^2-n-100= 0
Cuyas soluciones no son enteras...por ende no existe un grafo completo con 50 aristas.

GRAFOS COMPLETOS DE 1 A 12 VÉRTICES