Graph theory Flashcards
What is a graph?
A diagram with a set of points called vertices that are joined by lines called edges
What are adjacent vertices?
Two vertices that are at opposite ends of an edge (a common edge)
What does multiple edges mean?
Two or more edges which connect to the same pair of vertices.
What is a loop?
An edge in a graph that joins a vertex to itself
What is an isolated vertex?
A vertex that isn’t connected to any other vertex in a graph by an edge
What is the degree of a vertex?
The number of graph edges that touch that vertex
How many degrees does a loop add to a vertex?
Two
What is the sum of degrees?
The total number of degrees of each vertex added together
What is the in-degree of a vertex?
The number of edges coming into the vertex
What is the out-degree of a vertex?
The number of edges going out from that vertex
Give an example of a vertex and edge set.
Set of vertices: V = {A, B, C}
Set of edges: E = {AB, AD, AC, BC}
Give an example of an adjacency list.
A: B, D, E
B: A
C: D, E
D: A, C, E
E: A, C, D
The list indicates what each vertex is adjacent to
What is a null graph?
A graph made up of isolated vertices and no edges
What is a trivial graph?
A null graph with only one vertex
What are the features of a simple graph?
- No loops
- No multiple edges
- Number of vertices with an odd degree is even
What is the main feature of a connected graph?
There’s a path between each pair of vertices
What is the main feature of a disconnected graph?
There’s a pair of vertices with no path between them
What are the features of a non-directed/undirected graph?
Made up of vertices and non-directed edges
What is the main feature of a directed graph/digraph?
Each edge has an arrow to show the direction of movement
What is a simple digraph?
Directed graph with no loops or multiple edges
What is the main feature of a regular graph?
All vertices have the same degree
What are the features of a complete graph?
- Undirected
- Simple
- Every vertex is connected to every other vertex by an edge
What are the features of a weighted graph?
- Each edge is labelled with a number (weight) used to represent a quality associated with the edge (eg: distance, time)
- Can be directed or undirected
What is a subgraph?
A part of another graph with no new vertices or edges
What are the features of a bipartite graph?
- Vertices can be split into two groups
- Each edge of the graph joins a vertex in the 1st group to a vertex in the 2nd group
What is a complete bipartite graph?
Bipartite graph where every vertex in the 1st group is connected to every vertex in the 2nd group
What sort of adjacency matrix would “A” indicate?
One-stage matrix with no stopovers
What sort of adjacency matrix would “A²” indicate?
Two-stage matrix with one stopover
What sort of adjacency matrix would “A³” indicate?
Three stage matrix with two stopovers
What sort of adjacency matrix would “A + A²” indicate?
Matrix with one stopover at most
What sort of adjacency matrix would “A + A² + A³” indicate?
Matrix with two stopovers at most
What are the features of a planar graph?
- Undirected
- Can be drawn on a plane without any edges crossing
What is Euler’s formula?
For planar graphs: v + f - e = 2
v = number of vertices
f = number of faces
e = number of edges
