Grafo no dirigit

Grafo no dirigit en dos nodos i una aresta.

Un grafo no dirigit és un tipo de grafo en el qual les arestes representen relacions simètriques i no tenen un sentit definit, a diferència del grafo dirigit, en el qual les arestes tenen un sentit i per tant no són necessàriament simètriques.

Formalment, es definixen per un parell de conjunts $G=(V,E)$, a on:

• $V\ne \mathrm{\varnothing }$ és el conjunt no buit de vèrtiços o nodos.
• $E\subseteq \{(a,b)\in V\times V\}$ és el conjunt d'arestes, tal que $(a,b)=(b,a)$.

En el cas dels grafos no dirigits, una aresta $(a,b)$ també es pot denotar com $\{a,b\}$.

Siga $n=|V|$ el número de nodos d'un grafo no dirigit, est podrà a lo més tindre $n^2/2$ arestes, i $n(n-1)/2$ en cas que siga un grafo simple, que excloga els bucles.

Tot grafo dirigit simètric es pot representar com un grafo no dirigit. Per lo tant, els grafos no dirigits es poden vore com un cas particular de grafos dirigits.

En un grafo no dirigit, la transpuesta de la triangular superior de la seua matriu de adyacencia és igual a la seua triangular inferior, i viceversa.