D1, C2 - Graphs & Networks Flashcards
What are the points on graphs called
Vertices or Nodes
What are the lines on graphs called
Edges or Arcs
What is a graph that has number associated with an edge or arc called
Weighted graph or Network
What is a vertex set
A set of all the vertices
e.g. A, B, C, …
What is a edge set
A set of all the edges
e.g. AB, AC, BC, …
What is a subgraph
A part of a graph
What is the degree / valency / order of a vertex
The number of edges incident (coming out of the vertex)
What are the types of degree for a vertex (2)
Odd
Even
What is a walk
Any route through a graph from a vertex to a vertex
What is a path
A walk in which no vertex is visited more than once
What is a trail
A walk in which no edge is visited more than once
What is a cycle
A walk in which the start and end vertex are the same. No other vertex is visited more than once
What is a Hamiltonian cycle
A cycle that includes every vertex
What is a connected graph
A graph will all of its vertices connected
What is a loop
An edge that starts and finishes at the same vertex
What is a simple graph
A graph with no loops and at most one edge connecting any pair of vertices
What is a directed graph (digraph)
A graph where all the edges are directed, i.e. have direction arrows on them
What is an undirected graph
A graph where the sum of the degrees (of the vertices) is equal to 2 * number of edges
Number of odd vertices = even (or zero)
Euler’s Hand-shaking Lemma
A graph has 5 nodes and 8 edges. The valencies of the nodes are x, x-1, x+1, 2x-1, x-1. Find x
By Euler’s Hand-shaking Lemma
Total valency = 2 * number of edges
x + x-1 + x+1 + 2x-1 + x-1 = 2 * 8
6x - 2 = 16
x = 3
What is a tree
A connected graph with no cycles
What is a spanning tree
A subgraph that includes all the vertices of a graph and is also a tree
What is a complete graph
A graph where every vertex is connected to every other vertex
What are isometric graphs
Graphs which show the same information drawn differently
What must be the same with isometric graphs
Number of edges
Number of vertices
Same valencies
What does it mean if a complete graph is Kn
n is the number of vertices of the complete graph e.g. K5 is a complete graph with 5 vertices
What does an adjacency matrix show
The number of edges between the vertices (0’s down the middle unless there is a loop)
What does a distance matrix show
The weight of the arc between vertices
(-‘s down the middle)
Can you construct a graph given an:
a) Adjacency matrix
b) Distance matrix
a) YES
b) NO
If a graph is not directed, what does it mean for a distance matrix
Matrix should be ‘symmetrical’
What goes down the middle diagonal for an adjacency matrix
0’s unless there is a loop which would be a 2
What should you put in a distance matrix cell if there is no weight between the vertices
-
If I selected the column which is (B, D) what does this mean (what goes to what)
B goes to D
Are distance matrices or adjacency matrices always symmetrical
Adjacency matrices
What is a planar graph
A graph where edges only meet at a vertex (arcs don’t cross over)
What are the steps for The Planarity Algorithm (6)
1) Find a Hamiltonian Cycle
2) Draw this cycle as a polygon
3) Add in any other edges from the original graph (draw these inside the polygon)
4) List all the edges inside the polygon (may be useful to do at the start)
5) Choose any edge on the list and label it I (I for inside)
6) Look for unlabelled edges that cross ‘I’, if these edges cross each other the graph is NOT planar. If they don’t label them ‘O’ (outside). Repeat 5 until all edges are labelled (if all edges are labelled it is PLANAR)
How do you know if the Planarity Algorithm finds a planar graph
All edges will be labelled O or I
What does it mean if when performing the planarity algorithm, 2 edges labelled O (outside) intersect (or two labelled I intersect)
The graph is NOT planar
