HL AI - Graph Theory

Adjacency Matrix

a matrix which records the number of direct links between vertices

Adjacent Edges

edges that share a common vertex

Adjacent Vertices

two vertices connected by an edge

Circuit

a walk that begins and ends at the same vertex with no repeated edges (Eulerian Circuit)

Complete Graph

a simple graph in which every vertex is connected to every other vertex by an edge

Connected Graph

a graph in which every vertex is reachable from every other vertex

Cycle

a walk in which the end vertex is the same as the start vertex and no repeated vertices

Degree of a Vertex

the number of edges connected to that vertex

Directed Graph

a graph whose edges have an indicated direction

Eulerian Circuit

a circuit that contains every edge of a graph

Eulerian Trail

a trail that contains every edge of a graph

Graph

consists of a set of vertices and a set of edges

Hamiltonian Cycle

a cycle that includes every vertex of a graph once

Hamiltonian Path

a path that visits each vertex exactly once

In Degree / Out Degree

number of edges leading towards a vertex and away from

Loop

an edge that connects a vertex to itself

Minimum Spanning Tree

a spanning tree with the least total weight

Path

a walk with no repeated vertices

Simple Graph

a graph with no loops or multiple edges

Spanning Tree of a Graph

a subgraph which includes all the vertices of the original graph and is also a tree

Strongly Connected Graph

a graph where every vertex is reachable from every other vertex (like a connected graph but it is also a directed graph)

Subgraph

a graph within a graph

Trail

a walk in which no edge appears more than once

Transition Matrix

a matrix that gives the probabilities of movement in a single step

Tree

a connected graph with no cycles

Undirected Graph

a graph in which the edges have no direction

Walk

a sequence of linked edges

Weighed Adjacency Table

a table in which the weight of the connecting edges is shown

Weighted Graph

a graph with numbers assigned to its edges.

Finding Lower Bound (TSP)

deleted vertex:

- delete a vertex

- find a minimum spanning tree

- add the length of the MST to the two shortest lengths connecting to the deleted vertex

Finding Upper Bound (TSP)

nearest neighbour:

- choose a starting vertex

- move to the closest neighbour

- repeat until you create a cycle

- find the length of the cycle

Chinese Postman Algorithm