## Glossary

`Graph`

aka network`Vertex`

aka entity, node`Edge`

aka link, relationship, pair, triple, quad, tuple, line, arc

See Glossary of graph theory, Graph Measures & Metrics

## Directed graph

$G=(V,E)$, where $V$ is a set whose elements are called *vertices* (singular: vertex), and $E$ is a set of paired vertices, whose elements are called *edges*.

```
flowchart LR
a --> b
```

$E={(a,b)},V={a,b}$

This is common definition, there are more precise definitions for “subtypes”

- directed simple graph aka Directed Acyclic Graph (DAG)
- DAG corresponds to poset (partially ordered set)

- directed multigraph
- directed simple graph permitting loops
- directed multigraph permitting loops (Quiver)

## Directed labeled graph

aka edge-labeled, Node “Labeled Arc” Node (NLAN) $G=(V,E,i)$, where $i$ is a total function mapping each edge to some symbol (e.g. label) $i:V→Σ$

```
flowchart LR
a --connected--> b
```

$E={(a,b)},V={a,b},i((a,b))=connected$

## Directed multigraph

$G=(V,E)$, where $V$ is a set whose elements are called *vertices* (singular: vertex), and $E$ is a ~~set~~ multiset of paired vertices, whose elements are called *edges*.

```
flowchart LR
a --> b
a --> b
```

$E={(a,b),(a,b)},V={a,b}$

## Directed labeled multigraph 1

$G=(V,E,i)$, where $i$ is a total function mapping each edge to some symbol (e.g. label) $i:V→Σ$

```
flowchart LR
a --1--> b
a --2--> b
```

$e_{1}=(a,b),e_{2}=(a,b),E={e_{1},e_{2}},V={a,b},i(e_{1})=1,i(e_{2})=2$

## Directed labeled multigraph 2

**Second possible definition**

$G=(V,E)$, where $V$ is a set whose elements are called *vertices* (singular: vertex), and $E$ is a set of ~~paired vertices~~ triples, whose elements are called *edges*:

```
flowchart LR
a --1--> b
a --2--> b
```

$E={(a,1,b),(a,2,b)},V={a,b}$

## Bipartite graph

**Bipartite graph** is a graph whose vertices can be divided into two disjoint and independent sets
**Directed labeled multigraph** can be modeled as bipartite graph: vertices will be represented by first of disjoint sets and edges (labels) by the second set.

```
flowchart LR
classDef red fill:red
classDef blue fill:blue
a:::red
b:::red
1:::blue
2:::blue
a --> 1 --> b
a --> 2 --> b
```

## Hypergraph

A hypergraph, $H=(V,E)$, is a system of subsets of a given set of objects. $V$ denotes the set of vertices of the hypergraph, and $E⊆2_{V}$ denotes the set of hyperedges. A hyperedge $e∈E$ is merely a set of vertices, i.e. $e⊆V$, such that $∣e∣≥2$.

This is generalisation of graph - if all hyperdges is of size 2 it is just a graph.

Hypergraph visually can be represented as Euler digram, Zykov diagram etc.

Hypergraph can be modeled as bipartite graph. For example:

$e_{1}={a,b},e_{2}={b,c,d}$

```
flowchart TD
classDef red fill:red
classDef blue fill:blue
a:::red
b:::red
c:::red
d:::red
e1:::blue
e2:::blue
e1 --- a
e1 --- b
e2 --- b
e2 --- c
e2 --- d
```

If all hyperedges in hypergraph are of the same size ($∣e∣=k$) hypergraph is called **k-uniform**.

## Directed hypergraph

In directed hypergraph hyperedge (or hyperarc) is a pair of two sets $e=(e_{H},e_{T})$, where

$e_{H}⊆V,e_{H}=∅,e_{T}⊆V,e_{T}=∅,e_{H}∩e_{T}=∅and∣e∣=∣e_{H}∣+∣e_{T}∣$

Other way is to think about hyperedge as disjoint set, where we can distinguish two subsets “head” ($e_{H}$) and “tail” ($e_{T}$).

```
flowchart TD
a --- e1( ) --> c
b --- e1 --> d
a --- e2( ) --> e
e2 --> f
b --- e3( ) --> e
g --- e3
```

Directed hypergraph can be modeled as bipartite graph. For example:

$e_{1}=({a,b},{c,d}),e_{2}=({a},{e,f}),e_{3}=({b,g},{e})$

```
flowchart TD
classDef red fill:red
classDef blue fill:blue
a:::red
b:::red
c:::red
d:::red
e:::red
f:::red
g:::red
e1:::blue
e2:::blue
e3:::blue
a --> e1 --> c
b --> e1 --> d
a --> e2 --> e
e2 --> f
b --> e3 --> e
g --> e3
```

A **Backward** hyperedge, or simply **B-edge**, is a hyperedge $e=(e_{H},e_{T})$, with $∣e_{H}∣=1$ ($e_{2}$). A **Forward** hyperedge, or simply **F-edge**, is a hyperedge $e=(e_{H},e_{T})$, with $∣e_{T}∣=1$ ($e_{3}$).

Hypergraph which consists only from B- and F-edges (B-edges, F-edges) is called **BF-hypergraph** (B-hypergraph, F-hypergraph).

Incidence matrix for hypergraph is typically smaller than for graph and hypergraph can be used to “compress” graph:

e1 | e2 | e3 | |
---|---|---|---|

a | 1 | 1 | 0 |

b | 1 | 0 | 1 |

c | -1 | 0 | 0 |

d | -1 | 0 | 0 |

e | 0 | -1 | -1 |

f | 0 | -1 | 0 |

g | 0 | 0 | 1 |

## Labeled Property Graph

Labeled property graph (LPG) can be defined as extension of **directed labeled multigraph** - each vertex and edge can have properties: $G=(V,E,i,p_{v},p_{e})$, where $p_{v}:V→P[Σ→Σ∪⊥]$, $p_{e}:E→P[Σ→Σ∪⊥]$

$P$ is properties defined as **associative array** (aka dictionary, hash table). From mathematical point of view this is just a partial function.

In some papers properties are defined as ${(k,v)∣k,v∈Σ}$ (but this is not associative array, this is set of pairs).