The modules introduce mathematical tools required in the study of computer science. Topics include:
1.Logic and proof techniques
2.Number theory
3.Sequences and Mathematical Induction
4.Set theory, Functions and Relations
5.Counting and Probability
6.Graphs and Trees
It is the backbone of...
National University of Singapore
Department of Computer Science
2019/20 (Sem. 2) CS1231/CS1231S Discrete Structures Tutorial 10
1 Let G3 be the set of all undirected graphs whose vertices are a, b, c. Suppose G = ({a, b, c}, E) ∈ G3 .
Determine the number of possible G’s such that:
(i) G has a loop; (ii) G has a cycle;
(iii) G is cyclic; (iv) G is connected;
(v) G is a tree; (vi) G has exactly two connected components.
Solution:
Consider (labelled) undirected graphs with 3 nodes.
Each node may or may not have a loop (23 possibilities),
and each node pair may or may not have an edge (2(2) possibilities).
3
Total = 23 (23 ) = 26 = 64.
(i) #graphs with no loops = 13 2(2) = 8
3
⇒ #graphs with loops = 64 − 8 = 56.
(ii) #graphs with a cycle (choice only in loops) = 23 = 8.
(iii) #(∼loop∧ ∼cycle)= 2(2) − 1 = 7.
3
#cyclic = #(loop∨cycle) = 64 − 7 = 57.
(iv) #connected⇔ ∧, <, > or △ and any choice of loops: 4(23 ) = 32 possibilites
(v) tree ⇔ ∧, <, or > and no loops: 3 possibilities
(vi) G has exactly 2 components ⇔ 1 edge only and any choice of loops:
3 3
1
2 = 24 possibilities.
1
, x
2 The diagram here illustrates an undirected graph K, called a 3-sided wheel:
(i) Let K = (VK , EK ). List the elements of EK . u
(ii) How many different 3-sided wheels are there with VK = {u, x, y, z}?
y z
(iii) Determine the number of different 3-sided wheels with VK ⊆ {1, 2, 3, 4, 5, 6}
3-sided wheel K
(e.g. u = 4, x = 6, y = 2, z = 3)?
with vertices u, x, y, z
w x u x
The diagram here shows two
u w
4-sided wheels H and H ′ :
y z y z
(iv) Explain why H 6= H ′ .
4-sided wheel H 4-sided wheel H’
(v) Determine the number of different 4-sided wheels H with vertex set VH = {1, 2, 3, 4, 5}.
(vi) Determine the number of different 4-sided wheels H with vertex set VH ⊆ {1, 2, 3, 4, 5, 6, 7}.
Solution:
(ii) Just 1, since EK already has all possible edges
(iii) There are 64 = 15 choices for VK ; each choice gives one 3-sided wheel.
Therefore, there are 15 possibilites.
(iv) H 6= H ′ since u in H has 4 edges, but u in H ′ has 3 edges.
(v) With u at the center, there are just 3 possible wheels,
determined by who is not connected to x by one edge.
There are 5 possible choices for the center,
so there are 5 × 3 = 15 possible 4-sided wheels (Multiplication Rule)
(vi) There are 75 = 21 choices for VH ; each choice gives 15 4-sided wheels.
Therefore there are 21 × 15 = 315 possible 4-sided wheels for VH ⊆ {1, 2, 3, 4, 5, 6, 7}.
2
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller chrisbarn. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $7.91. You're not tied to anything after your purchase.
