incidatiematrix

Incidatiematrix is een wiskundige representatie die de relatie tussen de knopen en randen van een grafiek vastlegt. Voor een grafiek G = (V, E) met |V| knopen en |E| randen is de incidatiematrix B een |V| × |E| matrix. De kolommen komen overeen met randen en de rijen met knopen.

Voor een ongerichte grafiek heeft een kolom van B meestal precies twee 1-en, één voor elk knooppunt dat aan de betreffende rand is verbonden, en 0-en elders. Voor een gerichte grafiek (waar elke rand een richting heeft van bron naar doel) geldt: als rand e gaat van knoop u naar knoop v, dan is B(u, e) = -1, B(v, e) = +1, en alle overige entries zijn 0.

Eigenschappen en relaties: de rang van de incidatiematrix over de reële getallen is gelijk aan |V| − c, waarbij c het aantal verbonden componenten van de grafiek is (isolated knopen tellen mee). Incidatiematrices vormen een brug naar andere grafiekoperatoren; zo leidt B B^T tot de Laplaciaan L = D − A van een ongerichte grafiek, en ondersteunt het formuleringen van netstroom- en stromingsproblemen: B f = b beschrijft het evenwicht van stromen op knopen met f als randstromen en b als netto-inhoudingen bij knopen.

Toepassingen: incidentie-informatie wordt gebruikt in netwerkstromen, elektrische netwerken, berekeningen van de cykelruimte, en in algoritmen voor grafiekcompressie en (spectrale) analyse. In vergelijking met de adjacency- of afstandsmatrix biedt de incidatiematrix een compacte en operationele manier om verbindingen tussen knopen en randen te modelleren.