Unit2HOLIDAYREVISEFROEXAMSA+NEEDBYTERM4 Flashcards
(58 cards)
1
Q
Vertex
A
How many pints there are e.g. a,b,c,d connect to make a graph, so there are 4 points.
2
Q
Isolated vertex
A
not connected to nay vertex.
3
Q
Connected vertex
A
Has every vertex connected to every other vertex either either directly or indirectly via other vertices.
4
Q
Adjacency matrix
A
Mathematical representation of a diagram:
- 0= no direct connection.
- 1’s in diagonal=loop
- column all 0’s= isolated vertex.
5
Q
Planar graph
A
Graphs that can be drawn with no overlapping edges. They follow the Euler’s formula: v-e+f=2
6
Q
Isomorphic graph
A
- The same graph drawn in a different way.
- Same no of edges and vertices and the corresponding vertices have the same degree and the edges connect the same vertices.
7
Q
Complete graph
A
- A network where all vertices are connected directly to all other vertices without parallel edges or loops.
8
Q
Walks
A
- Starts at one vertex and follows any route to finish at another vertex.
- You must record the order you visit the edges.
9
Q
Trails
A
- A walk with no repeated edges.
10
Q
Paths
A
- A walk with no repeated edges or vertices.
11
Q
Circuit
A
- A walk with no repeated edges that starts and ends at the same vertex:
IN SUMMARY: - TAKE ANY ROUTE
- RECORD ROUTE
- START AND END AT SAME VERTEX
- NO REAPTED EDGES OR VETRICES
12
Q
Cycle
A
- A walk with no repeated edges or vertices that starts and ends at the same vertex.
13
Q
Eulerian trail
A
Follows every edge of a graph and will exist if it is:
- It is connected
- It has exactly tow vertices that have an odd degree.
14
Q
Eulerian circuit
A
Follows every edge and starts and ends at the same vertex.
- It is connected
- Has vertices of all even degree.
15
Q
Hamiltonian path
A
- Visits every vertex of graph once.
- Don’t have to start and end at the same vertex.
- No more than 2 vertices of degree 1.
16
Q
Hamiltonian cycle
A
- Visits every vertex of graph.
- Stars and ends at the same vertex.
17
Q
Subgraph
A
- A small part of a large graph that has some of the same vertices and edges as the larger one.
18
Q
Tree
A
- A connected graph:
- No cycles.
- No loops or edges.
- The number of edges can be calculated using (n-1), where n i the number of vertices.
19
Q
Spanning tree
A
- A connected graph:
- No cycles.
- No loops or edges.
- It is found by counting the no. of vertices (n) and removing enough edges so that there are n-1 edges, where n is the no. of edges and they should connect all vertices.
20
Q
Prims algorithm
A
A formula for determining the minimum spanning tree of a network.
21
Q
Bridge
A
-Is an edge in a connected graph, that if removed will cause the graph to be disconnected.
22
Q
Disconnected graph
A
- Are graphs that are not connected.
23
Q
Euler’s formula is?
A
- v-e+f=2
24
Q
Order of a matrix is always?
A
- row X column
25
In a square matrix where is the trailing diagonal
- Top right to bottom left.
26
In a square matrix where is the leading diagonal
- Top left to bottom right.
27
Symmetric matrix
- Square matrix
- Has leading diagonal
- The original matrix = transpose ...e.g. a=transpose of (a)
28
Zero matrix
- Matrix of any order with all elements as 0's.
- It is represented with the symbol (O).
29
Triangular matrix
Square matrix.
- Upper: when all the elements below the leading diagonal are 0's.
- Lower: when all the elements above the leading diagonal are 0's.
30
Identity Matrix
- Square matrix.
- Leading diagonal= all 1's.
- All other elements except leading diagonal=0.
- Represented with symbol (I).
- Anything times the identity matrix is= the same matrix.
31
How to transpose matrix on CAS?
- M-7-2.
32
Rules to add and subtract matrix?
- They must have same order.
33
Scaler multiplication of matrix?
- Instead of writing matrix b+b+b+b, we instead write 4b=4[ matrix]= [ matrix when it has been fully multiplied].
34
Rules to divide matrix
- You cannot divide a matrix and it will give you a value of undefined.
35
Post multiply?
- When it is matrix (A) * summing matrix.
36
Pre-multiply?
- When it is Summing matrix * matrix (A).
37
Summing matrix?
- A row or a column matrix where all the elements are 1 and is used to add all the elements in a matrix and give the answer as a single element.
38
Permutation matrix?
- Also an identity matrix.
- Has to be square.
- Only one (1's) per row.
39
Binary matrix?
- Can be any type of matrix.
- Only includes (1's) and (0's).
- Can include more than one (1's) per row.
40
Rules for matrix raised to a power?
- Only a square matrix can be raised to a power.
41
How to find the sum of the number of rows in a matrix?
- post multiply by the summing matrix.
42
How to find the sum of the number of columns in a matrix?
- pre-multiply by the summing matrix.
43
If matrix is symmetrical that means?
- That means that each row has to match the corresponding column
44
How to calculate the total one-step communication links?
- Add all of the elements up in each row, but keep them separate do not add all rows up together.
45
One step communication matrix?
- Draw matrix of the graph/communication.
46
How to find two step communication matrix from one step communication matrix?
- If one step matrix = c, THEN two step matrix= c^2.
47
How to find total of one-step and two-step communication matrix on CAS?
- Define one-step matrix (c).
- Input into CAS ( c+c^2).
48
A Dominance Matrix can used to represent?
- The result of a competition, argument or conflict between a group of people.
49
On step dominance matrix?
- Draw matrix of the graph/communication.
50
Properties of a one-step dominance matrix?
- Square matrix.
- Binary matrix.
- Leading diagonal as (0's).
- Not symmetrical.
- Sum of all elements= the number of games ( win/lose).
51
How to find two-step dominance matrix on CAS?
- Define normal matrix (d).
- Input into CAS ( d^2).
52
How to find total of one-step and two-step dominance matrix on CAS?
- Define one-step dominance matrix (d).
- Input into CAS ( d+d^2).
53
A transition matrix represents?
- Movement.
54
In a transition matrix elements in each column will always add up to?
- In a transition matrix elements in each column will always add up to 1.
55
In finace for investement rates we look for the?
- Lokk for the highest effective interest rate and we do this by using the CAS and typing in eff( rate, compounding periods in a year).
56
If there is a loop in a adjacency matrix it is represented as a ?
- ONE(1) in the matrix.
57
How to find inverse matrix by hand?
- A^-1 = 1/ det(a) x [ d -b ]
[ -c a ]
- det(a)= a X d - c X d , where matrix a= [ a b ]
[ c d ]
58
What does it mean if the determent is 0?
- There is not inverse and it is a single matrix.
