Definitions Flashcards
Graph
points (vertices or nodes) connected by lines (edges or arcs)
Subgraph
a graph each of whose vertices and edges belongs to another graph
Network =
weighted graph = graph with a number/weight associated with each edge
The degree or valency of a vertex is
the number of edges incident to it
A path is
a finite sequence of edges such that the end vertex of one edge in the sequence is the start vertex of the first edge
Two vertices are connected if
there is a path between them
A graph is connected if
all its vertices are connected
A cycle (circuit) is a
closed path i.e. the end vertex of the last edge is the start vertex of the first edge
Digraph =
edges of a graph have an associated direction
A tree is
a connected graph with no cycles (MS)
a spanning tree of a graph is
a subgraph which includes all the vertices of the graph and is also a tree - all nodes are connected (MS)
A minimum spanning tree is
a spanning tree such that the total length of its arcs is as small as possible = minimum connector =
a tree that contains all vertices and wight of tree is as small as possible (MS)
A bipartite graph
consists of two sets of vertices in X to vertices in Y, not vertices within a set
A matching is
a one to one pairing of elements between two sets
Decision variables
number of each of the things can be varied
Constrains
things preventing you from using an infinite number of each variable
Activity on arc network
activities represented by arcs and the completion of these activities, known as events, are shown as nodes.
The early event time is
the earliest time of arrival at the event allowing for the completion of all precceding activities
The late event time is
the latest time that the event can be left without extending the time needed for the project
Critical activity =
an activity which if its duration is increased or its delayed will increase the duration or delay the whole project
Handshaking lemma
sum of degrees = 2*number of edges as counting each end of each end
Walk =
path in which you are permitted to return to vertices more than once
Loop =
edge that starts and finishes at the same vertex (counts as two on a matrix)
Simple graph =
no loops, no more than one edge connecting any pair of vertices
Isomorphic graphs
show same information but are drawn differently - same number of edges and vertices - lines can be curved or straight
Distance matrices
records weight on the edges
useful to input networks onto a computer
can use Prims but not Kruskals
Planar graph =
no edges crossing each other
Hamiltonian cycle =
cycle visiting every edge of graph
Eulerian cycle =
cycle travels along every edge of the graph
adjacency matrix
records the number of direct links between vertices
A graph is traversable if it possible to
traverse (travel along) every arc just once without taking your pen off the paper - all valencies are even
A graph is semi-traversable if it
has two odd valencies - the start and finish point will be those two vertices
A graph is not traversable if
it has > 2 odd valencies
