Graph Theory

Graph Theory

What is a Graph?

A graph is a bunch of nodes (the circles) connected by edges (the lines).

Quite similar to the binary search tree terminology

Paths of a Graph

A path is some nodes connected by edges.

AECF is a path. It is a simple path, because it has no repeated nodes.

ADEA is a path. It is a cycle, because it revisits the node A

Types of Edges

Directed edges are one-way edges.

A path such as FED is invalid, because the edge between E and F goes from E to F, not F to E.

Edges which do not look like arrows are two way edges.

Draw

Sometimes, you will be asked to draw a graph, given the vertices of the graph and the edges between vertices. You will be told if the graph is directed or not.

Draw a directed graph with vertices {A, B, C} and edges {AB, CA, AC, CC}

Adjacency Matrices

See how there is an edge from A to B? In the adjacency matrix, in the Ath row and Bth column, there is a 1, which represents this.

See how there isn't an edge from C to A? In the adjacency matrix, in the Cth row and Ath column, there is a 0, which represents this.

More Terminology

A graph is connected if every node can reach every other node

A graph is made up of connected components.

A tree is a special kind of graph without cycles. If it has n nodes, it has exactly n - 1 edges.

A complete graph has all possible edges

A dense graph has many edges, while a sparse one has a few

A tree is a graph which has one less edge than nodes. A tree has only one simple path between two nodes and no cycles

A directed graph with no cycles is called a DAG (directed acyclic graph)

Multiple Choice

How many cycles are in the following graph?

• 0

• 1

• 2

• 3

• 4

Multiple Choice

How many paths are there from A to C of length 2 or length 4?

Hint: The paths are not necessarily simple.

• 4

• 3

• 2

• 1

• 0