Graf no dirigit

Un graf no dirigit és un tipus de graf en què les arestes representen relacions simètriques i no tenen un sentit definit, a diferència del graf dirigit, en què les línies tenen un significat i, per tant, no són necessàriament simètriques.^[1]

Graf no dirigit amb dos nodes i una línia o aresta.

Formalment, es defineixen per un parell de conjunts ${\displaystyle G=(V,E)}$, on:

• ${\displaystyle V\neq \emptyset }$ és el conjunt no exempt de vèrtexs o nodes.
• ${\displaystyle E\subseteq \{(a,b)\in V\times V\}\,}$ és el conjunt de les línies, tal que ${\displaystyle (a,b)=(b,a)}$.

Sigui ${\displaystyle n=|V|}$ el nombre de nodes d'un graf no dirigit, aquest pot tenir com a màxim ${\displaystyle n^{2}/2}$ arestes i ${\displaystyle n(n-1)/2}$ , per si es tracta d'un graf senzill, que exclou els bucles de la teoria de grafs. En un graf no dirigit, la transposada de la triangular superior de la seva matriu d'adjacència és igual a la seua triangular inferior i viceversa.

Enllaços externs

• Weisstein, Eric W., «UndirectedGraph» a MathWorld (en anglès).