## Glossary

• Graph aka network
• Vertex aka entity, node
• Edge aka link, relationship, pair, triple, quad, tuple, line, arc

## Directed graph

, where is a set whose elements are called vertices (singular: vertex), and is a set of paired vertices, whose elements are called edges.

flowchart LR
a --> b


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

• directed simple graph aka Directed Acyclic Graph (DAG)
• directed multigraph
• directed simple graph permitting loops
• directed multigraph permitting loops (Quiver)

## Directed labeled graph

aka edge-labeled, Node “Labeled Arc” Node (NLAN) , where is a total function mapping each edge to some symbol (e.g. label)

flowchart LR
a --connected--> b


## Directed multigraph

, where is a set whose elements are called vertices (singular: vertex), and is a set multiset of paired vertices, whose elements are called edges.

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


## Directed labeled multigraph 1

, where is a total function mapping each edge to some symbol (e.g. label)

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


## Directed labeled multigraph 2

Second possible definition

, where is a set whose elements are called vertices (singular: vertex), and is a set of paired vertices triples, whose elements are called edges:

flowchart LR
a --1--> b
a --2--> 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, , is a system of subsets of a given set of objects. denotes the set of vertices of the hypergraph, and denotes the set of hyperedges. A hyperedge is merely a set of vertices, i.e. , such that .

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:

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 () hypergraph is called k-uniform.

## Directed hypergraph

In directed hypergraph hyperedge (or hyperarc) is a pair of two sets , where

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

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:

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 , with (). A Forward hyperedge, or simply F-edge, is a hyperedge , with ().

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:

e1e2e3
a110
b101
c-100
d-100
e0-1-1
f0-10
g001

## Labeled Property Graph

Labeled property graph (LPG) can be defined as extension of directed labeled multigraph - each vertex and edge can have properties: , where ,

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