Types: N/A
Examples: N/A
Constructions: N/A
Generalizations: 7.1 Entry-by-Entry Definition of Matrix

Properties: N/A
Sufficiencies: N/A
Questions: N/A

Directed Graph

A directed graph consists of two sets $N$ and $E$ of nodes and edges. The set $E$ is a finite list of directed edges written

e_{i} \in N \times N = {(u, v) : u \in N and v \in N}

The set $N$ contains a finite number of objects known as vertices/nodes
The set $E$ contains a finite list of directed edges. Each directed edge is an ordered pair in $N \times N$ .

Adjacency Matrix for Directed Vertices

Let's create a directed graph with four vertices and five edges given by

\begin{aligned} N & = {u_{1}, u_{2}, u_{3}, u_{4}} \\ E & = {(u_{1}, u_{4}), (u_{2}, u_{1}), (u_{2}, u_{3}), (u_{4}, u_{3}), (u_{4}, u_{2})} \end{aligned}

Let's enumerate $E$ . We enumerate our edges by assigning indices in the order in which the edges are listed.

\begin{aligned} e_{1} & = (u_{1}, u_{4}) \\ e_{2} & = (u_{2}, u_{1}) \\ ⋮ \\ e_{4} & = (u_{4}, u_{2}) \end{aligned}

If $e_{i} = (u_{j}, u_{k})$ we will need to impose direction.

⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠

Text Elements

y
x

Embedded files

390479cd01ced13c64236fbaaed3aafa5a43245a: ${\vec{v}}_{1}$
b8b113db58287809b44243063d1974450d176baf: ${\vec{v}}_{2}$
5c41b34ba97ca8622399cfa815dfa811fde7040e: ${\vec{v}}_{3}$
0f8f8f5c6ed5e80c679f8e54649f72374c6d95f4: $u_{1}$
3b87b040aee9b2a4eb893d8ab53aba7a8b088bd9: $u_{2}$
50eb7876289650fcef6936fe6675261b606f1674: $u_{4}$
9cb8418b2d971489c553a80d798dbfc1ba984863: $u_{3}$
900307fc7db61df0da83813e9396c07fa243a877: $e_{1}$
9270a528e052d5f9f74169cea4670113cec6ed76: $e_{2}$
8e5065926355c57f048f75ddd7b58546c7e045c2: $e_{4}$
6ac6ccb77a0d5d361c9c1ab993422cefcc3901ed: $e_{5}$
fd71834e3854c793dccb0ff4b77a6a9884754adb: $e_{3}$
3e3e87b5a37796bb10bf21306efe03dda9b7fa2c: $e_{6}$
f2a0bfe9d38acd431768cf59caaa20c5c3b905db: $u_{j}$
2a9921dd768987dc5143ee2f47601f7022e653ff: $u_{k}$
663d27fc4e6238a96ee08cb5a9c0212e584648ea: $u_{1}$
f46bbfbed8baeb8a8909295fdb280f1d4653d3b5: $u_{2}$
583c3b266fbec0a3e557d1933329381cea56e145: $u_{4}$
58ac8859f8870a71ad16e2a7a038cba44e805d36: $u_{3}$
abb31f2b1eed1de1af16f7f31404fe5cf2126da1: $e_{1}$
924cf332c24ce8d1dca7dd5e9066e67ab56d224e: $e_{2}$
0faa5757f10897e78d1a958a11b23de2eb8785fb: $e_{3}$
64d079b1d130fee951ac766c786cec5998763d82: $e_{4}$
9d2b1f92d2ce2fc0bf88e8d93d8ad2e30079beee: $e_{5}$

The $i$ th edge comes out of $u_{j}$ and goes into $u_{k}$ .
Edge $i$ is incident out of node $u_{j}$ and incident into node $u_{k}$ .
We say $u_{j}$ is the initial node of edge $e_{i}$ and $u_{k}$ is the terminal node of edge $e_{i}$ .

Let's draw a graph diagram.

⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠

Text Elements

y
x

Embedded files

Let's construct an 7.1 Entry-by-Entry Definition of Matrix with

a_{i k} = {\begin{cases} + 1 & \underset{(incident out of)}{if edge e_{i} leaves node u_{k}} \\ - 1 & \underset{(incident into)}{if edge e_{i} goes into node u_{k}} \\ 0 & otherwise \end{cases}

Now, let's create a matrix using a direct graph incident table. We let the rows of the matrix represent the edges and the columns represent the nodes of our digraph.

\begin{aligned} \begin{array}{cccc} u_{1} & u_{2} & u_{3} & u_{4} \\ e_{1} & 1 & 0 & 0 & - 1 \\ e_{2} & - 1 & 1 & 0 & 0 \\ e_{3} & 0 & 1 & - 1 & 0 \\ e_{4} & 0 & 0 & - 1 & 1 \\ e_{5} & 0 & - 1 & 0 & 1 \end{array} & A = [\begin{array}{c} 1 & 0 & 0 & - 1 \\ - 1 & 1 & 0 & 0 \\ 0 & 1 & - 1 & 0 \\ 0 & 0 & - 1 & 1 \\ 0 & - 1 & 0 & 1 \end{array}] \end{aligned}