Final

Question 1

What is a binary relation from A to B?

Answer 1

For sets A and B, a subset of A × B

Question 2

What is a binary relationship on A?

Answer 2

Any subset of A × A

Question 3

The number of relations from A to B is?

Answer 3

2^|A||B|

Question 4

What is a function?

Answer 4

denoted f : A → B, is a relation from A to
B in which every element of A appears exactly once as
the first component of an ordered pair in the relation

Question 5

For the function f : A → B, What is the domain? The codomain?

Answer 5

Domain = A. Codomain = B.

Question 6

What is the range of a function?

Answer 6

The subset of B consisting of
those elements that appear as second components in the
ordered pairs of f

Question 7

What is a one to one function?

Answer 7

if each element of B appears at most once as the image
of an element of A.

Question 8

How many one-to-one functions from A to B?

Answer 8

|B|^|A|

Question 9

What is a onto function?

Answer 9

a function f that maps an element x to every element y. That means, for every y, there is an x such that f(x) = y

Question 10

The number of onto functions from A to B, where
|A| = m, |B| = n and m ≥ n is?

Answer 10

n!S(m, n)

Question 11

The number of ways in which it is possible to distribute
the m distinct objects into n identical containers, with no
container left empty, is

Answer 11

s(m.n)

Question 12

The number of ways to distribute m distinct objects into n distinct containers, such that no container is left empty is

Answer 12

n!S(m, n)

Question 13

What is a binary operation on A?

Answer 13

For any nonempty sets A, B, any function
f : A × A → B is called a binary operation on A. If
B ⊆ A, then the binary operation is said to be closed
(on A) (or A is closed under f ).

Question 14

What is a unary/monary operation on A?

Answer 14

A function g : A → A is called unary, or monary,
operation on A.
Example
g : Z → Z, where g(a) = −a.

Question 15

What is a communitive function?

Answer 15

f (a, b) = f (b, a)

Question 16

What is an associative function?

Answer 16

f for all
a, b, c ∈ A, f (f (a, b), c) = f (a, f (b, c))

Question 17

What is an identity in a function?

Answer 17

An
element x ∈ A is called an identity (or identity
element) for f if f (a, x) = f (x, a) = a, for all a ∈ A.

If f has an identity, then that identity is unique.

Question 18

When can you use Combinations with Repetition?

Answer 18

Selecting r objects from a collection of n objects where
repetition is allowed and order doesn’t matter.

Question 19

what is a homogenous vs non homogenous function?

Answer 19

When f (n) = 0 for all n ≥ 0, the relation is called
homogeneous; otherwise it is called
non-homogeneous

Question 20

What is a trail?

Answer 20

No edge repeated. If There’s a Trail, There’s Path

Question 21

What is a circuit?

Answer 21

Closed x-x trail

Question 21

What is a path?

Answer 21

No vertex repeated

Question 22

What is a cycle?

Answer 22

Closed x-x path

Question 23

For any graph G = (V, E), the number of components
of G is denoted by what?

Answer 23

κ(G).

Question 24

What is a complete graph?

Answer 24

a loop-free undirected graph, where for all a, b ∈ V, a ̸= b, there is an edge {a, b}.

Question 25

What is a pendant vertex?

Answer 25

A vertex of degree one?

Question 26

What is the relationship between degree of vertices and edges in a undirected graph?

Answer 26

total deg of all vertices = 2 |E|

Question 27

What is a regular graph?

Answer 27

An undirected graph (or multigraph) where each vertex has the same degree is called a regular graph. If deg(v) = k for all vertices v, then the graph is called k-regular.

Question 28

what is a n-cube?

Answer 28

n-cube or n-dimensional hypercube is the graph Qn = (V, E) where |V| = 2n and the vertices are labelled with n-bit binary strings v1, v2 ∈ E if and only if the labels for v1 and v2 differ in exactly one position.

Question 29

What is the minimum number of colours needed to properly colour G called

Answer 29

chromatic number of G and is written χ(G).

Question 30

What is a bipartite graph?

Answer 30

