Discrete Math DEPT Flashcards
(151 cards)
1
Q
According to the text, logic is primarily the science of:
a) Mathematical calculations
b) Correct reasoning
c) Philosophical debate
d) Computer hardware
A
Correct reasoning
2
Q
What is the main goal in the course, as stated in the introduction to logic?
a) To write complex computer programs
b) To solve algebraic equations
c) To translate languages to symbols
d) To memorize historical facts
A
To solve algebraic equations
3
Q
A declarative statement that is either true or false, but not both, is called a:
a) Question
b) Command
c) Proposition
d) Variable
A
Proposition
4
Q
Which of the following is a proposition according to the text’s examples?
a) Run!
b) Enjoy the lovely weather.
c) 3 + 4 = 9
d) Louis bought me two tickets of “Mission Impossible 5”.
A
3 + 4 = 9
5
Q
Why is “Run!” NOT a proposition?
a) It is too short.
b) It expresses an emotion.
c) It is a command and cannot be true or false.
d) It depends on who is speaking.
A
It is a command and cannot be true or false.
6
Q
What is the term for combining propositions using logical connectives?
a) Simple propositions
b) Compound propositions
c) Declarative statements
d) Truth values
A
Compound propositions
7
Q
The symbol “˄” represents which logical connective?
a) Disjunction
b) Negation
c) Conjunction
d) Conditional
A
Conjunction
8
Q
The symbol “∨” represents which logical connective?
a) Disjunction
b) Negation
c) Conjunction
d) Biconditional
A
Disjunction
9
Q
The symbol “~” (or “¬”) typically represents:
a) Conjunction
b) Negation
c) Implication
d) Equivalence
A
Negation
10
Q
If ‘p’ is a proposition, “~p” is its:
a) Converse
b) Inverse
c) Negation
d) Contrapositive
A
Negation
11
Q
The number of rows required in a truth table depends on the number of propositions and can be computed using the formula:
a) n + 2
b) n^2
c) 2n
d) 2^n
A
2^n
12
Q
In a conditional proposition “if p then q” (p ⟶ q), ‘p’ is called the:
a) Conclusion
b) Consequent
c) Hypothesis
d) Connective
A
Hypothesis
13
Q
In a conditional proposition “if p then q” (p ⟶ q), ‘q’ is called the:
a) Hypothesis
b) Antecedent
c) Premise
d) Conclusion
A
Conclusion
14
Q
Given a conditional statement “if p then q”, what is its converse?
a) if not p then not q
b) if not q then not p
c) if q then p
d) p if and only if q
A
if q then p
15
Q
Given a conditional statement “if p then q”, what is its inverse?
a) if not p then not q
b) if not q then not p
c) if q then p
d) p and q
A
if not p then not q
16
Q
Given a conditional statement “if p then q”, what is its contrapositive?
a) if not p then not q
b) if not q then not p
c) if q then p
d) p or q
A
if not q then not p
17
Q
The compound proposition “p if and only if q” is called a:
a) Conditional proposition
b) Biconditional proposition
c) Conjunction
d) Disjunction
A
Biconditional proposition
18
Q
The symbol “⟷” represents which type of proposition?
a) Conditional
b) Negation
c) Biconditional
d) Disjunction
A
Biconditional
19
Q
An alternative way to state “p if and only if q” is:
a) p is necessary for q
b) p is sufficient for q
c) p is a necessary and sufficient condition for q
d) if p then q, and if not p then not q
A
p is a necessary and sufficient condition for q
20
Q
A compound statement that is true for all possible combinations of the truth values of its propositional variables is a:
a) Contradiction
b) Contingency
c) Tautology
d) Proposition
A
Tautology
21
Q
A compound statement that is false for all possible combinations of the truth values of its propositional variables is a:
a) Contradiction
b) Contingency
c) Tautology
d) Hypothesis
A
Contradiction
22
Q
A compound statement that can either be true or false, depending on the truth values of the propositional variables, is a:
a) Contradiction
b) Contingency
c) Tautology
d) Conclusion
A
Contingency
23
Q
Logic gates are constructed using figures that correspond to:
a) Mathematical theorems
b) Compound propositions and connectives
c) Historical events in logic
d) Computer programming languages
A
Compound propositions and connectives
24
Q
A syntactical transform rule used to infer a conclusion from a premise to create an argument is a:
a) Truth table
b) Logical connective
c) Rule of inference
d) Propositional variable
A
Rule of inference
25
A sequence of statements that end with a conclusion is defined as a(n):
a) Proposition
b) Argument
c) Tautology
d) Predicate
Argument
26
The rule of inference "p ∴ p ∨ q" is known as:
a) Simplification
b) Addition
c) Modus Ponens
d) Hypothetical Syllogism
Addition
27
The rule of inference "p ∧ q / ∴ p" is known as:
a) Addition
b) Simplification
c) Modus Tollens
d) Disjunctive Syllogism
Simplification
28
Two compound propositions p & q are logically equivalent if:
a) p → q is a tautology
b) p ∧ q is a tautology
c) p ↔ q is a tautology
d) p ∨ q is a contradiction
p ↔ q is a tautology
29
The notation "p ≡ q" denotes that:
a) p implies q
b) p and q are contradictory
c) p and q are logically equivalent
d) p is a subset of q
p and q are logically equivalent
30
Statements that are neither true nor false when the values of the variables are not specified are called:
a) Propositions
b) Tautologies
c) Predicates
d) Arguments
Predicates
31
The term that describes the extent to which a predicate is true over a range of elements is:
a) Domain
b) Quantifier
c) Variable
d) Connective
Quantifier
32
The symbol "∀" is called the:
a) Existential quantifier
b) Universal quantifier
c) Predicate symbol
d) Logical connective
Universal quantifier
33
The universal quantification ∀xP(x) is read as:
a) There exists an x such that P(x)
b) For some x, P(x)
c) For all x P(x) or for every x P(x)
d) If P(x) then x
For all x P(x) or for every x P(x)
34
An element for which P(x) is false in a universal quantification ∀xP(x) is called a:
a) Proof
b) Counterexample
c) Premise
d) Conclusion
Counterexample
35
The symbol "∃" is called the:
a) Existential quantifier
b) Universal quantifier
c) Negation symbol
d) Implication symbol
Existential quantifier
36
The existential quantification ∃xP(x) is read as:
a) For all x, P(x)
b) If P(x) then for all x
c) There exists an x such that P(x)
d) P(x) is always true
There exists an x such that P(x)
37
What is the primary use of nested quantifiers mentioned in the text?
a) To simplify truth tables
b) To construct logic gates
c) To transform English sentences into logical statements
d) To define basic propositions
To transform English sentences into logical statements
38
A valid argument that establishes the truth of a mathematical statement or a theorem is a:
a) Conjecture
b) Axiom
c) Proof
d) Predicate
Proof
39
A statement that can be shown to be true is a:
a) Theorem
b) Axiom
c) Conjecture
d) Lemma
Theorem
40
Statements we assume to be true in a proof are called:
a) Corollaries
b) Lemmas
c) Theorems
d) Axioms (or postulates)
Axioms (or postulates)
41
A less important theorem that is helpful in the proof of other results is called a:
a) Conjecture
b) Corollary
c) Lemma
d) Axiom
Lemma
42
A theorem that can be established directly from a theorem that has been proved is a:
a) Lemma
b) Axiom
c) Conjecture
d) Corollary
Conjecture
43
A statement that is being proposed to be a true statement is a:
a) Theorem
b) Proof
c) Conjecture
d) Axiom
Conjecture
44
In a direct proof of p → q, one assumes 'p' is true and uses axioms, definitions, etc., to show:
a) 'p' must be false
b) 'q' must be false
c) 'q' must also be true
d) '~q' must be true
'q' must also be true
45
Proof by contraposition makes use of the fact that p → q is equivalent to:
a) q → p
b) ~p → ~q
c) ~q → ~p
d) p ↔ q
~q → ~p
46
What is the basic idea behind a proof by contradiction?
a) Assume the statement is true and show it leads to a known truth.
b) Assume the statement is false and show this assumption leads to a contradiction (nonsense).
c) Prove the contrapositive of the statement.
d) Break the statement into smaller, directly provable parts.
Assume the statement is false and show this assumption leads to a contradiction (nonsense).
47
Mathematical induction is a way of proving math statements for:
a) Only rational numbers
b) Only real numbers
c) All integers (or a subset like positive integers)
d) Only complex numbers
All integers (or a subset like positive integers)
48
The first step in a proof by mathematical induction for a statement P(n) is usually to:
a) Assume P(k) is true
b) Prove P(1) (or the base case) is true
c) Show P(k) → P(k+1)
d) Define the variables
Prove P(1) (or the base case) is true
49
In mathematical induction, after proving the base case, what is the next step?
a) Prove P(k+1) directly
b) Assume P(k) is true for some k
c) Look for a contradiction
d) State the conclusion
Assume P(k) is true for some k
50
Who introduced the concept of sets, defining a set as a collection of definite and distinguishable objects?
a) Leonhard Euler
b) Aristotle
c) G. Cantor
d) Euclid
G. Cantor
51
A set is defined as a:
a) Sequence of numbers
b) Well-defined collection of distinct objects
c) Logical argument
d) Mathematical proof
Well-defined collection of distinct objects
52
The symbol "∈" means:
a) Is a subset of
b) Is an element of
c) Is not an element of
d) Is equal to
Is an element of
53
Describing a set by listing its elements separated by commas and enclosed by braces is called the:
a) Set builder form
b) Rule form
c) Tabular or roster form
d) Axiomatic form
Tabular or roster form
54
Describing a set using a description like {x | …..} is called the:
a) Tabular form
b) Roster form
c) Enumeration form
d) Set builder or rule form
Set builder or rule form
55
The set of natural numbers (positive whole numbers) is typically represented by the symbol:
a) Z
b) Q
c) R
d) N (or sometimes ℕ)
N (or sometimes ℕ)
56
Sets whose elements are countable are called:
a) Infinite sets
b) Finite sets
c) Universal sets
d) Empty sets
Finite sets
57
Two sets are equal if:
a) They have the same number of elements.
b) They have precisely the same members.
c) They are both subsets of the same universal set.
d) They are described using the same method.
They have precisely the same members.
58
Two sets are equivalent if:
a) They have precisely the same members.
b) They have the same number of elements.
c) One is a subset of the other.
d) Their intersection is empty.
They have the same number of elements.
59
If A is a subset of B, it is written as:
a) A ∈ B
b) A ⊂ B
c) A ⊆ B
d) A = B
A ⊆ B
60
A is a proper subset of B (A ⊂ B) if every element in A is also in B, and:
a) B has fewer elements than A
b) A and B are identical
c) There exists at least one element in B that is not in A
d) A has at least one element not in B
There exists at least one element in B that is not in A
61
A set with no elements is called the:
a) Universal set
b) Infinite set
c) Empty (or Null) set
d) Singleton set
Empty (or Null) set
62
The empty set is represented by the symbol:
a) {0}
b) U
c) ∅ or {}
d) N
∅ or {}
63
The "order" of a set refers to its:
a) Arrangement of elements
b) Smallest element
c) Size (number of elements)
d) Type (finite or infinite)
Size (number of elements)
64
The union of two sets A and B (A∪B) is the set containing:
a) Only elements common to both A and B
b) All elements from A that are not in B
c) All elements from B that are not in A
d) All elements from both A and B
All elements from both A and B
65
The intersection of two sets A and B (A∩B) is the set containing:
a) Elements which are in both A and B
b) All elements from A or B or both
c) Elements in A but not in B
d) Elements not in A and not in B
Elements which are in both A and B
66
The difference of two sets A and B (A - B) is the set of:
a) Values in both A and B
b) Values in A but not in B
c) Values in B but not in A
d) Values not in A and not in B
Values in A but not in B
67
Venn diagrams are primarily used to:
a) Prove set identities algebraically
b) Visually represent sets and their relationships
c) Calculate the number of elements in a set
d) Define new types of sets
Visually represent sets and their relationships
67
The complement of a set S (Sc) is the set of:
a) All values in S
b) All values not in S (relative to a universal set)
c) The empty set if S is not empty
d) The universal set if S is empty
All values not in S (relative to a universal set)
68
A (binary) relation R from set X to a set Y is a subset of:
a) X ∪ Y
b) X ∩ Y
c) The Cartesian product X × Y
d) The power set of X
The Cartesian product X × Y
69
If (x,y) ∈ R, we write xRy and say that:
a) x is equivalent to y
b) x is greater than y
c) x is related to y
d) x is a function of y
x is related to y
70
The set {x ∈ X | (x,y) ∈ R for some y ∈ Y} is called the ______ of relation R.
a) Range
b) Codomain
c) Domain
d) Image
Domain
71
The set {y ∈ Y | (x,y) ∈ R for some x ∈ X} is called the ______ of relation R.
a) Domain
b) Codomain
c) Preimage
d) Range
Range
72
A relation R on a set X is called reflexive if:
a) (x,y) ∈ R implies (y,x) ∈ R for all x,y ∈ X
b) (x,x) ∈ R for every x ∈ X
c) (x,y) ∈ R and (y,z) ∈ R implies (x,z) ∈ R for all x,y,z ∈ X
d) (x,y) ∈ R and (y,x) ∈ R implies x = y for all x,y ∈ X
(x,x) ∈ R for every x ∈ X
73
A relation R on a set X is called symmetric if:
a) (x,x) ∈ R for every x ∈ X
b) If (x,y) ∈ R then (y,x) ∈ R, for all x,y ∈ X
c) If (x,y) ∈ R and (y,x) ∈ R then x = y, for all x,y ∈ X
d) If (x,y) ∈ R and (y,z) ∈ R then (x,z) ∈ R, for all x,y,z ∈ X
If (x,y) ∈ R then (y,x) ∈ R, for all x,y ∈ X
74
A relation R on a set X is called antisymmetric if for all x,y ∈ X:
a) If (x,y) ∈ R then (y,x) ∉ R
b) If (x,y) ∈ R and (y,x) ∈ R then x = y (the text states x ≠ y which is usually for strict antisymmetry, but often means x=y if both exist)
c) (x,y) ∈ R implies (y,x) ∈ R
d) (x,x) ∉ R
If (x,y) ∈ R and (y,x) ∈ R then x = y (the text states x ≠ y which is usually for strict antisymmetry, but often means x=y if both exist)
75
A partial order is a relation R on a set X that is reflexive, transitive, and:
a) Symmetric
b) Antisymmetric (as defined by: if (x,y) and (y,x) ∈ R then x = y - this is standard)
c) Universal
d) Empty
Antisymmetric (as defined by: if (x,y) and (y,x) ∈ R then x = y - this is standard)
76
A relation R on a set X is called transitive if for all x,y,z ∈ X:
a) (x,y) ∈ R implies (y,x) ∈ R
b) (x,x) ∈ R
c) If (x,y) ∈ R and (y,z) ∈ R then (x,z) ∈ R
d) If (x,y) ∈ R and (y,x) ∈ R then x = y
If (x,y) ∈ R and (y,z) ∈ R then (x,z) ∈ R
77
A relation that is reflexive, symmetric, and transitive on a set X is called:
a) A partial order
b) An equivalence relation
c) A function
d) A strict order
An equivalence relation
78
For a relation f from X to Y to be a function, the domain of f must equal X and:
a) For every y ∈ Y, there must be an x ∈ X such that (x,y) ∈ f
b) If (x,y) and (x,y') are in f, then y = y'
c) If (x,y) and (x',y) are in f, then x = x'
d) The relation must be symmetric
If (x,y) and (x,y') are in f, then y = y'
79
A function f from X to Y is one-to-one (or injective) if:
a) For each x ∈ X, there is exactly one y ∈ Y with f(x) = y
b) For each y ∈ Y, there is at most one x ∈ X with f(x) = y
c) The range of f is Y
d) The domain of f is X
For each y ∈ Y, there is at most one x ∈ X with f(x) = y
80
If f is a function from X to Y and the range of f is Y, f is said to be:
a) One-to-one (injective)
b) Onto Y (surjective)
c) A bijection
d) Reflexive
Onto Y (surjective)
81
A function that is both one-to-one and onto is called a:
a) Partial function
b) Surjection
c) Injection
d) Bijection
Bijection
82
Number theory is a branch of mathematics that primarily studies the set of:
a) Real numbers
b) Complex numbers
c) Rational numbers
d) Positive whole numbers (natural numbers)
Positive whole numbers (natural numbers)
83
According to the Division Algorithm, if 'a' and 'b' are integers with b ≠ 0, then there exist unique integers q and r such that a = bq + r and:
a) 0 < r ≤ |b|
b) 0 ≤ r < |b|
c) r = 0
d) r < 0
0 ≤ r < |b|
84
In the Division Algorithm (a = bq + r), 'q' is called the:
a) Divisor
b) Remainder
c) Quotient
d) Dividend
Quotient
85
In the Division Algorithm (a = bq + r), 'r' is called the:
a) Quotient
b) Factor
c) Divisor
d) Remainder
Remainder
86
If a and b are integers with a ≠ 0, and ac = b for some integer c, we say that:
a) b divides a (b|a)
b) a divides b (a|b)
c) a is a multiple of c
d) c is a divisor of a
a divides b (a|b)
87
If a|b, which of the following is NOT necessarily true according to the properties of divisibility?
a) a|bx for any integer x
b) If a|c, then a|(b+c)
c) a = b
d) If b|c, then a|c
a = b
88
If a|b and b|a, then (assuming a, b are integers):
a) a = b
b) a = -b
c) |a| = |b|
d) a > b
|a| = |b|
89
An integer 'd' is called a common divisor of 'a' and 'b' if:
a) d divides a+b
b) d divides a or d divides b
c) d divides a and d divides b
d) d divides ab
d divides a and d divides b
90
The largest common divisor of integers 'a' and 'b' (not both 0) is denoted by:
a) lcm(a,b)
b) gcd(a,b)
c) div(a,b)
d) mod(a,b)
gcd(a,b)
91
The Euclidean Algorithm is primarily used to find:
a) The least common multiple of two integers
b) The prime factorization of an integer
c) The greatest common divisor of two integers
d) Solutions to linear congruences
The greatest common divisor of two integers
92
A writing system for expressing numbers using digits or other symbols in a consistent manner is a:
a) Number theory
b) Numeral system (or system of numeration)
c) Division algorithm
d) Congruence relation
Numeral system (or system of numeration)
93
The decimal system is base:
a) 2
b) 8
c) 10
d) 16
10
94
The binary system uses which digits?
a) 0, 1, 2
b) 0, 1
c) 0 through 7
d) 0 through 9, A through F
0, 1
95
The octal system is base:
a) 2
b) 8
c) 10
d) 16
8
96
The hexadecimal system is base 16 and uses digits 0-9 and letters:
a) A, B, C, D, E, F
b) X, Y, Z, H, E, X
c) L, M, N, O, P, Q
d) Alpha, Beta, Gamma, Delta, Epsilon, Zeta
A, B, C, D, E, F
97
Two integers 'a' and 'b' are congruent modulo n (a ≡ b (mod n)) if and only if:
a) a and b have the same quotient when divided by n
b) a - b = n
c) a and b have the same remainder when divided by n
d) a + b is divisible by n
a and b have the same remainder when divided by n
98
An alternative definition for a ≡ b (mod n) is:
a) a - b = n + k for some integer k
b) n divides (a - b)
c) a = nb + k for some integer k
d) b = na + k for some integer k
n divides (a - b)
99
The property "a ≡ a (mod n)" for congruences is known as the:
a) Symmetric property
b) Transitive property
c) Equivalence property
d) Reflexive property
Reflexive property
100
If a ≡ b (mod n), then b ≡ a (mod n). This is the ______ property of congruence.
a) Reflexive
b) Symmetric
c) Transitive
d) Commutative
Symmetric
101
If a ≡ b (mod n) and b ≡ c (mod n), then a ≡ c (mod n). This is the ______ property of congruence.
a) Reflexive
b) Symmetric
c) Transitive
d) Associative
Transitive
102
The Principle of Counting states that if a choice consists of two steps, the first made in n1 ways and the second in n2 ways, the whole choice can be made in:
a) n1 + n2 ways
b) n1 * n2 ways
c) n1 / n2 ways
d) n2 / n1 ways
n1 * n2 ways
103
An arrangement of a group of things in a definite order is called a:
a) Combination
b) Permutation
c) Set
d) Sample
Permutation
104
In which of the following is the order of elements important?
a) Combination
b) Set
c) Permutation
d) Subset
Permutation
105
The number of permutations of n distinct objects taken n at a time is:
a) n
b) n^2
c) n!
d) 2n
n!
106
The number of permutations of n distinct objects taken r at a time is given by the formula:
a) n! / r!
b) n! / (n-r)!
c) n! / (r!(n-r)!)
d) (n-r)! / n!
n! / (n-r)!
107
Permutations that occur by arranging objects in a circle are called:
a) Linear permutations
b) Circular permutations
c) Distinct permutations
d) Repetitive permutations
Circular permutations
108
The number of ways to arrange n distinct objects in a circle is typically:
a) n!
b) (n-1)!
c) n
d) n! / 2
(n-1)!
109
An arrangement of objects without regard to the order is called a:
a) Permutation
b) Sequence
c) Combination
d) Array
Combination
110
The number of combinations of selecting r objects from n distinct objects is given by C(n,r) where C(n,r) = :
a) n! / (n-r)!
b) n! / r!
c) n! / (r!(n-r)!)
d) (n-r)!r! / n!
n! / (r!(n-r)!)
111
The "Seven Bridges of Konigsberg" problem led to the development of which branch of mathematics?
a) Calculus
b) Number Theory
c) Set Theory
d) Graph Theory
Graph Theory
112
Who is credited with explaining the impossibility of the Seven Bridges of Konigsberg problem, leading to graph theory?
a) G. Cantor
b) Carl Ehler
c) Leonhard Euler
d) Euclid
Leonhard Euler
113
In graph theory, a graph G is formally defined as an ordered pair (V,E) where V is the vertex set and E is the:
a) Vector set
b) Edge set
c) Element set
d) Eulerian set
Edge set
114
The elements of V in a graph G=(V,E) are called:
a) Edges or links
b) Vertices or nodes
c) Paths or circuits
d) Degrees or orders
Vertices or nodes
115
The order of a graph G is the number of its:
a) Edges
b) Vertices
c) Loops
d) Paths
Vertices
116
The size of a graph G is the number of its:
a) Vertices
b) Components
c) Cycles
d) Edges
Edges
117
An edge in a graph G which is a singleton (connects a vertex to itself) is called a:
a) Parallel edge
b) Bridge
c) Loop
d) Path
Loop
118
If a graph G has two edges with the same pair of vertices, these are called:
a) Loops
b) Parallel edges
c) Adjacent edges
d) Incident edges
Parallel edges
119
A graph that may have loops or parallel edges is a:
a) Simple graph
b) Multigraph
c) Pseudograph
d) Complete graph
Multigraph
120
A graph that may have parallel edges but should not have loops is a:
a) Simple graph
b) Multigraph
c) Pseudograph
d) Tree
Multigraph
121
A graph which neither has loops nor parallel edges is a:
a) Simple graph
b) Multigraph
c) Pseudograph
d) Connected graph
Simple graph
122
Two vertices v1, v2 are said to be adjacent if:
a) They have the same degree
b) There is an edge e ∈ E(G) such that e = {v1,v2}
c) They belong to the same component
d) They are both incident to a loop
There is an edge e ∈ E(G) such that e = {v1,v2}
c) They belong to the same component
123
If an edge e connects vertices u and v, then u and v are ______ to e.
a) Adjacent
b) Parallel
c) Incident
d) Equivalent
Incident
124
Two edges are said to be adjacent edges if they:
a) Are parallel
b) Have the same length
c) Have common endpoints
d) Are part of the same cycle
Have common endpoints
125
The neighborhood of a vertex v, N(v), is the set of all vertices in G which are:
a) Incident to v
b) At distance 2 from v
c) Adjacent to v
d) Connected to v by a bridge
Adjacent to v
126
The degree of a vertex v, deg(v), is the number of non-loop edges incident to v plus:
a) The number of loops incident to v
b) Twice the number of loops incident to v
c) Half the number of loops incident to v
d) Zero, as loops don't count for degree
Twice the number of loops incident to v
127
Δ(G) represents the ______ degree in graph G.
a) Minimum
b) Maximum
c) Average
d) Median
Maximum
128
δ(G) represents the ______ degree in graph G.
a) Minimum
b) Maximum
c) Total
d) Specific
Minimum
129
If all vertices of G have degree k, G is called a:
a) Complete graph
b) Simple graph
c) k-regular graph
d) Connected graph
k-regular graph
130
A graph in which all vertices are pairwise adjacent is a:
a) Path graph
b) Cycle graph
c) Regular graph
d) Complete graph (Kn)
Complete graph (Kn)
131
An alternating sequence of incident vertices and edges (v1, e1, v2, e2, ..., en, vn) is a:
a) Path
b) Trail
c) Walk
d) Cycle
Walk
132
The length of a walk is the number of ______ in the sequence.
a) Vertices
b) Edges
c) Distinct vertices
d) Distinct edges
Edges
133
A walk with no repeating edges is a:
a) Path
b) Trail
c) Cycle
d) Circuit
Trail
134
A closed trail (a trail where initial and terminal vertices are the same) is called a:
a) Path
b) Cycle
c) Tour
d) Walk
Tour
135
A walk with no repeating vertices is a:
a) Trail
b) Path
c) Tour
d) Closed walk
Path
136
A closed path (a path where initial and terminal vertices are the same, apart from start/end) is called a:
a) Trail
b) Tour
c) Cycle
d) Walk
Cycle
137
The girth of a graph G, ω(G), is the length of the:
a) Longest cycle
b) Shortest cycle
c) Longest path
d) Shortest path between any two vertices
Shortest cycle
138
The circumference of a graph G, Ω(G), is the length of the:
a) Longest cycle
b) Shortest cycle
c) Acyclic path
d) Spanning tree
Longest cycle
139
The shortest path between two vertices u and v in a graph G is the ______ between u and v, denoted d(u,v).
a) Connection
b) Eccentricity
c) Distance
d) Diameter
Distance
140
For a connected graph G, the eccentricity of a vertex v, ε(v), is the:
a) Shortest distance from v to any other vertex
b) Largest distance from v to any other vertex
c) Degree of v
d) Number of cycles passing through v
Largest distance from v to any other vertex
141
The diameter of a graph G, D(G), is the:
a) Smallest eccentricity in G
b) Largest eccentricity in G
c) Average eccentricity in G
d) Number of vertices in G
Largest eccentricity in G
142
The radius of a graph G, r(G), is the:
a) Smallest eccentricity in G
b) Largest eccentricity in G
c) Diameter divided by 2
d) Most central vertex
Smallest eccentricity in G
143
The set of vertices {v | ε(v) = D(G)} in a graph G are called the:
a) Centers of G
b) Peripheries of G
c) Core of G
d) Boundary of G
Peripheries of G
144
The set of vertices {v | ε(v) = r(G)} in a graph G are called the:
a) Centers of G
b) Peripheries of G
c) Outliers of G
d) Medians of G
Centers of G
145
A graph with no cycle is called:
a) Connected
b) Complete
c) Acyclic
d) Regular
Acyclic
146
A connected acyclic graph is called a:
a) Forest
b) Path
c) Cycle
d) Tree
Tree
147
A collection of disconnected trees is called a:
a) Grove
b) Forest
c) Bush
d) Graphle
Forest
148
Which of the following is a property of a tree with n vertices?
a) It has n edges.
b) Its size is n-1.
c) It must contain at least one cycle.
d) Multiple paths exist between any pair of vertices.
Multiple paths exist
149
An edge 'e' of a graph G is a bridge if:
a) e is part of every cycle in G
b) G - {e} is disconnected
c) e has the highest weight in G
d) e connects two components of G
G - {e} is disconnected
150
According to Theorem 2 in section 6.3, every connected graph has a spanning subgraph which is a:
a) Cycle
b) Complete graph
c) Tree
d) Forest
Tree
