# Graph is...

## # 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*.

$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 \to \Sigma$

$E = {(a,b)}, V = {a, b}, i((a,b)) = \text{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*.

$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 \to \Sigma$

$e_1=(a,b), e_2=(a,b), E = {e_1, e_2}, V = {a, b}, i(e_1) = \text{1}, i(e_2) = \text{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*:
$$
V = { (x,y,z) \mid x,z \in E \text{ and } y \in \Sigma }
$$

$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.

## # 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 \subseteq 2^V$ denotes the set of hyperedges. A hyperedge $e \in E$ is merely a set of vertices, i.e. $e \subseteq V$, such that $\lvert e \rvert \geq 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}$

If all hyperedges in hypergraph are of the same size ($\lvert e \rvert = 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 \subseteq V, e_H \neq \emptyset, e_T \subseteq V, e_T \neq \emptyset, e_H \cap e_T = \emptyset \text{ and } \lvert e \rvert = \lvert e_H \rvert + \lvert e_T \rvert$

Other way is to think about hyperedge as disjoint set, where we can distinguish two subsets “head” ($e_H$) and “tail” ($e_T$).

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

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 \to P[\Sigma \to \Sigma \cup \bot]$, $p_e: E \to P[\Sigma \to \Sigma \cup \bot]$

$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) \vert k,v \in \Sigma}$ (but this is not associative array, this is set of pairs).