A measure of the 'run time' sometimes proportional to the no. of operations carried out.
1 of 21
Size of an Algorithm
The complexity of the algorithm, in graphs this is how many vertices it has.
2 of 21
The order of an algorithm
A measure of its efficiency as a function of its size.
3 of 21
Graph
Consists of points (nodes or vertices) which are connected by lines (edges or arcs).
4 of 21
Subgraph
A graph whose vertices and edges belong to a graph
5 of 21
Weighted graph/Network
A graph where its edges are given numbers.
6 of 21
Degree/Valency of a vertex
The number of edges incident to it.
7 of 21
Path
A finite sequence of edges, such that the end vertex of one edge in the sequence is the start vertex of the next. In which no vertex appears more than once.
8 of 21
Cycle/Circuit
A closed path
9 of 21
Connected vertices
Two vertices are cnnected if they have a path between them.
10 of 21
Connected graph
A graph is connected if all the vertices are connected.
11 of 21
Directed edges
The edges have a direction associated with them.
12 of 21
Digraph
A graph made up of directed edges.
13 of 21
Tree
A graph with no cycles
14 of 21
Spanning tree
A subgraph of a graph which is a tree that connects all the nodes of the graph.
15 of 21
Eulerian graph
A graph in which every vertex is of even degree.
16 of 21
Eulerian cycle
A graph that includes every edge of a graph exactly once.
17 of 21
Semi-Eulerian graph
A graph that has exactly two vertices of odd degree.
18 of 21
Hamiltonian cycle
A cycle that passes through every vertex once and only once.
19 of 21
Planar graph
No two edges meet or cross except at a node.
20 of 21
Isomorphic graphs
Two graphs that have the same number of vertices and the degrees of the correspnding vertices are the same.
21 of 21
Other cards in this set
Card 2
Front
The complexity of the algorithm, in graphs this is how many vertices it has.
Back
Size of an Algorithm
Card 3
Front
A measure of its efficiency as a function of its size.
Back
Card 4
Front
Consists of points (nodes or vertices) which are connected by lines (edges or arcs).
Back
Card 5
Front
A graph whose vertices and edges belong to a graph
Comments
No comments have yet been made