Week 1 - 10 Flashcards
(113 cards)
1
Q
Bipartite graph
A
vertices can be divided into 2 sections
2
Q
Complete graph
A
vertices are all connected to every other vertices
3
Q
matching
A
a set of edges so that every vertex is incident with at most one vertex in the matching
4
Q
perfect matching
A
a set of edges where each vertex is incident with exactly one vertex in the matching - solves the assignment problem
5
Q
path
A
sequence of vertices joined together in edges
6
Q
alternating path
A
edges in the path alternate from being in the matching and not in the matching
7
Q
set
A
collection of objects
8
Q
power sets
A
contains other sets
9
Q
data structure
A
method of storing information so that a computer can access it
10
Q
cartesian product
A
the set of all ordered pairs with the first element A and the second element from B
11
Q
function
A
each input is mapped to exactly one output
12
Q
symmetric difference
A
set of elements in exactly one of A or B
13
Q
injective function
A
- one-to-one
- different arrows go to different locations
- if (a1, b) and (a2, b) both belong to f then a1 = a2
14
Q
surjective function
A
- every element of the codomain there is an element of the domain relating to it
- image of f = B
15
Q
bijective function
A
both injective and surjective
16
Q
relation
A
a relation from A to B is a subset of the cartesian product A x B
17
Q
reflexive graph
A
- every element has a self directed arrow loop
18
Q
symmetric graph
A
- every arrow is two-way
- whenever (a, b) is contained in R, then (b, a) is in R
19
Q
anti-symmetric graph
A
- no two-way arrows (exception for loops)
20
Q
transitive graph
A
- if we can get from a to c in two steps, we can get there in one step
21
Q
equivalence relation
A
- symmetric
- reflexive
- transitive
22
Q
partial order
A
- anti-symmetric
- reflexive
- transitive
23
Q
predicate
A
act likes a function which can take an element of the domain as input and produce a truth value as a output
24
Q
existential quantifier
A
there exists x, an element of the domain such that … is true
25
universal quantifier
for every value of x such that ... is true
26
¬ (universal quantifier(x)...)
existential quantifier(x)¬(...)
27
¬(existential quantifier(x)...)
universal quantifier(x)¬(...)
28
A ⇒ B is the same as ...
(¬A) v B
29
arguments
- sequence of statements (premises) and a conclusion
- valid = accept the premises as being true then we must accept the conclusion as true
30
rules of interference
- list of premises of the argument
- use rules to produce logical statements
- eventually, produce the conclusion of the argument
31
conjunction elimination
j: A ^ B
= A (or B)
- ^ Elim j
32
conjunction introduction
j:A
k: B
= A ^ B
- ^Intro j, k
33
implication introduction
j:A
k:B
= A ⇒ B
- ⇒Intro j-k
34
implication elimination
j:A ⇒ B
= A becomes B
- ⇒Elim j,k
35
disjunction introduction
j:A
= A v B (or B v A)
- v Intro j
36
disjunction elimination
j: A v B
k: ¬A
= B
- v Elim j, k
37
negation introduction
j: A ⇒ (B ^ (¬B)
- ¬ Intro j
38
types of proof
1. direct - X ⇒Y
2. contrapositive - ¬X ⇒ ¬Y
3. by contradiction - ¬X ⇒ (p ^ (¬p)
39
inductive proof
1. check the base case - prove the property holds for 1 or 0
2. hypthesis - states that it works up to an arbituary point int the integers - k
3. prove that statement is past the arbituary point in the integers - k + 1
4. if we accomplish these steps, we have proved the statement is true for all positive integers
40
well-ordering principle
inductive proofs work because if P(x) is false for some choice of x, then it is false for some smallest choice of x
41
uses of the well-ordering principle
- analysing running time for algorithms
- proving the correctness of algorithms
42
cardinality
the number of elements in a set - |A|
43
countable infinities
- countably infinite if it has the same cardinality as Z+
- if the set is countable infinite, then there is a path which steps through all the elements of the set, one by one
44
uncountable infinities
set of real numbers
45
addition principle
|A v B| = |A| x |B|
- does not work if A ^ B has one or more elements
46
mulitplication principle
|A x B| = |A| x |B|
47
permutation
ordering of the elements of the set
- let A be a set with |A| = n
- the number of permutations of A is n!
48
ordered selections
- let A be a set with |A| = n
- the number of ways we can make an ordered selection of k elements of A is n!/(n - k)!
49
unordered selections
n!/(n-k)!k! = binomial coefficent
50
binomial theorem
(a + b)^n = the sum of (nCi)a^(n-i)b^i
51
pascals identity
(nk) = (n-1 k-1) + (n-1 k)
52
inclusion-exclusion
|A v B v C| = |A| + |B| + |C| - |A ^ B| - |A ^ C|- |B ^ C| + |A ^ B ^ C|
53
recursive definitions
F(n) = F(n-1) + F(n-2) because every sequence summing to n either ends with a 1 or with a number that is at least 3
54
number theory
the study of integers and their properties
55
divisibility
assume p and q are integers. when we say p divides q we mean there exists an integer k such that q = kp
56
when does a sequence have a multiplicative inverse
- gcd(a, m) = 1
- a and m are coprime
57
subset problem
input: a sequence of positive integers, and an integer c
question: is there a subset of {w1, w2 ... wt} that sums to c?
58
super-increasing
every number is larger than the sum of previous numbers.
- if a sequence is super-increasing we can easily solve the subset sum using the greedy approach
59
why use graphs
- helps to solve complex problems
- used in data structures
- visualisation
- used in search engines
60
d-regular graph
every vertex in G has d degrees
61
what is a degree
number of edges incident to a vertice
62
isomorphisim
a graph in which a single graph can have more than one form. that means two different graphs can have the same number of edges, vertices, and same edges connectivity
63
what to do to prove an equivalence relation between graphs
1. reflexive: G is isomorphic to itself
2. symmetric: if G1 is isomorphic to G2, then G2 is isomorphic to G1
3. transitive: if G1 is isomorphic to G2 and G2 is isomorphic to G3, then G1 is isomorphic to G3
64
what is G'
a subgraph of G
65
what is a spanning sub-graph
if V(G') = V(G) then G is a spanning sub-graph
66
what is a walk
a sequence of vertices and edges in a graph
- allow for repeated vertices and edges
67
what is a trail
a sequence of vertices and edges in a graph where all edges are distinct
- repeated vertices but not allowed repeated edges
68
what is a path
a sequence of vertices and edges in a graph where all vertices are distinct
- repeated edges but not allowed repeated vertices
69
what is meant by a closed (walk/path/trail)
v0 = vk
70
eurelian tour
a closed walk in a graph G that passes through every edge exactly once
71
eurelian theorem
a connected (multi)graph with at least one edge has a Eurelian tour if every vertex has an even degree
72
eurelian trail
a walk in graph G that passes through every edge exactly once (NOT CLOSED)
73
hamiltonian cycle
a cycle that visits every vertex exactly once
74
theorem 1.11
number of vertices with odd degree is even
75
adjacency list
associates each vertex in the graph with a list of its neighbours in some order
76
adjacency matrix
a rectangular array of numbers (called entries or elements) of the matrix
77
matrix addition
- same shape needed
- add each one in each position together
78
matrix multiplication
height of first matrix and length of second matrix
79
A^K
A multiplying itself k times
- shows the number of length k walks between the nodes
80
incidence matrix
vertices and edges
81
biadjacency matrix
- for a bipartite graph
- V(one group) x V(other group)
82
graph matching
a set of M of non-overlapping edges
83
graph perfect matching
a graph is a matching where every vertex is incident to an edge in the matching
84
maximum cardinality
maximum matching
85
saturated
v is incident to an edge in M
86
alternating path (graph)
if edges in P are alternating between M and not M
87
acyclic
graph with no cycles
88
tree
connected acyclic graph
89
leaf
vertex of degree one in a forest
90
any tree with at least two vertices has ....
at least two leaves
91
characterisation of trees
1. G is a tree
2. G is connected and has exactly n -1 edges
3. G is acyclic and has n-1 edges
92
a spanning tree of a connected graph is a ...
sub-graph of G, is a tree and contains all elements in V(G)
93
matrix equality
the matrices A and B are equal if they have the same order and their corresponding entries are equal
94
diagonal matrix
an n x n matrix A where A[i, j] = 0 for all i != j and at least one for A[i, i}
95
square matrix
number of rows = number of columns
96
identity matrix
a diagonal matrix where all diagonal elements are equal to 1
97
transpose of a matrix
columns = rows
rows = columns
98
symmetric matrix
A = A^T
99
skew symmetric matrix
A^T = -A
100
euclidean plane
a geometric space where each point is represented by a pair of ordered real numbers
101
dot product
sum of each individual vertice pairs
- v1u1 + v2u2 + ... + vnun
102
cosine rule
v . u = |v||u|cosA
103
cross product where
only in R^3
104
cross product (sin)
v x u = |v||u|sinA x n
n = unit vector perpendicular to v and u
105
unit vector
v/|v|
106
(|v|)^2 =
v.v
107
what 2 things can the distributive rule do in terms of maths
1. expand
2. factorise
108
what things should you look for to clarify if ordered pairs are not a function
1. repeated elements of A in the ordered pairs
2. elements of A do not appear in the ordered pairs at all
109
if a graph has no ordered pairs at all what is it
transitive
anti-symmetric
symmetric
110
if a graph only has self-directed loops what is it
reflexive
symmetric
anti-symmetric
transitive
111
what should an equivalence class look like
{a, b} {c, d, e} {g}
112
practice creating truth tables for predictate - week 3, activity sheet 3 q1, 3, 4
113
eurelian trail theorem
a connected graph with at least one edge has Eulerian trail if and only if it has either 0 or 2 vertices of odd degree
