Ilmaantuvuusmatriisi

Insidenssimatriisi on yksi graafin esitysmuodoista , jossa on osoitettu graafin osuvien elementtien (reuna (kaari) ja kärki) väliset linkit. Matriisin sarakkeet vastaavat reunoja, rivit vastaavat pisteitä. Nollasta poikkeava arvo matriisisolussa ilmaisee kärjen ja reunan välisen suhteen (niiden esiintymisen ).

Suunnatun graafin tapauksessa kukin kaari <x,y> sijoitetaan vastaavaan sarakkeeseen: "1" x-pisteen riville ja "-1" kärjen y riville; jos kärjen ja reunan välillä ei ole yhteyttä, niin vastaavaan soluun laitetaan "0".

Esimerkki

Kaavio	Ilmaantuvuusmatriisi
	${\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&0&0&1\\0&0&0&1&1&1&0\\0&0&0\0&0&0&1)$

Rivit vastaavat pisteitä 1-6 ja sarakkeet reunoja e1-e7. Esimerkiksi toisessa sarakkeessa olevat 2. ja 3. rivillä tarkoittavat, että reuna e2 yhdistää kärjet 2 ja 3.

Tämän esityksen ominaisuudet

Käytetään kaikissa kaavioissa, vaikka silmukassa olisikin.
Jokaisessa sarakkeessa saa olla korkeintaan kaksi 1:tä (jos tämä reuna on silmukka, niin 1 sijoitetaan vastapäätä silmukan kärkeä). Suunnatun graafin tapauksessa sarakkeen tulee sisältää 1 ja -1.
Voidaan käyttää hypergraafien esittämiseen (jolloin sarake voi sisältää enemmän kuin kaksi 1:tä)

Ilmaantuvuusmatriisi

Esimerkki

Tämän esityksen ominaisuudet

Katso myös

Muistiinpanot

Kirjallisuus