IB AI HL Graph Theory

A graph is

a set of vertices and edges

An edge is

two joined vertices

A weighted graph is

a graph that has a value on each edge

An adjacency table is organized

from -> to, from/to

A transition table is organized

to -> from, to/from

Adjacent vertices are

connected by an edge

An unweighted graph is

a graph with no values

A walk is

any sequence of connected vertices

The degree of a vertex is

the number of edges at a vertex

A connected graph is

a graph where all vertices are joined

An unconnected graph is

a graph where some vertices aren't joined

A subgraph is

a graph that is contained within the original graph

A directed graph is

where all edges have a direction

An in degree is

the number of edges arriving at a vertex

An out degree

the number of edges leaving at a vertex

An adjacency matrix

is an adjacency table in matrix form

A graph is a connected directed graph when

a walk can be constructed in one direction

A graph is a strongly connected directed graph when

a walk can be constructed in both directions for all vertices

A loop is

an edge that starts and finishes at the same vertex

A simple graph is

a graph with no loops or multiple edges

A multigraph is

a graph that contains a loop or multiple edges

A transition matrix is

a transition table in matrix form

A transition matrix shows

the probability of each edge being travelled upon

An adjacency matrix shows

the number of connections between vertices

What does a Minimum Spanning Tree look for?

best method to connect all vertices

What does the Chinese Postman Problem look for?

best method to visit all edges of the graph

What does the Travelling Salesman Problem look for?

best method to visit all the vertices

A tree is

a connected graph with no cycles

A spanning tree is

a subgraph which is a tree and connects all vertices

What is the first step in Kruskal's algorithm?

find the edge of smallest weight in the graph

What is the second step in Kruskal's algorithm?

add the edge of smallest weight that does not form a cycle

What is the first step of Prim's algorithm?

select any vertex and add the edge of least weight

What is the second step of Prim's algorithm?

add edge of least weight to the tree that does not already connect to a vertex in the tree

Are graphs created using Kruskal's algorithm guaranteed to be connected?

no

Are graphs created using Prim's algorithm guaranteed to be connected?

yes

A trail is

a walk that does not repeat any edges

A circuit is

a trail that starts and finishes at the same vertex

A Eulerian Trail is

a trail that uses all edges of a graph

A Eulerian circuit is

a circuit that uses all edges of the graph

Eulerian trails or circuits are both about

using all edges of a graph

What kind of degree are all vertices in a Eulerian circuit?

even

At which vertices do trails begin?

all vertices with odd degrees

Can you have a Eulerian trail if all vertices have an odd degree?

no

Can you have a Eulerian circuit if all vertices have an odd degree?

no

A path is

a walk that uses all vertices once

A cycle is

a path that begins and ends in the same place and does not pass through any vertex more than once

A Hamiltonian cycle is

a path that passes through all the vertices and returns to the starting point

A complete graph is

when each vertex is connected to every other vertex

What do you use to find the minimum spanning tree?

Kruskal's, Prim's

What do you use to solve the Chinese Postman Problem?

Kruskal's, Prim's

What do you use to solve the Travelling Salesman Problem?

Nearest Neighbor, Deleted Vertex

What is the first step of the Nearest Neighbor algorithm?

create a table of distances

What is the second step of the Nearest Neighbor algorithm?

use distance table to go to nearest unvisited vertex, then return home at the end

What is the first step of the Deleted Vertex algorithm?

choose a vertex and remove it and all its edges

What is the second step of the Deleted Vertex algorithm?

find the minimum spanning tree

What is the third step of the Deleted Vertex algorithm?

find lower bound

How do you find the lower bound in a Deleted Vertex algorithm?

(# of vertices) x (lowest weight edge)

What is the fourth step of the Deleted Vertex algorithm?

repeat with a different vertex and choose

A Hamiltonian cycle is about

using all vertices of a graph