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

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

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