Worksheetsdc1-23
Total questions: 50
Worksheet time: 25mins
A vertex of a graph is called pendant if
its degree equals 0
its degree equals 2
its degree equals 1
it is not isolated
there is no true answer
A vertex of a graph is called isolated if
there is no true answer
its degree equals 0
its degree equals 2
its degree equals 1
it is not pendant
A subgraph of a graph G = (V, E) is
a graph H = (W, F) where W⋂V≠∅ and F⋂E≠∅
a graph H = (W, F) where W ⊆ V and F ⊆ E
a graph H = (W, F) where V⊂ W and E ⊂ F
a graph H = (W, F) where W ≠ V and F ≠ E
a graph H = (W, F) where W⋂V=∅ and F⋂E=∅
The union of two simple graphs G1=(V1,E1) and edge set G2=(V2,E2) is
the undirected graph with vertex set V1 ⋃ V2 and edge set E1 ⋃ E2 such that |E1⋃E2|=|E1|+|E2|.
the undirected graph with vertex set V1 ⋃ V2 such that |V1⋃ V2|=|V1|+|V2| and edge set E1 ⋃ E2
the multigraph with vertex set V1⋃ V2 and edge set E1 ⋃ E2 such that |E1 ⋃ E2|=|E1|+|E2|
the simple graph with vertex set V1 ⋃ V2 and edge set E1 ⋃ E2
the simple graph with vertex set V1 ⋂ V2 and edge set E1 ⋂ E2
A directed graph differs from a directed multigraph since
every directed multigraph has multiple edges and has no loops
every directed multigraph has multiple edges
every directed graph has multiple edges and has no loops
every directed graph has loops and multiple edges
every directed multigraph has loops and has no multiple edges.
A pseudograph differs from a multigraph since
every pseudograph has multiple edges and has no loops
every multigraph has loops and has no multiple edges
every multigraph has multiple edges and has no loops
every multigraph has no multiple edges and loops
every pseudograph has no multiple edges and loops
A simple graph differs from a multigraph since
every multigraph has loops
every multigraph has multiple edges or loops
every simple graph has loops
every simple has loops or multiple edges
every multigraph has multiple edges
Which of the following simple graphs does exist?
a simple graph with seven vertices of degrees 0, 1, 1, 2, 3, 4, 6.
a simple graph with four vertices of degrees 0, 1, 1, 4.
a simple graph with six vertices of degrees 1, 2, 3, 4, 5, 6.
a simple graph with five vertices of degrees 1, 2, 2, 2, 3.
a simple graph with three vertices of degrees 0, 1, 2.
How many edges are there in an undirected graph having 3 vertices each of degree 3 and 5 vertices each of degree 5?
34
17
8
16
25
How many edges are there in an undirected graph with 7 vertices each of degree 4?
7
12
14
28
20
An element a of a poset (S, ≤) is called maximal if
there is no b ∈ S such that b < a
b ≤ a for all b ∈ S
a ≤ b for all b ∈ S
there is no b ∈ S such that a < b
a is not a greatest element of (S, ≤).
Which of the following sets is the equivalence class of 3 for congruence modulo 5?
{…, –8, –3, 3, 9, 15, …}
{…, –5, –1, 3, 7, 11, …}
{…, –10, –5, 0, 5, 10, …}
{…, –8, –3, 2, 7, 12, …}
{…, –7, –2, 3, 8, 13, …}
Which of the following relations on the set of all people is an equivalence relation?
{(a, b) | a and b share a common grandmother}
{(a, b) | a and b speak a common language}
{(a, b) | a and b don’t understand each other}
{(a, b) | a and b have a common friend}
{(a, b) | a and b like the same films}
Find two incomparable elements in the poset (P({a, b}), ⊆).
∅ and {a, b}
∅ and {a}
{a} and {a, b}
{a} and {b}
{b} and {a, b}
Find the least element of the poset ({5, 10, 25, 55, 70, 110}, |).
there is no least element
5
110
25, 70, 110
5, 10
Find the greatest element of the poset ({1, 2, 3, 6, 7, 42, 126}, |).
1
126
there is no greatest element
42, 126
3, 6, 7
Find minimal elements of the poset ({3, 4, 7, 8, 9, 21, 36, 72}, |).
8, 9, 21
3, 4, 7
3
21, 72
3, 7, 8
Find maximal elements of the poset ({2, 4, 6, 7, 8, 14, 20, 21, 42}, |).
42
8, 14, 20
7, 21, 42
8, 20, 42
2, 7
Find the lexicographic ordering of the following 5-tuples: (1, 0, 1, 0, 1), (0, 1, 1, 1, 0), (0, 1, 0, 1, 0), (0, 1, 0, 0, 1), (1, 1, 0, 0, 0).
(0, 1, 0, 1, 0), (0, 1, 0, 0, 1), (0, 1, 1, 1, 0), (1, 1, 0, 0, 0), (1, 0, 1, 0, 1).
(1, 1, 0, 0, 0), (1, 0, 1, 0, 1), (0, 1, 0, 1, 0), (0, 1, 1, 1, 0), (0, 1, 0, 0, 1).
(0, 1, 0, 0, 1), (0, 1, 0, 1, 0), (0, 1, 1, 1, 0), (1, 0, 1, 0, 1), (1, 1, 0, 0, 0).
(1, 0, 1, 0, 1), (0, 1, 1, 1, 0), (0, 1, 0, 1, 0), (0, 1, 0, 0, 1), (1, 1, 0, 0, 0).
(0, 1, 0, 1, 0), (0, 1, 0, 0, 1), (1, 1, 0, 0, 0), (0, 1, 1, 1, 0), (1, 0, 1, 0, 1).
Find the least element of the poset ({2, 3, 4, 6, 18, 36}, |)
2
36
2, 3
4, 6, 18
there is no least element
Find the greatest element of the poset ({2, 4, 5, 6, 10, 24, 50}, |).
50
2
there is no greatest element
4, 6, 10
24, 50
Let S = {1, 2, 3, 4, 5, 6, 7, 8}. Which of the following collections of sets forms a partition of S?
{1, 2, 3, 4}, {5, 6, 7}, {7, 8}
{1, 4, 8}, {3, 5, 7}, {2, 6}
{1, 2} {3, 4, 5}, {4, 6, 7, 8}
{1, 2, 3}, {2, 4, 6}, {5, 7, 8}
{1, 2, 3, 7}, {3, 4, 5, 6, 8}
Which of the following sets is the equivalence class of 1 for congruence modulo 3?
{…, –6, –3, 0, 3, 6, …}
{…, –4, –1, 2, 5, 8, …}
{…, –7, –4, –1, 1, 4, 7, …}
{…, –5, –2, 1, 4, 7, …}
{…, –9, –5, 1, 5, 9, …}
Find the lexicographic ordering of the following strings of lowercase English letters: computer, computing, comma, competent, computable.
computer, computable, computing, comma, competent
comma, computable, computer, computing, competent
comma, competent, computable, computer, computing
computer, competent, comma, computing, computable
computable, computer, computing, competent, comma
Find minimal elements of the poset ({2, 3, 5, 6, 9, 30, 45}, |)
30, 45
2, 3, 5
2, 3
5, 6
2
Find maximal elements of the poset ({1, 2, 3, 5, 6, 15, 30, 45}, |).
15, 30, 45
30, 45
45
1
2, 3, 5
Let S = {0, 1, 2, 3}. With respect to the lexicographic order based on the usual “less than” relation find all pairs in S S less than (1, 3).
(0, 0), (1, 1), (1, 2), (2, 0), (2, 1), (0, 1), (0, 2), (0, 3)
(2, 0), (2, 1), (2, 2), (3, 0), (1, 0), (1, 1), (1, 2), (0, 0), (0, 3)
(1, 0), (1, 1), (1, 2)
(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2)
(0, 0), (1, 1), (2, 2), (3, 3)
Find two incomparable elements in the poset (P({0, 1}), ⊆).
∅ and {0, 1}
∅ and {1}
{0} and {0, 1}
{1} and {0, 1}
{0} and {1}
Which of the following are posets?
(Z^+,>)
(Z, >)
(Z, ≥)
(Z, ≠)
(Z, <)
Which of the following relations on {0, 1, 2, 3, 4} is an equivalence relation?
{(0, 0), (0, 1), (1, 0), (2, 2), (2, 4), (3, 3), (4, 2)}
{(1, 2), (2, 3), (1, 3), (3, 4), (1, 4), (4, 4)}
{(0, 0), (1, 1), (1, 3), (2, 2), (3, 2), (3, 3), (3, 4), (4, 4)}
{(0, 0), (0, 3), (1, 1), (2, 2), (2, 4), (3, 0), (3, 3), (4, 2), (4, 4)}
{(0, 0), (0, 1), (1, 2), (0, 2), (2, 1), (3, 4), (4, 1), (3, 1)}
List the ordered pairs in the relation on {1, 2, 3, 4} corresponding to the matrix .... (where the rows and columns correspond to the integers listed in increasing order).
{(1, 2), (1, 3), (1, 4), (2, 2), (3, 1), (3, 3), (4, 1)}
{(0, 2), (0, 3), (1, 0), (1, 2), (2, 0), (2, 2), (3, 0)}
{(1, 3), (1, 4), (2, 1), (2, 2), (3, 1), (3, 3), (4, 1)}
{(0, 1), (0, 2), (0, 3), (1, 1), (2, 0), (2, 2), (3, 0)}
{(0, 0), (1, 1), (1, 2), (2, 1), (2, 2), (2, 4), (3, 1), (3, 2), (4, 2)}
Represent the relation R= {(0, 1), (0, 3), (1, 2), (1, 3), (2, 0), (2, 1), (2, 3), (3, 2), (3, 3)} on {0, 1, 2, 3} with a matrix (with the elements of this set listed in increasing order).
Let R1 = {(a, b) | a = b + 1} and R2 = {(a, b) | a + b ≤ 3} be relations on {0, 1, 2, 3}. Find R1 - R2.
{(3, 2)}
{(1, 0), (2, 1)}
{(0, 0), (0, 2), (1, 2), (2, 0), (3, 0)}
{(1, 1), (2, 0)}
{(2, 1)}
Let R = {(1, 2), (2, 3), (3, 4), (4, 1), (4, 2)}. Find R^3 .
{(1, 4), (2, 3), (3, 3), (4, 3)}
{(1, 4), (2, 1), (2, 2), (3, 2), (3, 3), (4, 3), (4, 4)}
{(1, 3), (2, 4), (3, 1), (3, 2), (4, 2), (4, 3)}
{(1, 2), (2, 3), (3, 4), (4, 1), (4, 2)}
{(1, 1), (2, 2), (3, 3), (4, 4)}
Let R = {(a, b) | a ≤ b} be a relation on the set of integers. The relation R is
reflexive, symmetric and transitive
antisymmetric and symmetric
reflexive, antisymmetric and transitive
non-reflexive and non-transitive
non-antisymmetric and non-symmetric
Let R = {(1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (3, 2), (4, 4)} be a relation on {1, 2, 3, 4}. The relation R is
Symmetric
Reflexive
antisymmetric
transitive
reflexive and transitive
Let R = {(1, 1), (2, 1), (2, 3), (3, 1), (4, 2), (4, 3)}. Find R^2.
{(1, 1), (2, 1), (2, 3), (3, 1), (4, 2), (4, 3)}
{(1, 1), (2, 1), (3, 1), (4, 1), (4, 3)}
{(1, 1), (2, 1), (3, 1), (4, 1)}
{(2, 1), (4, 1), (3, 1), (2, 3)}
{(1, 1), (1, 2), (1, 3), (2, 4), (3, 2), (3, 4)}
A relation S on a set B is called antisymmetric if
(b, c) ∈ whenever (c, b) ∈ S for all b, c ∈ B
(b, b) ∈ S for every element b ∈ B
both (a, b) and (b, a) belong to S only if a = b for all a, b ∈ B
whenever (b, c) ∈ S and (c, a) ∈ S then (b, a) ∈ S for all a, b, c ∈ B
it is not symmetric
A relation S on a set B is reflexive if
(b, c) ∈ S whenever (c, b) ∈ S for all b, c ∈ B
it is not antisymmetric
whenever (b, c) ∈ S and (c, a) ∈ S then (b, a) ∈ S for all a, b, c ∈ B
it is both symmetric and antisymmetric
(b, b) ∈ S for every element b ∈ B
List the triples in the relation {(a, b, c) | a, b and c are positive integers with 1 < a + b < c ≤ 4}
{(0, 2, 3), (0, 2, 4), (2, 0, 3), (2, 0 , 4), (1, 1, 3), (1, 1, 4), (0, 3, 4), (3, 0, 4)}
{(1, 2, 4), (0, 1, 3), (0, 2, 4), (0, 3, 4)}
{(0, 1, 2), (0,1, 3), (0, 1, 4), (0, 2, 3), (0, 2, 4), (1, 0, 2), (1, 0, 3), (1, 0, 4), (2, 0, 3), (2, 0, 4)}
{(1, 1, 3), (1, 1, 4), (1, 2, 4), (2, 1, 4)}
{(1, 2, 1), (0, 1, 3), (1, 1, 2), (2, 1, 1), (1, 0, 3), (3, 0, 1)}
List the ordered pairs in the relation on {1, 2, 3} corresponding to the matrix ..... (where the rows and columns correspond to the integers listed in increasing order).
{(1, 2), (1, 3), (2, 1), (2, 3), (3, 2), (3, 3)}
{(1, 2), (2, 1), (3, 3)}
{(1, 1), (1, 3), (2, 2), (2, 3), (3, 1), (3, 2)}
{(1, 1), (2, 2), (3, 1), (3, 2), (1, 2), (1, 3)}
{(1, 1), (1, 3), (3, 1), (3, 3)}
Represent the relation R = {(1, 1), (1, 2), (2, 1), (2, 3), (3, 2)} on {1, 2, 3} with a matrix (with the elements of this set listed in increasing order).
Let R = {(a, b), (b, c), (c, a), (d, b)} and S = {(a, a), (b, b), (c, c), (d, a)} be relations on A = {a, b, c, d}. Find S * R
{(a, a), (b, b), (c, c), (d, a)}
{(a, a), (b, a), (c, a), (c, b), (d, b), (d, c)}
{(a, a), (a, b), (b, b), (b, c), (c, a), (c, c), (d, a), (d, b)}
{(a, b), (b, c), (c, a), (d, b)}
{(b, a), (c, b), (a, c), (b, d), (a, d)}
Let R1 = {(1, 1), (1, 2), (2, 2), (2, 3), (3, 3), (3, 4)} and R2 = {(1, 2), (2, 1), (2, 4), (3, 1), (3, 2), (3, 4)} be relations from {1, 2, 3} to {1, 2, 3, 4}. Find R1⋂R2
{(1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4)}
{(1, 2), (3, 4)}
{(1, 1), (2, 2), (2, 3), (3, 3)}
{(1, 1), (2, 1), (2, 4), (3, 1), (3, 2)}
{(1, 1), (1, 2), (2, 2), (3, 3), (3, 4)}
. List the ordered pairs in the relation R from A = {0, 1, 2, 3, 4} to B = {0, 1, 2, 3} where (a, b) ∈ R if and only if a + b = 3.
{(0, 3), (1, 2), (2, 1), (3, 0), (4, –1)}
{(0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3)}
{(0, 3), (1, 2), (2, 1), (3, 0)}
{(0, 0), (1, 1), (2, 2), (3, 3)}
{(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3), (3, 4)}
Find C(8, 4).
1680
35
140
70
840
Find P(8, 5).
336
56
6720
28
72
How many different strings can be made from the letters in ORONO, using all the letters?
10
120
6
12
20
How many ways are there to choose eight coins from a piggy bank containing 100 identical pennies and 80 identical nickels?
P(100, 80)
36
100!/80!*8!
9
C(100, 8) + C(80, 8)
A croissant shop has plain croissants, cherry croissants, chocolate croissants, almond croissants, apple croissants and broccoli croissants. How many ways are there to choose a dozen croissants?
12376
924
6188
210
3003
