Incidenční matice

Incidenční matice je jednou z forem znázornění grafu , ve které jsou vyznačeny vazby mezi dopadajícími prvky grafu (hrana (oblouk) a vrchol). Sloupce matice odpovídají hranám, řádky odpovídají vrcholům. Nenulová hodnota v buňce matice udává vztah mezi vrcholem a hranou (jejich výskyt ).

V případě orientovaného grafu je každý oblouk <x,y> umístěn v odpovídajícím sloupci: "1" v řádku vrcholu x a "-1" v řádku vrcholu y; pokud mezi vrcholem a hranou není žádné spojení, pak se do příslušné buňky vloží „0“.

Příklad

Graf	Incidenční matice
	${\begin{pmatrix}1&0&0&0&1&0&0\\1&1&0&0&0&1&0\\0&1&1&0&0&0&0\\0&0&1&1&0&0&1\\0&0&0&1&1&1&0\\0&0&0&0\0&0&0{1)$

Řádky odpovídají vrcholům od 1 do 6 a sloupce odpovídají hranám e1–e7. Například ty ve druhém sloupci ve 2. a 3. řádku znamenají, že hrana e2 spojuje vrcholy 2 a 3.

Vlastnosti této reprezentace

Používá se pro jakékoli grafy, i když existuje smyčka.
Každý sloupec musí obsahovat maximálně dvě jedničky (pokud je tato hrana smyčka, pak se jednička umístí naproti vrcholu, ke kterému smyčka dopadá). V případě orientovaného grafu by měl sloupec obsahovat 1 a -1.
Lze použít k reprezentaci hypergrafů (v takovém případě může sloupec obsahovat více než dvě jedničky)

Incidenční matice

Příklad

Vlastnosti této reprezentace

Viz také

Poznámky

Literatura