Matriu d'adjacència: diferència entre les revisions

LaUna ''' matriu d'adjacència ''' és una [[Matriu (matemàtiques)|matriu]] [[matriu quadrada|quadrada]] que s'utilitza com una forma de representar [[relació binària|relacions binàries]].

# Es crea una [[matriu zero]], les columnes i files representen els '' nodes '' del graf.

#: Si aquesta aresta és un [[Bucle (teoria de grafs)|bucle]] i el graf és [[Grafgraf #(matemàtiques)|graf]] Grafés no dirigit|no dirigit]], llavors se suma [[dos|2]] en comptes de 1.

[[Fitxer: 6n-graf.svg|250px|thumb|Exemple de [[graf (matemàtiques)|graf]], per al qual es calcula la matriu d'adjacència.]]

La matriu d'adjacència per al [[graf (matemàtiques)|graf]] de la figura ve donada per:

* El nombre de camins '' C _{i, j} '' ('' k ''), travessant '' k '' arestes des del node '' i '' al node '' j '', ve donat per un element de la potència k -èsima de la matriu d'adjacència:

Hi ha altres formes de representar relacions binàries, com ara els [[parell ordenat|parells ordenats]] o els [[graf (matemàtiques)|grafs]] s. Cada representació té les seves prestacions. En particular, la matriu d'adjacència és molt utilitzada en la [[programació informàtica]], perquè la seva naturalesa binària i matricial calça perfecte amb la dels [[ordinador|ordinadors]]. No obstant això, una persona normal i corrent se li farà molt més senzill comprendre una relació descrita mitjançant grafs, que mitjançant matrius d'adjacència. Una altra representació matricial per a les relacions binàries és la [[matriu d'incidència]].

{{ORDENA:Matriu D'Adjacencia}} <!--ORDENA generat per bot-->