Előfordulási mátrix

Az előfordulási mátrix az egyik gráfábrázolási forma , amelyben a gráf beeső elemei (él (ív) és csúcs) közötti kapcsolatokat jelzik . A mátrixoszlopok az éleknek, a sorok a csúcsoknak felelnek meg. A mátrixcellában a nullától eltérő érték a csúcs és az él közötti kapcsolatot (az előfordulásukat ) jelzi.

Irányított gráf esetén minden <x,y> ív a megfelelő oszlopba kerül: "1" az x-csúcs sorában és "-1" az y csúcs sorában; ha nincs kapcsolat a csúcs és az él között, akkor „0” kerül a megfelelő cellába.

Példa

Grafikon	Előfordulási mátrix
	${\begin{pmatrix}1&0&0&0&1&0&0\\1&1&0&0&0&1&0\\0&1&1&0&0&0\\0&0&1&1&0&0&1\\0&0&0&1&1&1&0\\0&0&0\0&0&0&1mátrix)$

A sorok az 1-től 6-ig terjedő csúcsoknak, az oszlopok pedig az e1-e7 éleknek felelnek meg. Például a 2. és 3. sorban a második oszlopban lévők azt jelentik, hogy az e2 él köti össze a 2. és 3. csúcsot.

Az ábrázolás jellemzői

Bármilyen grafikonhoz használható, még akkor is, ha van hurok.
Minden oszlop legfeljebb két 1-est tartalmazhat (ha ez az él egy hurok, akkor az 1-et azzal a csúcsponttal kell elhelyezni, amelyre a hurok esik). Irányított gráf esetén az oszlopnak 1-et és -1-et kell tartalmaznia.
Hipergráfok ábrázolására használható (ebben az esetben az oszlop kettőnél több 1-est is tartalmazhat)

Előfordulási mátrix

Példa

Az ábrázolás jellemzői

Lásd még

Jegyzetek

Irodalom