Math AI HL - Graph Theory

Complete Graph

Exactly one edge between each pair of vertices

Simple graph

No loops or multiple edges

Connected graph

if there is a path between any pair of vertices

Weighted graph

the edges are assigned numerical values like money or distance

Directed graph

The edges in a directed graph can only be travelled along in the direction indicated

Trail

a walk where no edges are repeated

Path

a walk where no vertices are repeated

Circuit

no edges are repeated + last vertex is the same as the first vertex

Cycle

Last vertex is the same as the first vertex

No vertices are repeated (except the first)

What is a tree

A connected graph that does not contain any cycles

Degree

number of edges in/out of the vertex/node

In degree = number of edges coming into the node

Out degree = number of edges leaving the node

can be even/odd

Strength of connection

Strongly connected = directed graph where every vertex is connected if you follow the directions

Weakly connected = directed graph where all vertices are connected if the directions are ignored

Adjacency Matrix

Shows the number of ways to get from vertex X to vertex Y.

M^n = number of walks of length ‘n’ in the graph.

The column sum of a transition matrix of a directed graph must be

equal to 1 (transition matrix has opposite to-from)

Algorithms for finding minimum spanning tree (summary of each)

Kruskal’s:
- Pick an edge of minimum weight

-Pick the next edge of minimum weight. Check if it creates a cycle, if not then put it on the list. Continue this process until every vertex is added.

Prim’s:
- Pick a vertex at random. Put it on the tree

-Join the tree created to the nearest vertex out of the tree

-Repeat until all vertices are connected

Eulerian Graphs

All vertices must have an even degree

Semi-eulerian

All vertices except two have even degrees

Chinese Postman Problem

A postman wants to visit all edges and return back to t

he origin in the most efficient way (minimum total weight)

EVERY EDGE

1. Determine the degree of each vertex

2. If all are even, add together all the weights. This will be the solution.

3. If there are 2 odd degrees, determine the path of least weight between the two and add this to the total of the weights of all the edges of the graph.

Hamiltonian Cycle

possess a cycle that visits every vertex

Travelling Salesman Problem

EVERY VERTEX

• must determine lowest upper bound and highest lower bound

Nearest Neighbour Algorithm

FOR UPPER BOUND

• Pick a starting vertex

• Pick the vertex of lowest weight not yet visited

• Repeat until all vertices have been used

• Add the final edge to return to the starting vertx

Deleted Vertex Algorithm

FOR LOWER BOUND

• Remove one vertex and all associated edges

• Construct the minimum spanning tree using P/K

• Add the 2 shortest edges connected originally to the starting vertex