A graph G = (V, E) is called bipartite if V = V1 ∪ V2 with V1 ∩ V2 = ∅, and every edge of G is of the form {a, b} with a ∈ V1 and b ∈ V2. If each vertex in V1 is adjacent to every vertex in V2, we have a complete bipartite graph. In this case, if |V1| = m and |V2| = n, then the graph is denote by Km,n.

Question 31

What is the chromatic polynomial?

Answer 31

the chromatic polynomial of G, denoted P(G, λ), is the number of ways we can properly colour the vertices of G using at most λ colours.

Question 32

What is a tree and a forest?

Answer 32

Let G = (V, E) be a loop-free undirected graph. The graph is called a tree if G is connected and contains no cycles. If G contains no cycles, we call it a forest.

Question 33

What does a removal of a edge of a tree do?

Answer 33

Disconects; If a and b are vertices in a tree T = (V, E), then there is a unique path that connects these vertices.

Question 34

What is a spanning tree and a spanning forest?

Answer 34

A spanning tree for a connected graph is a spanning subgraph that is a tree. A spanning forest for a graph is a spanning subgraph that is a forest.

Question 35

How do you know if a graph G is connected using trees?

Answer 35

If G = (V, E) is an undirected graph, then G is connected if and only if G has a spanning tree.

Question 36

What is the relationship between verticies and edges in trees?

Answer 36

In every tree T = (V, E), |V| = |E| + 1.

Question 37

How many pendant verticies does a tree have?

Answer 37

For every tree T = (V, E), if |V| ≥ 2, then T has at least two pendant vertices.

Question 38

How many distinct paths are there (as subgraphs) in a tree T?

Answer 38

(n choose 2)

Question 39

What is the in and out degree?

Answer 39

the in degree of v is the number of edges in G that are incident into v. id(v). b) the out degree of v is the number of edges in G that are incident from v. od(v).

Question 40

What is a directed tree?

Answer 40

If G is a directed graph, then G is called a directed tree if the undirected graph associated with G is a tree

Question 41

What is a rooted tree?

Answer 41

When G is a directed tree, G is called a rooted tree if there is a unique vertex r, called the root, in G with id(r) = 0, and for all other vertices v, id(v) = 1.

Question 42

What are leafs and branch nodes?

Answer 42

In a rooted tree, a vertex with out degree 0 is called a leaf (or terminal vertex). All other vertices are called branch nodes (or internal vertices).

Question 43

What is a binary tree?

Answer 43

A rooted tree is called binary if for each vertex v, od(v) = 0, 1, or 2. If od(v) = 0 or 2 for all v, then the rooted tree is called a complete binary tree.

Question 44

What are m-ary trees?

Answer 44

Let T = (V, E) be a rooted tree and let m ∈ Z + . We call T an m-ary tree if od(v) ≤ m for all v ∈ V. When m = 2, the tree is called a binary tree. If od(v) = 0 or m, for all v ∈ V, then T is called a complete m-ary tree. The special case of m = 2 results in a complete binary tree. Let T = (V, E) be a complete m-ary tree with |V| = n. If T has ℓ leaves and i internal vertices, then (a) n = mi + 1; (b) ℓ = (m − 1)i + 1; (c) i = (ℓ − 1)/(m − 1) = (n − 1)/m.

Question 45

What is height and balance?

Answer 45

If T = (V, E) is a rooted tree and h is the largest level number achieved by a leaf of T, then T is said to have height h. A rooted tree T of height h is said to be balanced if the level number of every leaf in T is h − 1 or h.

Question 46

What is distance in a weighted graph?

Answer 46

Distance in a Weighted Graph Consider loop-free connected digraphs with weights assigned to the edges. Note: If (x, y) ̸∈ E, we define wt(x, y) = ∞. The length of a weighted directed path is the sum of the weights of each edge. The distance from a to b is d(a, b) = length of a shortest a − b path ∞ if no a − b path exists

Question 47

Distance from a Vertex to a Set

Answer 47

Distance from a Vertex to a Set For fixed v0 ∈ V and S ⊂ V with v0 ∈ S. Then S = V − S and we define the distance from v0 to S by d(v0, S) = min v∈S {d(v0, v)}