Graph is...

Last updated Aug 7, 2023

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

flowchart LR a --connected--> b

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

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

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

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

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 ($\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$).

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 \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).

Graphs