Cadena simple. Cadena con todas sus aristas distintas.
Camino. Cadena con todos sus vértices distintos.
Cadena cerrada. Cadena de longitud no nula en donde el vértice inicial y final coinciden.
Ciclo. Cadena simple cerrada con todos sus vértices internos distintos.
Camino y conexión.
Dos vértices u y v están conectados si existe un camino de u a v y viceversa.
Un grafo es conexo si todo par de vértices esta conectado.
Conexo. Si existe un camino entre un par de vértices conectado.
TEOREMA
Un grafo es conexo sii el numero de componentes conexas es 1.
Crear matrices.
– Crear matriz nula, cuyas filas y columnas representan los vértices del grafo.
– Para cada arista:
* Si no es bucle -> Se suma 1 en el elemento correspondiente de la matriz
* Si es bucle ->
+ Si es GD -> Sumar 1
+ Si es GND -> Sumar 2
– Se obtiene una matriz que representa el numero de aristas entre cada par de vértices
Ejemplo:
0 – 2 – 1 – 0
2 – 2 – 1 – 1
1 – 1 – 0 – 0
0 – 1 – 0 – 0
e1 {v1, v2} ≡ a12, a21
e2 {v1, v2} ≡ a12, a21
e3 {v1, v3} ≡ a13, a31
e4 {v2, v3} ≡ a23, a32
e5 {v3, v5} ≡ a35, a53
e6 {v2, v5} ≡ a25, a52