Grafos

GRAFOS

Definición 1.1 Un grafo (o bien un grafo no dirigido) G consiste de un conjunto finito de vértices V y un conjunto finito de lados l tales que cada lado esta asociado a un par no ordenado de vértices.

Notación: Si un lado esta asociado a un único par de vértices lo escribiremos como
l = ((,()
Donde
l es el lado
y
υ, ( vértices.

Definición 1.1.1 Se dice que un par((,() de vértices es no ordenado si cumple
((, () = ((, ().

Ejemplo 1.1

Definición 1.2 Un grafo dirigido G consiste de un conjunto finito de vértices V y un conjunto finito de lados L, tales que cada lado pertenece a un par ordenado de vértices.

Definición 1.2.1 Se dice que un par (u, v) de vértices es ordenado si cumple ((,() ((, ()

Ejemplo 1.2

Definición 1.3 Se dice que doslados l i y l j, si l i l j, son lados paralelos si están asociados al mismo par de vértices y los lados del tipo l = ((, () se llaman lazos.

Ejemplo 1.3

Definición 1.4 La valencia (grado) de un vértice V es el número de lados incidentes en V.

Notación: La valencia de V se denota como ((v).

Ejemplo 1.4

((v1) = 2
((v2) = 2
((v3) = 2((v4) = 3
((v5) = 1

Definición 1.5: Un grafo (dirigido o no dirigido) que no tiene lados paralelos ni lazo se llama: Grafo (dirigido o no dirigido) simple.

Algoritmo para construir la matriz de adyacencia de un grafo.

• Paso 1: Se le asignan un orden arbitrario a los vértices.
• Paso 2: Se construye una matriz de dimensión cardinalidad (( vértices) porcardinalidad (( vértices).
• Paso 3: En la posición I j-ésima se coloca 1 si el vértice i es adyacente al vértice j; 0 en el otro caso.

Ejemplo 1.5 Construir la matriz de adyacencia (MA) para el siguiente grafo:

| | |v1 |v2 |v3 |v4 |v5 |
| |v1 |0 |1 |1 |0 |0 |
| |v2 |1 |0 |0 |1 |0 |
|MA =|v3 |1 |0 |0 |1 |0 |
| |v4 |0 |1 |1 |0 |1 |
| |v5 |0 |0 |0 |1 |1 |

Se obtiene la valencia de cada uno de los vértices si sumamos la fila o columna correspondiente a dicho vértice.
| | |V1 |v2 |v3 |v4|v5 |
|A | |0 |1 |0 |1 |0 |
|B | |1 |0 |1 |0 |0 |
|C |MA = |0 |1 |0 |1 |1 |
|D| |1 |0 |1 |0 |0 |
|E | |0 |0 |1 |0 |0 |

| |0 |

Notas:
• La suma de la fila en unamatriz de incidencia representa el número de lados incidentes en ese vértice.
• Si la suma de la columna es uno (1) en una matriz de incidencia entonces ese lado es un lazo.
• La matriz de incidencia nos permite representar grafos con lados paralelos y lazos simultáneamente.
Definición 1.6: Sea G un grafo, v y w dos vértices, un camino de longitud n de v a w es una sucesión de lados(v0, v1, v2,..., vn) donde v0 = v y vn = w y todos los lados son diferentes.
Definición 1.7: Sea G un grafo, v y w dos vértices, un camino simple de longitud n de v a w es una sucesión de lados (v0, v1, v2,..., vn) donde v0 = v y vn = w y los vi son diferentes.

|Ejemplo 1.7: | |
|...