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.

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 $|e|\ge 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\subseteq V,e_H\ne \varnothing ,e_T\subseteq V,e_T\ne \varnothing ,e_H\cap e_T=\varnothing \text{ 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\to P[\Sigma \to \Sigma \cup \perp ]$, $p_e:E\to P[\Sigma \to \Sigma \cup \perp ]$

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