Graph (Maths)

Graphs are a structure consisting of a set of objects called nodes, which are connected using a binary relation known as their edges. They are used extensively in modelling network-based problems, especially in computer science and electrical engineering

Definition §

A graph is a set, consisting of two smaller subsets for nodes and edges. It is notated as $G=\{V,E\},V=\{Vertices\},E=\{Edges\}$. $V$ is a set of vertices, and $E$ is a binary relation on $V$.

$$V=\{v_1,v_2,v_3,\dots v_n\}$$

$$E=\{(v_i,v_j)|v_i,v_j\in V\wedge v_i\text{ is connected to }{v}_j\}$$

$$G=\{V,E\}$$

Note that not all nodes need to be connected.

Terms §

Node Terms §

• Two nodes are said to be adjacent if an edge exists between them
• Degree : The number of edges connected to a given node is it’s degree. Depending if the graph is directed, the degree may be separated into:
  • In-degree: Number of edges pointing at the node, $v$
  • Out-degree: Number of edges exiting the node $v$

Graph Terms §

• Order: Number of vertices or nodes, i.e. the cardinality of $V$ = $|V|$
• Size: Number of edges of a graph, i.e. the cardinality of $E$ = $|E|$
• Diameter: The number of edges in the longest, shortest path between any pair of nodes. The diameter of a disconnected graph is always infinity.
• Graph Density: Define as the ratio of the size of the graph to the maximum possible size of a graph = $\frac{|E|}{\max (|E|)}$
• Transitive Closure: The transitive closure of $E$ on $V$. That is, a superset of $E$ is transitive, where an edge $(u,v)$ is created if a path exists from $u$ to $v$, through intermediate nodes.

Graph Types §

Graph Traversal §