00 - Graph - MM

Graphs are useful mathematical models for representing urban and transportation networks.

Directed graph

directed graph

A directed graph is a set of $N$ nodes and a set of $A$ arcs or links whose elements are ordered pairs of distinct nodes.

It is represented as

$G = (N, A)$

Nodes are usually numbered with integers.
Arcs are either named with integers, or with the pair of nodes they connect

For the example graoh above we would have:

\begin{aligned} N & = 1, 2, 3, 4, 5, 6, 7 \\ A & = {(1, 2), (1, 3), (2, 3), (2, 4), (3, 6), (4, 5), (4, 7), (5, 2), (5, 3), (5, 7), (6, 7)} \end{aligned}

Graph representation

Incidence matrix

07. Schematizzazione dell'offerta di trasporto#Matrice di incidenza

A graph is a just a diagram. We need to make calculations. We have to define a way to translate the graph into a mathematical instrument we can use.

Each graph can be written as a matrix, called incidence matrix.

Each row represents a node
Each column represents an arc or link

We can represent a graph through a matrix in which every row represents a node, and each column represents a link (links are also numbered).

The graph above gives the following incidence matrix:

[\begin{matrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & - 1 & 0 & 0 \\ - 1 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & - 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & - 1 & - 1 & - 1 & 0 & 0 & 0 & 1 & - 1 \\ 0 & 0 & 0 & 0 & - 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & - 1 & 1 & - 1 & 1 \end{matrix}]

Elements in a graph

Adjacency and Incidency

Forward star or Adjacency

forward star or adjacency of node $i$ ($e[i]$)

A forward star, or Adjacency of a node $i$ , is the set of head nodes of links emanating from node $i$ . It is designated by $E [i]$ .

For example, given the graph below:

the forward star of node $5$ is

E [5] = 2, 3, 7

By gathering the adjacency of all nodes, the number of links in A can be obtained:

| A | = | E [1] \cup E [2] \cup \dots \cup E [n] |

Incidency

incidency of node $i$

The incidency of node $i$ is the set of tail nodes of links incoming to node $i$ .

Out-degree and In-degree

outdegree of node $i$

The out-degree of node $i$ is the number of elements in the [[#Forward star or Adjacency]] of that same node $i$ .

$| E [i] |$

Path

A path is a chain of links, starting at node $p$ and ending at a different node $q$ .

Directed path

directed path

A directed path on a graph is a sequence of arcs
$a_{1} = (i_{1}, j_{1}), a_{2} = (i_{2}, j_{2}), . . ., a_{n} = (i_{n}, j_{n})$
so that
$j_{1} = i_{2}, j_{2} = i_{3}, . . ., j_{n - 1} = i_{n}$

Given the following graph

a possible directed path si:

path = (1, 2) (2, 3) (3, 6) (6, 7)

Undirected path

undirected path

An undirected path on a graph is a sequence of arcs
$a_{1} = (i_{1}, j_{1}), a_{2} = (i_{2}, j_{2}), . . ., a_{n} = (i_{n}, j_{n})$
so that

\begin{aligned} j_{1} = i_{2} \lor j_{1} & = j_{2} \lor i_{1} = i_{2} \\ j_{2} = i_{3} \lor j_{2} & = j_{3} \lor i_{2} = i_{3} \\ ⋮ \\ j_{n - 1} = i_{n} \lor j_{n - 1} & = j_{n} \lor i_{n - 1} = i_{n} \end{aligned}

Given the graph

An undirected path can be:

Undirected path = (1, 2) (2, 3) (5, 3) (5, 7)

Cycle

cycle

A cycle or directed cycle is a [[#Directed path]] with the additional condition
$j_{n} = i_{1}$

From the graph

a cycle is

cycle = (2, 4) (4, 5) (5, 2)

There can also be undirected cycles, where the direction of links doesn't matter.

Connected nodes

connected nodes

Node- $i$ is connected to node- $j$ if there exits a [[#Directed path]] starting at $i$ and ending at $j$ .

Tree

tree

A tree is a special type of graph that contains no cycles.

It can be directed or undirected.

Trees have the following characteristic:
$# nodes = # links - 1$

observation

A [[#Path]] is always a tree. More specifically, a [[#Directed path]] is always a directed tree.

BUT

A tree is not necesseraly a [[#Path]]

!700
%%🖋 Edit in Excalidraw%%

Spanning tree

spanning tree

A spanning tree is a part of graph $G$ , or subgraph, that contains all the same nodes of $G$ but with only a subset of links, so that they forma an undirected [[#Tree]].

Rooted spanning tree

There exist a node, called the root node, which is connected with any other node in the network.

Also, the undirected path from a root node to any other node in the tree is unique (it's a #Spanning tree).

Storing and retrieving paths

In a directed #Spanning tree, we can store paths in a simple matrix.

This tree can be stored as an array $p$ of pointers:

[\begin{matrix} index & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ p & 0 & 5 & 1 & 2 & 1 & 2 & 4 & 3 \end{matrix}]