Definitions Flashcards
Efficiency
A measure of the run time of the algorithm and in most cases is proportional to the number of operations that must be carried out
Size
Is a measure of it’s complexity and so in the case of algorithms on graphs is the number of vertices on the graph
Order
Measure of its efficiency as a function of the size of the problem
‘Middle Item Position’ - With N items
Odd: 0.5(N+1)
Even: 0.5(N+2)
Graph
Consists of Points (Vertices or Nodes) which are connected by Lines (Edges or Arcs)
Subgraph
A graph, each of whose vertices belongs to the main graph and each of whose edges belongs to the main graph
Weight
A number associated to an edge of a graph
Becomes a weighted graph or network
Degree / Valency of a Vertex
The number of edges incident to it
A vertex can be odd or even
Path
A finite sequence of edges, such that the end vertex of one edge in the sequence is the start vertex of the next, and in which no vertex appears more than once
Cycle (Circuit)
A closed path - The end vertex of the last edge is the start vertex of the first edge
Connected
Two graphs are connected if there is a path between them
A graph is connected if all it’s vertices are connected
Digraph
The edges of a graph have a direction associated with them, they are directed edges, which form a digraph
Tree
A connected graph with no cycles
A spanning tree
Is a subgraph which includes all the vertices of the graph and is also a tree
Eulerian Graph
A graph with every vertex of even degree
Eulerian Cycle
A cycle that includes every edge of a graph exactly once
Semi-Eulerian Graph
A graph with exactly two vertices of odd degree
Planar Graph
A graph that can be drawn in a plane in such a way that no to edges meet each other except at a vertex to which they are both incident
Isomorphic
If they have the same number of vertices and the degrees of corresponding vertices are the same
Total Float Equation
Latest Finish Time - Earliest Start Time - Duration
