Grafo no dirigido

Un grafo no dirigido es un tipo de grafo en el cual las aristas representan relaciones simétricas y no tienen un sentido definido, a diferencia del grafo dirigido, en el cual las aristas tienen un sentido y por tanto no son necesariamente simétricas.

Grafo no dirigido con dos nodos y una arista.

Formalmente, se definen por un par de conjuntos ${\displaystyle G=(V,E)}$, donde:

• ${\displaystyle V\neq \emptyset }$ es el conjunto no vacío de vértices o nodos.
• ${\displaystyle E\subseteq \{(a,b)\in V\times V\}\,}$ es el conjunto de aristas, tal que ${\displaystyle (a,b)=(b,a)}$.

En el caso de los grafos no dirigidos, una arista ${\displaystyle (a,b)}$ también se puede denotar como ${\displaystyle \{a,b\}}$.

Sea ${\displaystyle n=|V|}$ el número de nodos de un grafo no dirigido, este podrá a lo más tener ${\displaystyle n^{2}/2}$ aristas, y ${\displaystyle n(n-1)/2}$ en caso de que sea un grafo simple, que excluya los bucles.

Todo grafo dirigido simétrico se puede representar como un grafo no dirigido. Por lo tanto, los grafos no dirigidos se pueden ver como un caso particular de grafos dirigidos.

En un grafo no dirigido, la transpuesta de la triangular superior de su matriz de adyacencia es igual a su triangular inferior, y viceversa.