Week 2 - Relations, Functions and Induction

Question 1

What is graph isomorphism?

Answer 1

A function that turns one representation of a graph into another (a graph showing the same information, but arranged differently)

Question 2

What is a function?

Answer 2

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

Question 3

What is the domain and target?

Answer 3

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

Question 4

What is the range of a function?

Answer 4

All the elements of a target space that are mapped by the function

Question 5

What is a GIPO?

Answer 5

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

Question 6

What is an onto/surjective function? What happens to the cardinality from A to B?

Answer 6

It maps to target elements at least once or more. |A| >= |B|

Question 7

What is an into/injective function? What happens to the cardinality from A to B?

Answer 7

It maps to target elements at most once, or none at all

|A| =

Question 8

What is a bijection? What happens to the cardinality from A to B?

Answer 8

It maps to all target elements exactly once. (both onto and into)

|A| = |B|

Question 9

What is a graph and what does it contain?

Answer 9

A set of vertices and edges. Vertices are the dots (node/neurons), edges are the lines (synapses)

Question 10

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 ____

Answer 10

adjacent, incident, neighbours

Question 11

What does the degree of a vertex mean?

Answer 11

The number of edges that emanate from it

Question 12

What is the edge multiplicity?

Answer 12

The number of edges that meet at a vertex

Question 13

What is a path and cycle? What is its length?

Answer 13

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)

Question 14

What is a forest? What is a tree?

Answer 14

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

Question 15

When does induction not work?

Answer 15

When its not indexed by natural numbers (i.e. bounded by a lower bound)

Question 16

How do you do a proof by induction?

Answer 16

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

Question 17

What does reflexive, symmetric, antisymmettric, transitive mean?

Answer 17

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)

Question 18

What are closure properties?

Answer 18

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

Question 19

Reflexive, transitive symmetric closues

Answer 19

basically transforming a set to contain these closures mean what numbers do you need to add to make that happen?

Question 20

What is an equivalence relation?

Answer 20

Something that is symmetrical, reflexive and transitive

Question 21

What is a partial ordering? What is a total ordering?

Answer 21

Partial ordering is reflexive, antisymmetric and transitive. Total ordering means every element needs to have a relationship with other elements

Question 22

What is a minimum element? What is a maximum element?

Answer 22

Minimum - it has no predecessor. Maximum - it has no successor