#Type/Example #Topic/Linear_Algebra #Type/Definition

Types: N/A
Examples: N/A
Constructions: N/A
Generalizations: 7.1 Entry-by-Entry Definition of Matrix, 01 Set Theory

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

Undirected Graphs

An undirected graph $G$ consists of two finite sets $N$ and $E$ .

The set includes a list of objects called nodes (or vertices).
The set $E$ will be called the set of edges and includes a list of sets with two unique elements. Each edge will be called an undirected edge.

Example

Let's take a look at a graph with 4 nodes and 6 edges.

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

Remark. Notice, for undirected graphs, each edge is modeled as a set (not ordered pairs!).

{u_{1}, u_{2}} = {u_{2}, u_{1}}

Therefore, the order of the elements in the sets do not matter.
$⧫$

Each edge has exactly two nodes, and no nodes are connected to themselves. Let's enumerate these edges.

e_{1} = {u_{1}, u_{2}}, e_{2} = {u_{1}, u_{3}}, \dots, e_{6} = {u_{3}, u_{4}}

A good way to visualize this graph is to use a graph diagram. To do so, each node we draw as a dot and each edge a line segment connecting two nodes.

⚠ 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}$

We can use this diagram to create an undirected incidence matrix to capture the entire graph connectivity. To do so, we use the 7.1 Entry-by-Entry Definition of Matrix.

a_{i k} = \underset{for i \in [6], k \in [4]}{{\begin{cases} 1 & if edge i touches node k \\ 0 & otherwise \end{cases}}

To create this undirected incidence matrix, we set up the table which we use to read the entries of the incidence matrix.

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

Undirected graphs are a very useful tool for analyzing problems involving general connectivity between distinct objects. However, there are a number of modeling contexts where we may want to assign a direction to each edge. For this purpose ,we can create 7.5 Directed Graphs.

Therefore, the order of the elements in the sets do not matter. ⧫

Text Elements

Embedded files

Therefore, the order of the elements in the sets do not matter.
$⧫$