Gràfic dirigit vs no dirigit
Un gràfic és una estructura matemàtica que està formada per un conjunt de vèrtexs i arestes. Un gràfic representa un conjunt d'objectes (representats per vèrtexs) que estan connectats a través d'uns enllaços (representats per arestes). Utilitzant notacions matemàtiques, un gràfic es pot representar amb G, on G=(V, E) i V és el conjunt de vèrtexs i E és el conjunt d'arestes. En un gràfic no dirigit no hi ha cap direcció associada a les arestes que connecten els vèrtexs. En un gràfic dirigit hi ha una direcció associada a les arestes que connecten els vèrtexs.
Gràfic no dirigit
Com s'ha esmentat anteriorment, un gràfic no dirigit és un gràfic en el qual no hi ha cap direcció a les arestes que uneixen els vèrtexs del gràfic. La figura 1 representa un gràfic no dirigit amb un conjunt de vèrtexs V={V1, V2, V3}. El conjunt d'arestes del gràfic anterior es pot escriure com a V={(V1, V2), (V2, V3), (V1, V3)}. També es pot observar que no hi ha res que impedeix escriure el conjunt d'arestes com a V={(V2, V1), (V3, V2), (V3, V1)} ja que les arestes no tenen direcció. Per tant, les arestes d'un gràfic no dirigit no són parells ordenats. Aquesta és la característica principal d'un gràfic no dirigit. Els gràfics no dirigits es poden utilitzar per representar relacions simètriques entre objectes que es representen per vèrtexs. Per exemple, una xarxa de carreteres bidireccionals que connecta un conjunt de ciutats es pot representar mitjançant un gràfic no dirigit. Les ciutats es poden representar amb els vèrtexs del gràfic i les vores representen les carreteres de doble sentit que connecten les ciutats.
Gràfic dirigit
Un gràfic dirigit és un gràfic en què les arestes del gràfic que uneixen els vèrtexs tenen una direcció. La figura 2 representa un gràfic dirigit amb un conjunt de vèrtexs V={V1, V2, V3}. El conjunt d'arestes del gràfic anterior es pot escriure com a V={(V1, V2), (V2, V3), (V1, V3)}. Les arestes en un gràfic no dirigit són parells ordenats. Formalment, l'aresta e en un gràfic dirigit es pot representar pel parell ordenat e=(x, y) on x és el vèrtex que s'anomena origen, font o punt inicial de l'aresta e, i el vèrtex y s'anomena extrem., vèrtex final o punt terminal. Per exemple, una xarxa de carreteres que connecta un conjunt de ciutats mitjançant carreteres unidireccionals es pot representar mitjançant un gràfic no dirigit. Les ciutats es poden representar amb els vèrtexs en el gràfic i les vores dirigides representen les carreteres que connecten les ciutats tenint en compte la direcció en què circula el trànsit a la carretera.
Quina diferència hi ha entre el gràfic dirigit i el gràfic no dirigit?
En un gràfic dirigit, una aresta és una parella ordenada, on la parella ordenada representa la direcció de l'aresta que uneix els dos vèrtexs. D' altra banda, en un gràfic no dirigit, una aresta és un parell no ordenat, ja que no hi ha cap direcció associada a una aresta. Els gràfics no dirigits es poden utilitzar per representar relacions simètriques entre objectes. El grau interior i el grau exterior de cada node en un graf no dirigit són iguals, però això no és cert per a un graf dirigit. Quan s'utilitza una matriu per representar un gràfic no dirigit, la matriu sempre es converteix en un gràfic simètric, però això no és cert per als gràfics dirigits. Un gràfic no dirigit es pot convertir en un gràfic dirigit substituint cada aresta per dues arestes dirigides que van en direcció oposada. Tanmateix, no és possible convertir un gràfic dirigit en un gràfic no dirigit.
