Graphs and Networks Flashcards
What does a graph consist of
Points (vertices/nodes), the list of which may be referred to as the vertex set
Lines (edges/arcs), the list of which may be referred to as the edge set
Weighted graph or network
If a graph has a number (weight) associated with each edge
Subgraph of G
A graph, each of whose vertices belong to G and each of whose edges belong to G
A part of the original graph
The number of edges incident to a vertex
Degree/valency/order
A loop counts as 2
A vertex has either odd or even degree
Walk
A finite sequence of arcs such that the end vertex of one arc is the start vertex of the next
Path
A walk in which no vertex appears more than once
Trail
A walk in which no edge is visited more than once
Cycle/circuit
A closed path - finishes at the start vertex
Hamiltonian cycle
A cycle that visits every vertex exactly once
When is a graph connected?
If all its vertices are connected
Loop
An edge which starts and finishes at the same vertex
Simple graph
One with no loops and no more than one edge connecting any pair of vertices
Directed edges
Where the edges have a direction associated to them
Known as a digraph
Euler’s handshaking lemma
In any undirected graph, the sum of the degrees of the vertices is equal to 2x the amount of edges. As a consequence, the number of odd vertices must be even, including possibly zero.
Tree
A connected graph with no cycles
Spanning tree of a graph
A subgraph which includes all the vertices of a graph and is also a tree
Complete graph
A graph in which every vertex is connected by a single edge to every other vertex
Symbolised by K
no. of nodes
Isomorphic graphs
Have the same number of vertices of the same degree connected differently
Adjacency matrix
A table which shows the amount of connections between the vertices of a graph. Each entry describes the number of arcs joining the corresponding vertices
How many connections is a loop?
2
Distance matrix
The matrix associated with a weighted graph, the entries represent the weight of each arc, not the number, only write the weight if an edge connects them, no paths
Matrix for a directed graph
The values in the matrix represent the distance from the value on the left to the one on the top
Planar graph
One that can be drawn in a plane such that no two edges meet except at a vertex
When can you use the planarity algorithm?
When a graph contains a Hamiltonian cycle
Planarity algorithm setup
- Find a Hamiltonian cycle
- Draw a regular polygon with a neighbouring vertex for each connected vertices in the Hamiltonian cycle
- Draw the edges that weren’t in the Hamiltonian cycle inside the polygon
- Draw the polygon again with no edges inside
- Make a key to highlight the lines on the original polygon depending on whether they go on the inside or the outside.
Planarity algorithm execution
- Draw one edge from the first polygon on the inside of the second
- Note that line with an (i) next to it and then note any that cross that line with an (o) next to them and draw on the outside of the second polygon, ticking next to the note of the original line
- Work down the list noting any that cross the next line as in the opposite region to them
- Repeat until all lines have been drawn and ticked or it doesn’t work at which stage it isn’t planar
