1/44
Looks like no tags are added yet.
Name | Mastery | Learn | Test | Matching | Spaced |
---|
No study sessions yet.
Graph
Diagram showing lines connecting points
Vertex
One of the points in a graph
Edge
One of the connecting lines in a graph
Two vertices are adjacent if they are joined by an edge
Multiple edges
Two or more edges that connect the same vertices
Loop
An edge that joins a vertex directly to itself
Simple graph
One that has no loops or multiple edges
Degree of a vertex
The number of edges connected to that vertex (A loop is considered to be connected to its vertex twice)
The sum of the degrees in a graph will always be even since every edge joins two vertices
Directed graph
One in which all the edges have a direction- in this case the edges are usually called arcs
For an undirected graph
The sum of the degrees of the vertices equals twice the number of edges
Adjacency matrix
Shows the number of edges that join adjacent vertices
For a given network shows the number of one-step routes between the vertices eg M
M² gives number of two-step routes, M³ 3-step routes and so on
Symmetric about the leading diagonal
Means that you can go along each edge in either direction
Directed graph adjacency matrix
Shows the number of edges from one vertex to another, in that particular direction
Planar graph
A graph that can be drawn in the plane
A planar graph can always be drawn so that no two edges cross
Weighted graph
A graph in which each edge is labelled with a number used to represent some quantity associated with the edge
Connected graph
One in which there is a path between each pair of vertices, ie. a way of getting from each vertex to each other vertex via one or more edges
Bridge
An edge in a connected graph that, if removed, leaves a graph disconnected
Complete graph
A simple graph in which every vertex is joined to every other vertex by an edge. The complete graph with n vertices is denoted Kn.
A complete graph with n vertices
Has n(n-1) / 2 edges
Subgraph
A graph that consists of some (though not necessarily all) of the vertices and edges in the original graph
Bipartite graph
A graph whose set of vertices can be split into two distinct groups in such a way that each edge of the graph joins a vertex in the first group to a vertex in the second group
Every subgraph of a bipartite graph is also bipartite
Complete bipartite graph
A bipartite graph where every vertex of the first set is connected to every vertex of the second set
Number of edges in a complete bipartite graph
Is m x n, where m is the number of vertices in the first group and n is the number of vertices in the second group
Bipartite graph test
Start at any vertex and colour it eg white, then colour any vertex connected to it black, then move to hose vertices and continue to process through the network until all vertices are either white or black. If any edge has two white or two black vertices at its ends, then the graph is not bipartite. If every vertex has one white and one black vertex at its ends, then the graph is bipartite
Faces
Regions in a graph bounded by the edges, including the outer infinitely large region
Euler’s rule
States that for a connected planar grate, v + f — e = 2, where v is the number of vertices, f is the number of faces and e is the number of edges
Walk
Any route in a graph from one vertex to another vertex along the connecting edges
Doesn’t have to include all the vertices/edges, can repeat vertices/edges
Open walk
A walk that starts and finishes at different vertices
Closed walk
A walk that starts and finishes at the same vertex
Length of a walk
The number of edges it includes
Trail
A walk in which no edge is repeated
Open trail
Trail that starts and finishes at different vertices
Closed trail/circuit
A trail that starts and finishes at the same vertex
Path
A walk in which all of the edges and all the vertices are different (a path may start and finish at the same vertex)
Open path
A path that starts and finishes at different vertices
Cycle/closed path
A path that starts and finishes at the same vertex
Eulerian
A connected graph that has a closed trail (starts and ends at the same vertex) that includes every edge once and once only
May include repeated vertices
Have no vertices of odd degree- each vertex must be of even degree
Semi-Eulerian
If there is an open trail that includes every edge once only
Two vertices must be of odd degree, all others even
Can only be traversed by starting at one of the odd vertices and finishing at the other
Eulerian trail
A walk with no repeated edges that includes every edge in a graph
Open/Semi Eulerian trail
Will only exist if graph has exactly two vertices of odd degree
Closed Eulerian trail
A walk with no repeated edges that includes every edge in a graph and starts and finishes at the same vertex
Will only exist if graph has all vertices of even degree
Hamiltonian path
A path that includes every vertex in a graph once only
A path cannot have repeated edges
Does not have to visit every edge
Hamiltonian cycle
A cycle that includes each vertex in a graph (except the first) once only
Hamiltonian graph
A graph that contains a Hamiltonian cycle
Semi-Hamiltonian graph
A graph that contains a Hamiltonian path but not a Hamiltonian cycle
Graph will not be hamiltonian
If it contains a bridge