előfordulási mátrix
Ha azt mondjuk, hogy a széle g és az egyes csúcsok u és y incidens g. Ez csak a költségek, ha g összeköti u és y. Miután tisztázta ezt, nézzük ezt a módszert. Az előfordulási mátrix alapján egy hasonló, de nem azonos elven, hogy a szomszédsági mátrix. Így, ha az utóbbi mérete n × n, ahol n - a csúcsok száma, az előfordulási mátrix - n × m. itt N - a csúcsok száma, m - az élek számát. Tehát most, hogy az értéket a cella, akkor nem társítani a tetején a tetején, és a tetején a borda.
Mindegyik mátrix esetén egy irányítatlan gráf a cella van beállítva, hogy 0 vagy 1, és abban az esetben egy irányított gráf. készült 1, 0 vagy -1. Ugyanez, de strukturált:
- irányítatlan gráf
- 1 - a felső széle a beeső
- 0 - a tetején nem esemény, hogy a szélén
- irányított gráf
- 1 - a felső széle az incidens, és ez kezd
- 0 - a tetején nem esemény, hogy a szélén
- -1 - vertex incidens szélén, és annak végén
Mi konstrukció az előfordulási mátrixa egy irányítatlan gráf az első, majd a digráf.
Bordák betűkkel e-ig. vertex - számokat. Minden szélei a gráf nem orientált, azonban előfordulási mátrix töltött pozitív értékek.
Mert digráf grafikon mátrix egy kicsit más megjelenés. Az egyes cellái készült három érték egyikét. Felhívjuk figyelmét, hogy a nullák a két mátrix (ábra. 1 és 2), hogy ugyanabban a helyzetben, mivel mindkét esetben a gráf struktúra egyedül. Azonban, néhány pozitív egységek visszatettük a negatív, például, egy irányítatlan gráf cella (1, b) tartalmaz, 1 és -1 a digráf. Valóban, ez helyénvaló, mivel az első esetben, a szélén b nem foglalkozik, és a második - .. megcímzett, és ahol a bemeneti vertex vertex ez „1”.
Minden oszlop felel minden egyik szélét, így a grafikon leírtuk a mátrix esetén, mindig a következő jellemző: az egyes oszlopok a előfordulási mátrix két egység, 1 vagy -1, ha orientált szélén, a többi része - nullák .