Final Flashcards
awdawdwad
What is a binary relation from A to B?
For sets A and B, a subset of A × B
What is a binary relationship on A?
Any subset of A × A
The number of relations from A to B is?
2^|A||B|
What is a function?
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
For the function f : A → B, What is the domain? The codomain?
Domain = A. Codomain = B.
What is the range of a function?
The subset of B consisting of
those elements that appear as second components in the
ordered pairs of f
What is a one to one function?
if each element of B appears at most once as the image
of an element of A.
How many one-to-one functions from A to B?
|B|^|A|
What is a onto function?
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
The number of onto functions from A to B, where
|A| = m, |B| = n and m ≥ n is?
n!S(m, n)
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
s(m.n)
The number of ways to distribute m distinct objects into n distinct containers, such that no container is left empty is
n!S(m, n)
What is a binary operation on A?
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 ).
What is a unary/monary operation on A?
A function g : A → A is called unary, or monary,
operation on A.
Example
g : Z → Z, where g(a) = −a.
What is a communitive function?
f (a, b) = f (b, a)
What is an associative function?
f for all
a, b, c ∈ A, f (f (a, b), c) = f (a, f (b, c))
What is an identity in a function?
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.
When can you use Combinations with Repetition?
Selecting r objects from a collection of n objects where
repetition is allowed and order doesn’t matter.
what is a homogenous vs non homogenous function?
When f (n) = 0 for all n ≥ 0, the relation is called
homogeneous; otherwise it is called
non-homogeneous
What is a trail?
No edge repeated. If There’s a Trail, There’s Path
What is a circuit?
Closed x-x trail
What is a path?
No vertex repeated
What is a cycle?
Closed x-x path
For any graph G = (V, E), the number of components
of G is denoted by what?
κ(G).
What is a complete graph?
a loop-free undirected graph, where
for all a, b ∈ V, a ̸= b, there is an edge {a, b}.
What is a pendant vertex?
A vertex of degree one?
What is the relationship between degree of vertices and edges in a undirected graph?
total deg of all vertices = 2 |E|
What is a regular graph?
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.
what is a n-cube?
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.
What is the minimum number of
colours needed to properly colour G called
chromatic number of G and is written χ(G).
What is a bipartite graph?
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.
What is the chromatic polynomial?
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.
What is a tree and a forest?
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.
What does a removal of a edge of a tree do?
Disconects; If a and b are vertices in a tree T = (V, E), then there
is a unique path that connects these vertices.
What is a spanning tree and a spanning forest?
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.
How do you know if a graph G is connected using trees?
If G = (V, E) is an undirected graph, then G is
connected if and only if G has a spanning tree.
What is the relationship between verticies and edges in trees?
In every tree T = (V, E), |V| = |E| + 1.
How many pendant verticies does a tree have?
For every tree T = (V, E), if |V| ≥ 2, then T has at
least two pendant vertices.
How many
distinct paths are there (as subgraphs) in a tree T?
(n choose 2)
What is the in and out degree?
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).
What is a directed tree?
If G is a directed graph, then G is called a directed tree
if the undirected graph associated with G is a tree
What is a rooted tree?
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.
What are leafs and branch nodes?
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).
What is a binary tree?
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.
What are m-ary trees?
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.
What is height and balance?
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.
What is distance in a weighted graph?
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
Distance from a Vertex to a Set
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)}
