Decision 2: Graphs and Networks Flashcards
What is a graph?
Points (vertices/nodes) connected by lines (edges/arcs)
What is a vertex/node?
The point where the ends of two edges meet
What is an arc/edge?
A line joining dots together
What is a sub-graph?
A section of an original graph, containing some of the edges and nodes
What is degree/valency/order?
The number of arcs coming off a node
What is a path?
A non-repeating, finite sequence of connected vertices
What is a walk?
A path where vertices can be repeated
What is a trail?
A walk in which no edge is visited more than once
What is a cycle/circuit?
A path that returns to its starting position (start/end vertex is an exception to the path rules)
What is the handshaking lemma?
Sum of degrees = 2 x number of edges
The number of odd nodes must be even
What is always true for total valency?
Total valency is always even
What is a connected graph?
All vertices in the graph are connected; there are no constituent parts to the graph
What is a loop?
An edge that starts and ends at the same vertex, adding two to the valency
What is a simple graph?
A graph with no loops and no more than one edge connecting the same pair of vertices
What is a digraph?
A graph with edges that have a direction associated with them
What is a tree?
A connected graph that has no possible cycles
What is a spanning tree?
A tree subgraph containing all vertices from the original graph
What is a bipartite graph?
Two sets of vertices, X and Y, in which only vertices from different sets can be connected (i.e. X can only be connected to Y)
What is a complete graph? (2)
All nodes are directly connected to each other
Kn = n vertices
What is a complete bipartite graph? (2)
Every node from one set is connected to all nodes in the other set
K(n,m) = n vertices connected to m vertices
What is an isomorphic graph?
The same graph drawn differently
What is an adjacency matrix?
A matrix recording the number of direct links between each node
What is a distance matrix?
A matrix recording the distances between directly connected nodes
What is a Hamiltonian cycle?
A cycle that includes every vertex
What is the planarity algorithm used for?
To determine if a graph is planar (can be drawn so that no edges cross except at a vertex)
What is the planarity algorithm? (4)
Find a Hamiltonian cycle from the graph in question
Redraw the graph with the cycle as a polygon and the remaining sides within the polygon
Label one of the interior edges, I and list any edges that cross it, labelling them O unless two of them cross each other (meaning the graph is non-planar)
Work through the sides until all of them are labelled and then redraw the graph so that all of the I edges are inside the polygon and the O edges are around the outside
