Gráf szomszédsági mátrixa

Egy G gráf A_G szomszédsági mátrixa az a mátrix, amely sorai és oszlopai is a gráf csúcsaival vannak azonosítva és egy u csúcsnak megfelelő sor és egy v csúcsnak megfelelő oszlop találkozásánál lévő pozícióban m áll, ha u és v ké t különböző csúcs, amelyeket m darab él köt össze; továbbá 2m, ha u=v és u-ra m darab hurokél illeszkedik.

Tehát egy gráf szomszédsági mátrixára teljesül, hogy

• elemei természetes számok,
• a főátlón páros természetes számokat tartalmaz,
• szimmetrikus.

Ha egy gráfban van hurokél, akkor a főátlóján van nem-nulla elem.