Gráf szomszédossági mátrixa Sorai és oszlopai a mátrix csúcsait jelölik. Egy elem értéke az adott két csúcs között futó élek száma. Irányított mátrix esetén a csúcsok sorrendje számít. (vagyis ai,j az i-ből j-be menő élek száma) A2 – a mátrixok szorzásának tulajdonságai miatt – pont a közös szomszédok számát adja. Fogalmazhatunk úgy is, hogy azt adja meg, hogy hányféleképpen juthatunk el az egyik csúcsról a másikra 2 lépésben. A főátló esetén a két csúcs azonos, tehát az érték pont a fokszámmal egyenlő. Am mátrix értékei az jelölik, hogy az adott két csúcs között hány m lépéses séta (út, amely ismétlést tartalmazhat) van. A3 főátlóbeli elemeinek összege a háromszögek számának hatszorosa. A szomszédossági mátrix sajátértékei ≤ a gráf maximális fokszáma Δ(G).
Szerzők: yoda
[Szócikk szerkesztése]
[Lexikon kezdőlapra lépés]
A szócikknek van egy olyan módosított újabb változata is, amit mi még nem ellenőriztünk. A megtekintéshez kattintson ide!
|
