Grafos

GRAFOS DEFINICIONES BÁSICAS Un grafo G es un par (V,E) donde V es un conjunto (llamado conjunto de vértices) y E un subconjunto de VxV (conjunto de aristas). Gráficamente representaremos los vérticespor puntos y las aristas por líneas que los unen. Un vértice puede tener 0 o más aristas, pero toda arista debe unir exactamente 2 vértices. A a
 
  B
 
 

Arista
  Vértice
  
  Bucle: Es la arista que el vértice inicial y el final es el mismo
 

Vértice
 

A
 

B
 
 

Aristas múltiples: Son las aristas que unen a dos vértices mas de unavez.

A
 

B
 
 

Aristas
 
 

Vértices adyacentes: Es cuando dos vértices están unidos por una arista. El vértice A es adyacente al vértice B

A
 

B
 
 Aristas adyacentes: tienen un vértice en común. {A,B} adyacente {A,C} y {A,D} B
 

A
 

C
 

D
 
  Una arista y un vértice son incidentes si el vértice es extremo de la arista. Uincidente {u, v} y {u, x} U
 
  X
  V
 
 

Vértice aislado: Si no es adyacente a ningún otro vértice.

A
  A
 

B
  Vértice
 aislado
  E
  C
  D
 

Ordende un grafo. Es el número de vértices.

Orden= 4 Grado de un vértice. Numero de aristas de las que es extremo. Se dice que un vértice es par o impar según lo sea su grado.

A
 

B

G(A)= 2G(B)= 2 G(C)= 2 G(D)= 2 Grafo simple: Si no tiene bucles ni aristas múltiples. Grafo dirigido o dígrafo: Importa el orden de las aristas

Grafo regular: Tiene el mismo grado en todos los vértices.Si ese grado es k lo llamaremos k-regular.

Es un grafo 2-regular. Grafo bipartito: Sus vértices pueden formar dos conjuntos disjuntos de modo que no haya adyacencia entre vértices pertenecientes almismo conjunto A B

X:{A, B} Y:{C, D, E}

C

D

E

Grafo completo: Existe una arista entre cada par de vértices. Un grafo completo con n vértices se denota kn.

Grafo bipartito...