Week 1 - 10 Flashcards
Bipartite graph
vertices can be divided into 2 sections
Complete graph
vertices are all connected to every other vertices
matching
a set of edges so that every vertex is incident with at most one vertex in the matching
perfect matching
a set of edges where each vertex is incident with exactly one vertex in the matching - solves the assignment problem
path
sequence of vertices joined together in edges
alternating path
edges in the path alternate from being in the matching and not in the matching
set
collection of objects
power sets
contains other sets
data structure
method of storing information so that a computer can access it
cartesian product
the set of all ordered pairs with the first element A and the second element from B
function
each input is mapped to exactly one input
symmetric difference
set of elements in exactly one of A or B
injective function
- one-to-one
- different arrows go to different locations
- if (a1, b) and (a2, b) both belong to f then a1 = a2
surjective function
- every element of the codomain there is an element of the domain relating to it
- image of f = B
bijective function
both injective and surjective
relation
a relation from A to B is a subset of the cartesian product A x B
reflexive graph
- every element has a self directed arrow loop
symmetric graph
- every arrow is two-way
- whenever (a, b) is contained in R, then (b, a) is in R
anti-symmetric graph
- no two-way arrows (exception for loops)
transitive graph
- if we can get from a to c in two steps, we can get there in one step
equivalence relation
- symmetric
- reflexive
- transitive
partial order
- anti-symmetric
- reflexive
- transitive
predicate
act likes a function which can take an element of the domain as input and produce a truth value as a output
existential quantifier
there exists x, an element of the domain such that … is true
universal quantifier
for every value of x such that … is true
¬ (universal quantifier(x)…)
existential quantifier(x)¬(…)
¬(existential quantifier(x)…)
universal quantifier(x)¬(…)
A ⇒ B is the same as …
(¬A) v B
arguments
- sequence of statements (premises) and a conclusion
- valid = accept the premises as being true then we must accept the conclusion as true
rules of interference
- list of premises of the argument
- use rules to produce logical statements
- eventually, produce the conclusion of the argument
conjunction elimination
j: A ^ B
= A (or B)
- ^ Elim j
conjunction introduction
j:A
k: B
= A ^ B
- ^Intro j, k
implication introduction
j:A
k:B
= A ⇒ B
- ⇒Intro j-k
implication elimination
j:A ⇒ B
= A becomes B
- ⇒Elim j,k
disjunction introduction
j:A
= A v B (or B v A)
- v Intro j
disjunction elimination
j: A v B
k: ¬A
= B
- v Elim j, k
negation introduction
j: A ⇒ (B ^ (¬B)
- ¬ Intro j
types of proof
- direct - X ⇒Y
- contrapositive - ¬X ⇒ ¬Y
- by contradiction - ¬X ⇒ (p ^ (¬p)
inductive proof
- check the base case - prove the property holds for 1 or 0
- hypthesis - states that it works up to an arbituary point int the integers - k
- prove that statement is past the arbituary point in the integers - k + 1
- if we accomplish these steps, we have proved the statement is true for all positive integers
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
uses of the well-ordering principle
- analysing running time for algorithms
- proving the correctness of algorithms
cardinality
the number of elements in a set - |A|
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
uncountable infinities
set of real numbers
addition principle
|A v B| = |A| x |B|
- does not work if A ^ B has one or more elements
mulitplication principle
|A x B| = |A| x |B|
permutation
ordering of the elements of the set
- let A be a set with |A| = n
- the number of permutations of A is n!
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)!
unordered selections
n!/(n-k)!k! = binomial coefficent
binomial theorem
(a + b)^n = the sum of (nCi)a^(n-i)b^i
pascals identity
(nk) = (n-1 k-1) + (n-1 k)
inclusion-exclusion
|A v B v C| = |A| + |B| + |C| - |A ^ B| - |A ^ C|- |B ^ C| + |A ^ B ^ C|
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
number theory
the study of integers and their properties
divisibility
assume p and q are integers. when we say p divides q we mean there exists an integer k such that q = kp
when does a sequence have a multiplicative inverse
- gcd(a, m) = 1
- a and m are coprime
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?
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
why use graphs
- helps to solve complex problems
- used in data structures
- visualisation
- used in search engines
d-regular graph
every vertex in G has d degrees
what is a degree
number of edges incident to a vertice
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
what to do to prove an equivalence relation between graphs
- reflexive: G is isomorphic to itself
- symmetric: if G1 is isomorphic to G2, then G2 is isomorphic to G1
- transitive: if G1 is isomorphic to G2 and G2 is isomorphic to G3, then G1 is isomorphic to G3
what is G’
a subgraph of G
what is a spanning sub-graph
if V(G’) = V(G) then G is a spanning sub-graph
what is a walk
a sequence of vertices and edges in a graph
- allow for repeated vertices and edges
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
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
what is meant by a closed (walk/path/trail)
v0 = vk
eurelian tour
a closed walk in a graph G that passes through every edge exactly once
eurelian theorem
a connected (multi)graph with at least one edge has a Eurelian tour if every vertex has an even degree
eurelian trail
a walk in graph G that passes through every edge exactly once (NOT CLOSED)
hamiltonian cycle
a cycle that visits every vertex exactly once
theorem 1.11
number of vertices with odd degree is even
adjacency list
associates each vertex in the graph with a list of its neighbours in some order
adjacency matrix
a rectangular array of numbers (called entries or elements) of the matrix
matrix addition
- same shape needed
- add each one in each position together
matrix multiplication
height of first matrix and length of second matrix
A^K
A multiplying itself k times
- shows the number of length k walks between the nodes
incidence matrix
vertices and edges
biadjacency matrix
- for a bipartite graph
- V(one group) x V(other group)
graph matching
a set of M of non-overlapping edges
graph perfect matching
a graph is a matching where every vertex is incident to an edge in the matching
maximum cardinality
maximum matching
saturated
v is incident to an edge in M
alternating path (graph)
if edges in P are alternating between M and not M
acyclic
graph with no cycles
tree
connected acyclic graph
leaf
vertex of degree one in a forest
any tree with at least two vertices has ….
at least two leaves
characterisation of trees
- G is a tree
- G is connected and has exactly n -1 edges
- G is acyclic and has n-1 edges
a spanning tree of a connected graph is a …
sub-graph of G, is a tree and contains all elements in V(G)
matrix equality
the matrices A and B are equal if they have the same order and their corresponding entries are equal
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}
square matrix
number of rows = number of columns
identity matrix
a diagonal matrix where all diagonal elements are equal to 1
transpose of a matrix
columns = rows
rows = columns
symmetric matrix
A = A^T
skew symmetric matrix
A^T = -A
euclidean plane
a geometric space where each point is represented by a pair of ordered real numbers
dot product
sum of each individual vertice pairs
- v1u1 + v2u2 + … + vnun
cosine rule
v . u = |v||u|cosA
cross product where
only in R^3
cross product (sin)
v x u = |v||u|sinA x n
n = unit vector perpendicular to v and u
cross product
