Számít referencia-módszerek
Legyen G - címkézett gráf n csúcsú és m élek. Definiáljuk a szomszédsági mátrix A (G) az alábbiak szerint:
A szomszédsági mátrix négyzet, a méret N „n.
Látható, hogy a szomszédsági mátrix szimmetrikus, és az egységek száma minden sorban megegyezik a mértéke a vertex, amely megfelel ezen a vonalon. Szerint a szomszédsági mátrix a konstrukciója egyszerű grafikus ábrázolása a grafikon.
4.6 példa. Szerkesszünk egy olyan grafikont a szomszédsági mátrix
Lehetőség van, hogy meghatározzuk a mátrix esetén I (G). ahol n sorból és m oszlopból, melynek elemei meghatározása a következő:
Példa 4.7. Tekintsük a gráf példa 4,6 ', amely élek.
Minden sorban a beesési csak két elem különbözik 0 (vagy az egyik, ha a szélén egy hurok). Ezért ez a módszer leírását gazdaságtalan. Az arány a beesési is adható egy listát a szélek. Minden sor a listában felel meg a szélén, akkor rögzített számok csúcsok esetet is.
Példa 4.8. Tekintsük a gráf példa 4.7. Listája bordák alakja: a
Szerint a listát a szélek a konstrukciója egyszerű mátrix esetén, mert minden éle a lista felel meg az oszlop mátrixok, és vertex számok az egyes lista-elem olyan nem - tagok előfordulási mátrix sorok, amelyek egyenlő 1.
A grafikon is képviselheti különböző módokon. Néha nem könnyű látni, hogy ugyanezeket a grafikonokat különböző ábrákon vagy különböző mátrixok. Grafikonok, amelyek egymástól csak a címkéjén csúcsok izomorfak. Újraszámozás egy sor új csúcsok szoba található az eredeti sorrendben. Az új szomszédsági mátrix eredményeként kapott mozgásának minden egyes eleme aij a sor és oszlop, azaz kapott permutációt () a sorok és oszlopok az eredeti mátrix. Tudod, hogy minden lehetséges permutációja a sorok és oszlopok annak érdekében, hogy a nonisomorphic grafikonok, de el fog tartani n. permutáció, hogy meglehetősen munkaigényes.