Graph¶
$G = (V, E)$
$V = \{v_1, v_2, v_3, v_4, v_5, v_6, v_7, v_8, v_9, v_{10}, v_{11}\}$
$E = \{(v_1, v_2), (v_2, v_3), (v_2, v_6), (v_3, v_7) \cdots\}$
Graph¶
$|V| = 11$
$|E| = 11$
Directed and undirected graph¶
Walk¶
A $x-y$ walk is a finite sequence $$ (x, x_1), (x_1, x_2), \cdots, (x_n, y) $$
- closed walk: $x = y$, otherwise open walk
Trail¶
$x-y$ trail is a walk with no repeated edge.
Path¶
$x-y$ path is a walk with no repeated vertex.
Cycle¶
$x-x$ path is a cycle.
Circuit¶
$x-x$ trail is a circuit.
Degree¶
Degree of a vertex is the number of edges connected to the vertex.
$deg(v_1) = 5$
Regular graph¶
A graph in which each vertex has the same degree.
Complete graph¶
Simple graph¶
A graph without self-loop or multiple edge.
Multigraph¶
A graph with multiple edges.
Pseudograph¶
A non-simple graph in which both self loops and multiple edges are permitted.
Hypergraph¶
Allow an edge connected to multiple vertcies.
$$E = \{(v_1, v_2, v_3), (v_2, v_3), (v_3, v_5, v_6), (v_4)\}$$