Week 2 - Relations, Functions and Induction Flashcards
What is graph isomorphism?
A function that turns one representation of a graph into another (a graph showing the same information, but arranged differently)
What is a function?
Something that takes an element from set A as input and outputs a unique element. F(a) = b E B, or in other words f maps a to b
What is the domain and target?
Domain is the set which you’re mapping from, target is the set you’re mapping to f(x) = y, here x is the domain, y is the target
What is the range of a function?
All the elements of a target space that are mapped by the function
What is a GIPO?
Given input, produce output. This is different from a function because one input can produce multiple outputs (surjection), and unlike a function not all of the domain elements have to be mapped in a GIPO
What is an onto/surjective function? What happens to the cardinality from A to B?
It maps to target elements at least once or more. |A| >= |B|
What is an into/injective function? What happens to the cardinality from A to B?
It maps to target elements at most once, or none at all
|A| =
What is a bijection? What happens to the cardinality from A to B?
It maps to all target elements exactly once. (both onto and into)
|A| = |B|
What is a graph and what does it contain?
A set of vertices and edges. Vertices are the dots (node/neurons), edges are the lines (synapses)
Two vertices joined by an edge are _____, and the edge is ____ to each of those vertices. The vertices adjacent to vertex v, are called v’s ____
adjacent, incident, neighbours
What does the degree of a vertex mean?
The number of edges that emanate from it
What is the edge multiplicity?
The number of edges that meet at a vertex
What is a path and cycle? What is its length?
Path - a walk where no vertices are repeated
Cycle - the only repetitions are the first and last vertex.
The number of edges it has its its length (of a path or cycle)
What is a forest? What is a tree?
A graph with no cycles is a forest, and a connected graph with no cycles is a tree. A forest is a collection of trees
When does induction not work?
When its not indexed by natural numbers (i.e. bounded by a lower bound)
How do you do a proof by induction?
Start with a base case (i.e. n = 1), inductive hypothesis (Assume whatever you are going to prove is smaller than or equal to k). Finish with a inductive step where you consider the statement with k+1 as the variable
What does reflexive, symmetric, antisymmettric, transitive mean?
reflexive - (a,a), (b,b)
Symmetric - if (a,b) then (b,a)
Anti-symmetric - if (a,b) then (b,a) cannot exist, unless a=b
Transitive - if (a,b), (b,c) then (a,c)
What are closure properties?
A set of numbers is said to be closed for a specific mathematical operation if the result of the operation on any two numbers is the set itself a member of the set
Reflexive, transitive symmetric closues
basically transforming a set to contain these closures mean what numbers do you need to add to make that happen?
What is an equivalence relation?
Something that is symmetrical, reflexive and transitive
What is a partial ordering? What is a total ordering?
Partial ordering is reflexive, antisymmetric and transitive. Total ordering means every element needs to have a relationship with other elements
What is a minimum element? What is a maximum element?
Minimum - it has no predecessor. Maximum - it has no successor
