In graph theory, a vertex is incident with an edge if the vertex is one of the two vertices the edge connects. An incidence is a pair ( u , e ) {\displaystyle (u,e)} where u {\displaystyle u} is a vertex and e {\displaystyle e}
is an edge incident with u {\displaystyle u} . Two distinct incidences ( u , e ) {\displaystyle (u,e)} and ( v , f ) {\displaystyle (v,f)} are adjacent if and only if u = v {\displaystyle u=v} , e = f {\displaystyle e=f} , or the edge u v {\displaystyle uv} equals e {\displaystyle e} or f {\displaystyle f} . A graph can be formally defined as an ordered triple ( V , E , ψ ) {\displaystyle (V,E,\psi )} , where V {\displaystyle V} is the set of vertices, E {\displaystyle E} is the set of edges, and ψ {\displaystyle \psi } is an incidence function (or incidence mapping) that maps each edge to a pair of vertices. For an edge e ∈ E {\displaystyle e\in E} , if ψ ( e ) = ( u , v ) {\displaystyle \psi (e)=(u,v)} , then u {\displaystyle u} and v {\displaystyle v} are called the end-vertices (or endpoints) of the edge e {\displaystyle e} , and the edge e {\displaystyle e} is said to be incident with vertices u {\displaystyle u} and v {\displaystyle v} . A graph can also be specified as an incidence structure S = ( P , B , I ) {\displaystyle S=(P,B,I)} , where P {\displaystyle P} is a set of "points" (the vertices), B {\displaystyle B} is a set of "blocks" (the edges), and I {\displaystyle I} is the incidence relation between them.
Incidence matrix
The incidence matrix of an undirected graph G = ( V , E ) {\displaystyle G=(V,E)} without self-loops is an n × m {\displaystyle n\times m} matrix A = a i j {\displaystyle A=a_{ij}} , where n = | V | {\displaystyle n=|V|} is the number of vertices and m = | E | {\displaystyle m=|E|} is the number of edges. The rows correspond to vertices and the columns correspond to edges, with
a i j = { 1 if vertex v i is incident with edge e j , 0 otherwise. {\displaystyle a_{ij}=\left\{{\begin{array}{rl}\,1&{\text{if vertex }}v_{i}{\text{ is incident with edge }}e_{j},\\0&{\text{otherwise.}}\end{array}}\right.}
… excerpt ends here. Continue reading the full article.
