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)}$.

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.

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

Enlaces externos

• Weisstein, Eric W. «UndirectedGraph». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 

• Datos: Q109424306