Graph

graph-theory

Graph

A graph is defined as a tuple of the sets of edges $E$ and the sets of vertices $V$.

$$G=(E,V)$$

Density

Definition

Graph Density

The density of a graph $G$ is given by dividing the number of edges by the number of vertices.

$$\epsilon (G)=\frac{|E(G)|}{|V(G)|}=\frac{{\alpha }_0}{{\alpha }_1}$$

Link to original

Handshaking Lemma

Definition

Handshaking Lemma

In a simple undirected graph $G$, it holds that:

$$\sum _{v\in V(G)}d(v)=2\cdot \left|E(G)\right|$$

where $d(v)$ is the degree of $v$.

In a directed graph $G$, it holds that:

$$\sum _{v\in V(G)}{d}^{+}(v)=\sum _{v\in V(G)}{d}^{-}(v)=\left|E(G)\right|$$

Link to original

Connected Graph

Definition

Zusammenhängender Graph

Connected Graph

A graph is called connected if exists an edge sequence from all $v$ to all $w$.

Or equivalently, a graph is called connected $G$ consists of exactly one connected component.

Strong Connectivity: A directed graph $G$ is called strongly connected if it is connected and respects the directions of the edges.

Weak Connectivity: A directed graph is called weakly connected if it is connect but does not respect the direction of the edges.

Link to original