GRAFOS NO DIRIGIDOS
El grado de un vértice es el número de aristas incidentes con él, cada bucle se cuenta dos veces:
– Denotaremos el grado de un vértice por dG(Vértice).
– Denotaremos el conjunto de vértices adyacentes por Γ(Vértice).
 |
dG(1) = 2 dG(2) = 1 dG(3) = 1 |
Γ(1) = {2,3} Γ(2) = {1} Γ(3) = {1} |
GRAFOS DIRIGIDOS
El grado de salida de un vértice es el número de arcos salientes de ese vértice.
El grado de entrada de un vértice es el número de arcos entrantes de ese vértice.
El grado de un vértice será la suma de estos dos grados.
– Denotaremos el grado de salida por dS(Vértice)
– Denotaremos el grado de entrada por dE(Vértice)
– Denotaremos el conjunto de vértices adyacentes salientes de v por Γ(v).
– Denotaremos el conjunto de vértices adyacentes entrantes de v por Γ-¹(v).
 |
dS(1) = 1 dS(2) = 1 dS(3) = 0 dE(1) = 1 |
Γ(1) = {3} Γ(2) = {1} Γ(3) = {Ø} Γ-¹(1) ={2} |
CAMINOS
Una cadena es una sucesión finita W = v0 e1 v1 e3 … cuyos elementos son alternativamente vértices y aristas.
Una cadena simple es una cadena con todas sus aristas distintas.
Una cadena cerrada es una cadena de longitud no nula donde el vértice incial y final coinciden.
La longitud de una cadena es el número de aristas que contiene.
Un camino es una cadena con todos sus vértices distintos.
Un ciclo es Cadena simple + Cadena cerrada + Camino.
CONEXIÓN
Dos vértices están conectados si existe un camino de uno a otro y viceversa.
Un grafo es conexo si todo par de vértices están conectados.
Un grafo dirigido es débilmente conexo si su no dirigido asociado es conexo.