A graph is made up of nodes connected by edges. Each edge connects two nodes, or a node to itself. If two nodes are connected by two or more edges we describe that graph as a multigraph. Two nodes connected by a graph are described to be adjacent, phew!

Walks, Trails, and Paths

A walk from node A to node B is a sequence of edges from A to B where the edges in the graphs share endpoints (an endpoint is one of the two terminating points of an edge).

A trail is a walk in which no edge is traversed more than once.

A path is a walk in which no node is traversed more than once

Connected Graphs

A connected graph is one where there is a walk from every node to every other node.

In a connected graphs the number of nodes in the graph is always less than or equal to one more than the number of edges.

Formally, let G be a connected graph, N be the set of nodes contained in the graph, and E be the set of edges contained in the graph. Then |N| ≤ |E|+1.

Cycles and Loops

A loop is an edge from a node to itself.

A cycle is a non empty trail (no edge repeated) from a node back to itself in which no node is repeated more than once.

If a graph has two different trails connecting two of its vertices then it has a cycle.

Eulerian Paths

A trail that uses all the edges exactly once. You can determine the existence of an eulerian path by examining the degree of each node. A node’s degree is the number of edges connected to it.

A connected graph only has an eulerian path if all of its nodes have an even degree or if exactly two of its nodes have an odd degree.

Subgraphs

A subgraph is basically what you imagine it to be, a graph containing some of the edges and nodes of the original.

A spanning subgraph is one that contains all the nodes of the original.

Prim’s Algorithm

Prim’s algorithm finds the shortest connected spanning subgraph.

The algorithm is as follows:

1. Select any node and mark it

2. Select the shortest unmarked edge that connects a marked node to any other unmarked node and mark both that edge and the connecting node, in the case of a tie choose arbitrarily

3. Repeat step 2 until every node is marked

4. The marked edges and nodes are the shortest spanning subgraph

It can be helpful to produce a table to demonstrate iterations

Dijsktra’s Shortest Path Algorithm

Given a connected graph Dijsktra’s shortest path algorithm finds the shortest path between two nodes.

1. Set the starting node N as the current node with a cost of 0

2. Mark the current node as visited. For each of its unvisited neighbours:

   1. Let P be the concatenation of the path associated with the current vertex plus the edge from the current vertex to its neighbour.
   2. If the neighbour has not been assigned a path assign it P.
   3. Otherwise, if the cost of the path associated with the neighbour is greater than P assign P to the neighbour.

3. Stop if the destination node M has been visited. Otherwise set the current node the unvisited node with the least cost and go to step 2.

It can be helpful to produce a table as you go:

Trees

A graph with no cycles is referred to as a tree.

Formally, the following properties are equivalent for a graph G of n nodes:

• G is a tree
• There exists one trail between any pair of nodes
• G is connected and has exactly n-1 edges
• G is connected and either n=1 and G has no edges or n≥2 and removing any edge makes G unconnected
• G has no cycles and adding any edge between non-adjacent nodes creates a cycle containing them

The easiest proof of a tree is:

G is connected and has exactly n-1 edges

For a connected graph, every connected spanning subgraph is a tree.

Rooted Trees

A rooted tree is one with a distinguished node, that is a vertex from which there is a path to any other node.

The height of the rooted tree is the length of the longest path from the root node.

Directed Graph

A directed graph or a digraph is a set of nodes and set of directed edges where each directed edge has a source and target node.

If there are nodes N and M with an arrow connecting N to M the following properties are true:

• N is adjacent to M
• N is an antecedent of M
• M is a successor of N

The underlying graph of a digraph is found by replacing the directed edges with undirected edges. A digraph is connected if the underlying graph is connected.