Discrete Mathematics (Ch 8, Graph Theory)
SKKU Math Lectures and Labs
Prof : Sang-Gu LEE (http://matrix.skku.ac.kr/sglee/ )
http://matrix.skku.ac.kr/2018-DM/DM-Labs.htm Discrete Math Labs (실습실)
http://matrix.skku.ac.kr/2018-album/2018-Lectures-sglee.htm (강의실)
http://matrix.skku.ac.kr/2018-DM-QnA/ (질문과 답변)
http://matrix.skku.ac.kr/2018-DM-Sol/2018-DM-Sol.htm (문제풀이)
http://matrix.skku.ac.kr/2018-DM-PBL/ (PBL report 보고서)
http://matrix.skku.ac.kr/2018-DM-PBL-Eng/ (PBL report Eng, 영문
보고서)
Ch 8, Graph Theory
Lecture Note http://matrix.skku.ac.kr/2018-DM/Ch-8/
DM-Ch-8-Lab http://matrix.skku.ac.kr/2018-DM/DM-Ch-8-Lab.html
Ch-8-Lab 2 http://matrix.skku.ac.kr/2014-Models/Graph-Project.html
http://discretetext.oscarlevin.com/dmoi/sec_gt-intro.html
(DM Sec 8.1 동영상강의) Graph Theory https://youtu.be/TSFIJBU2dX8
(DM Sec 8.2 동영상강의) Path and Cycle https://youtu.be/iqUTT5C1TOs
(DM Sec 8.3 동영상강의) Hamiltonian cycle https://youtu.be/at7Hx5wxnYk
(DM Sec 8.4 동영상강의) Shortest Path https://youtu.be/MHDJ3rALtEU
* Name of Your Class Mate: Chingis Oinar
*Note: this part is more of a general response rather than picking a specific person as above mentioned.
Fill in the below for your self-assessment and your project/term paper.
(A) Briefly describe your contributions through Q&A for yourself and fellow students in our "DM" classes!
(A1) Quantity : **
(A2) What you contributed through this course (Q & A and/or In-class)?
My contribution as an individual was two-way contribution. In one way I learnt from others and I have been in part of different discussions throughout this course. The other way I have contributed is that I have put a lot of effort in helping others by revising and finalizing their solutions. Moreover, I tried my best to post as many general questions as possible regarding the course or assignments to make sure that not only me, but the others can benefit from my questions.
(A3) No. of Final OK by SGLee Problems (and/or Completed Discussion/Question) in QnA that your name is included.
Final Ok Problems Number: 72 Problems (from chapter 1,2,3,4,5,6,7,8,9)
Discussions that the Professor made a comment on/wrote a Final ok on: +15 posts.
(B)Quality of Your Participation:
(B1) What did you especially remember while you are doing A-1, 2, 3.
The most interesting thing that popped up in my head is how awkward I felt in the very beginning to post anything. However, thanks to the Professor and my classmates who always pushed me and appreciated the good work which made me feel way more comfortable day by day.
(B2) What did you learn or feel while learning DM (Action Learning/PBL) with your classmates?
I am really happy to be part of this fabulous lecture where learning isn’t just about math and getting a good grade, but it has a broader meaning of sharing with others and participating in discussions to hold an effective place in the class and to be a productive individual.
(B3) Write names of YOUR PBL Team members and Team Leader.
(B4) What is your project (and In-depth study) and your role in your Team (Leader, Idea, Solve, Prove, Coding, Typing, Presentation etc.
As for our team work that is divided in two parts:
A) QnA activity: In this part each we had to manage Chapter 8 (Graph Theory), where we took a different approach by embedding some discussion portals for the students to talk about. Moreover, we provided the students a chance to solve more exciting and core problem by removing the redundant ones.
B)
Actual Team Project: in this part Me and Mr.Kim Jung Ju
participated in doing an in depth research for the shortest path problem under
the name of “ Analysis of Shortest Path Algorithms from a Computer Science’s
Perspective” where we discussed different approaches taken to solve such
problem while keeping the time complexity into consideration.
(The QnA activity and The Team Project are attached at the end of this PBL
Report)
As far as for my role I have been the leader who tried his best to organize and push the team specially the less active members by reminding them that how DM could affect them in a useful way. Moreover, I have been the concept founder and solver who provides the solutions for student’s questions plus finds new ideas and ways of making Chapter 8 way more joyful. Finally, I’ll be the main presenter and spokesperson for my Team.
◆ Number of your QnA participation up to the Due date. ( 192 total entries )
Part 1: Your meaningful questions in QnA which you had you got the Final answer.
· Note: The questions I have done are pretty general (yet still am attaching some of them – One question per one page)
Question Title: “Reply/Question on Homework” Date 13/09/2018
Question text:
“Good Job
:D , the professor didn't actually declare any rules for uploading the homework
answers(yet) but I think you better insert pictures ( in the text itself)
rather than an attachment, it'll be easier for everyone to follow up with you,
rather than switching back and forth between downloaded files and icampus
website.
by the way I have a question, The professor
didn't mention any specific section, are you sure we have to solve just from
1.1?”
Professor Reply: Date
13/09/2018
“I see^^ I will check the page number of problem clear.
But if you solve and shared a couple of problems and Solution.
That will do it for you^^”
Question by TA and follow up question by me (Muhammad)
Original text by the TA: Date 13/09/2018
“방정식 P(x) = 0 이 실근을 갖지 않는다.
를 지금까지 배운 논리기호로 표시해 보세요 ( 실수 집합은 R로 표기합니다. )
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
The equation P (x) = 0 does not have a real root. (the real set is written as R).
Represent this proposition using logical symbol you have learned so far.
There is no x in real such that P (x) = 0.”
Solved by Muhammad: Date 16/09/2018
“There is no x in real
such that P (x) = 0
given that P(x) means not having a real root
we can say
∀ x in R , not P(x)=0
which means for all x in Real they can have a real root
“
Revised by SGLee: Date 17/09/2018
“There is no x in real such that P (x) = 0
<=> ∃! x ∈ R ∋ P(x)=0
“
Follow up Question by Muhammad: Date 17/09/2018
“Isn't
it the same thing ? but the other way round
there is no x such that p(x)
all of x can't justify p(x)
I guess both are logically equivalent, do i have to stick with the exact same words?”
Final Answer by SGLee: Date 17/09/2018
“Yes, you have to stick with the exact same words in symbol:
∃! x ∈ R ∋ P(x)=0
( for There is no x in real such that P (x) = 0 )
because it is the most clear statement to all (not only for you).”
Question Title: “Request for Chapter 2 notes-PDF” Date 23/09/2018
Question text:
“Hello there,
Can anyone tell me where can I find the PDF version
of lecture notes for chapter2?
* if it's not uploaded it would be a great help
if you can upload it Sir/TA.
Best Regards”
Professor Reply: Date 26/09/2018
“Hello, Dear Muhammed!
.. PDF file of the Chapter 2 (Proofs) ...
I can give the file to you when you are ready. And I will give it to you when you are ready.
NOW if you want, (as I said in the class) you can read copy and do work the second chapter on the link: http://matrix.skku.ac.kr/2018-DM/DM-Ch-2-Lab.html .
Professor uploaded all the materials of the second chapter on this link.
Happy Chuseok! “
Question Title: “About PBL Report(inquiry)” Date 27/09/2018
Question text:
“Hello there,
Does anyone have any information about
submitting the PBL report? I mean When ? hardcopy or softcopy?what should we
include in it?
* I checked the related post on notice board.
Alas, I didn't get much info.”
* I
understood everything, but the part of "final ok" i didn't, How can I
get the final ok if there are some questions which i solved/reviised/finalized
without a final ok? Shall I tell you next class or remind you?
Thanks Sir
“
Professor
Reply: Date 29/09/2018
“
For the part of "final ok"
. We still have more than 10 days before we submit your pbl report.
So I will grade and You or your friend or the one you degignate or your team member can see me or TA to get final ok by sglee or TA ... Once a week or before you submit.
You can get help from me in my OH or just after the next class.”
Part 2: Problems with your name in [Solve-Revise-Finalize and Final OK by SGLee/TA]
p.64, Problem 15 (Chapter1 Self-Test)
Solved by 전종문, 2018.09.14
Revised by Muhammad/모하메드, 2018.09.17
Finalized by 전종문, 2018.09.20
Refinalized by Muhammad/모하메드. 2018.10.05
[Offline] In person meeting-Final Ok By Professor, 2018.10.05
Problem:
Determine whether the following argument is valid.
p →q ∨ r
p ∨¬q
r ∨ q
-----------------
∴ q
Solution
By using Truth Table.
Case |
p |
q |
r |
-q |
q ∨ r |
p →q ∨ r
|
p ∨¬q
|
r ∨ q
|
q |
1 |
T |
T |
T |
F |
T |
T |
T |
T |
T |
2 |
T |
T |
F |
F |
T |
T |
T |
T |
T |
3 |
T |
F |
T |
T |
T |
T |
T |
T |
F |
4 |
T |
F |
F |
T |
F |
F |
T |
F |
F |
5 |
F |
T |
T |
F |
T |
T |
F |
T |
T |
6 |
F |
T |
F |
F |
T |
T |
F |
T |
T |
7 |
F |
F |
T |
T |
T |
T |
T |
T |
F |
8 |
F |
F |
F |
T |
F |
T |
T |
F |
F |
For the conclusion to be true we have to consider the cases when all premises are true (cases marked in yellow), these cases are: 1 , 2 , 3 , 7.
Then we try to find a counter example -if any- in the conclusion for these cases. We can see that counter examples can be found in case 3 and case 7 where q is false.
Therefore, this argument is invalid.
Question by TA
Solved by Muhammad Date 16/09/2018
Revised by SGLee and Final OK Date 17/09/2018
“방정식 P(x) = 0 이 실근을 갖지 않는다.
를 지금까지 배운 논리기호로 표시해 보세요 ( 실수 집합은 R로 표기합니다. )
The equation P (x) = 0 does not have a real root. (the real set is written as R).
Represent this proposition using logical symbol you have learned so far.
There is no x in real such that P (x) = 0.”
Solution:
“There is no x in real such that P (x) = 0
<=> ∃! x ∈ R ∋ P(x)=0
“
p.64, Problem 14 (Chapter 1 Self-Test)
Solved by 김희성 Sep . 16th Revised by 조영은 Sep, 21th
Finalized by 모하메드 Sep,26th Re-Finalized by 모하메드 Oct,05th
[Offline] In person meeting-Final Ok By Professor, 2018.10.05
----------------------------------------------------------------------------------------
Problem 14:
Write the following argument symbolically and determine whether it is valid.
If the Skyscrapers win, I'll eat my hat.
If I eat my hat, I'll be quite full.
Therefore, if I'm quite full, the Skyscrapers won.
Solution:
First, let’s give each statement(proposition) a symbol as following:
The Skyscrapers win ---> proposition p
Eat my hat ---> proposition q
quite full ---> proposition r
Secondly, changing the given argument into symbols we get:
p->q (If the Skyscrapers win, I'll eat my hat)
q->r (If I eat my hat, I'll be quite full)
ㅡㅡㅡ
r->p (Therefore, if I'm quite full, the Skyscrapers won)
Finally, we check the validity:
For the argument to be valid, the conclusion and the premises should be true (no matter what the inputs are) but assuming that p is false, q is false and r is true we can get:
p->q (Is true)
q->r (Is true)
ㅡㅡㅡ
r->p (but the conclusion is false)
Since the conclusion is False while the premises are true (counter example), we can say that the argument is invalid.
Note: This Invalidity is called the fallacy of affirming the conclusion
p.63, Problem 5 (Chapter 1 Self-Test)
Solved by 정호진 2018.09.17
Revised By : Muhammad/모하메, Finalized By : Muhammad/모하메드26/Sep/2018
Re-Finalized By : Muhammad/모하메드05/Oct/2018
[Offline] In person meeting-Final Ok By Professor, 2018.10.05
Problem 5:
If p, q and r are true, find the truth value of the proposition (p∨q) ∧ ㄱ((ㄱp∧ r) ∨q))
Solution:
p∨q - true; ㄱp∧ r - false;
(ㄱp∧ r) ∨q) - true; ㄱ((ㄱp∧ r) ∨q)) - false;
(p∨q) ∧ ㄱ((ㄱp∧ r) ∨q)) - false
-------------------------------------------------------------------
Truth Table:
p |
q |
r |
-p |
p∨q |
¬p ∧ r |
(¬p ∧ r ) ∨ q |
¬ ((¬p ∧ r ) ∨ q) |
( p ∨ q) ∧¬((¬p ∧ r ) ∨ q).
|
T |
T |
T |
F |
T |
F |
T |
F |
F |
p.64, Problem 8 (Chapter1 Self-Test)
Solved by 정호진 2018.09.17 Revised by SGLee 2018.09.17
Finalized by Muhammad /모하메드 2018.9.26
Re-Finalized By : Muhammed/모하메드05/Oct/2018
[Offline] In person meeting-Final Ok By Professor, 2018.10.05
Problem 8
Assume that a, b, and c are real numbers. Represent the statement
a<b or (b<c and a ≥ c)
symbolically, letting
p: a<b, q: b<c, r: a<c.
--------------------------------------------------------------
Solution:
p∨(q∧ㄱr) ■
Page : 63 Problem 1 - Chapter 1
Solved By : Muhammed/모하메드, Date: 2018.09.17
Finalized By: 전종문, Date: 2018.09.20
Final OK by SGLee
Problem 1
1. If A = {1, 3, 4, 5, 6, 7}, B = {x | x is an even integer},
C = {2, 3, 4, 5, 6}, find (A ∩ B) − C.
Solution
A = {1, 3, 4, 5, 6, 7}
B = {x | x is an even integer}={2,4,6,8,10,...}
C = {2, 3, 4, 5, 6}
A ∩ B= {4,6}
Since, (A ∩ B) ⊆ C
(A ∩ B) − C = { } ■ (empty set)
Page 64 Problem 12 Chapter 1
Solved by 전솔람 Date 2018.09.19
Revised and Finalized by Muhammad/모하메드 Date 2018.09.26
Final OK by TA Date 2018.10.04
12. Represent the statement
If ( a ≥ c or b < c ), then ( b ≥ c )
symbolically using the definitions of Exercise 8.( p : a < b, q : b < c, r : a < c )
Sol)
a ≥ c is equivalent to the reverse of r ( a < c ), so a ≥ c represents ¬ r
And, b < c is equivalent to q ( b < c )
And, b ≥ c is same to the reverse of q ( b < c ), so b ≥ c represents ¬ q
As a result, " ( a ≥ c or b < c ), then ( b ≥ c ) " can be represented as " ( ¬ r ∨ q ) → ¬ q
Page 64 Problem 17-Ch. 1 Solved by 전솔람 19th Sep.
Revised and Finalized by Muhammad/모하메드 26th Sep.
Final OK by SGLee,
17. Is the statement
" The team won the 2006 National Basketball Association championship "
a proposition? Explain.
Sol)
Answer No!
It is not proposition.
Because the statement cannot be determined to True or False.
Why? Because we don't know what "team" the statement is referring to. □
Problem 13 p.124(Chapter2 Self-Test)
Solved by 전종문, Date : 2018.09.21
Revised by 유가이 올렉산드르: 2018.09.23
Finalized by Muhammad/모하메드:2018.09.26
ReFinalized and Final OK by SGLee 2018.09.27
Problem
Use mathematical induction to prove that the statements in Exercises 13-16 are true for every positive integer n.
13. 2 + 4 + … + 2n = n(n+1) (*)
-----------------------------------------------------------------------
Proof
Ⅰ. Basis Step: (*) is true for n=1
2=1(1+1)=2 is true.
Ⅱ. Inductive Step:
Assume (*) is true for n=k :
[that is: If n=k, then 2 + 4 + … + 2k = k(k+1) --- (*) is true.]
* We want to [show that it's true for n=k+1]
Add 2(k+1) at the left hand side of (*)
2 + 4 + … + 2k + 2(k+1)
= k(k+1) + 2(k+1) (because of (*) 2 + 4 + … + 2k = k(k+1) )
= (k+1)(k+2) (because k(k+1) +2(k+1) is equal to(k+1)(k+2) )
So, 2 + 4 + … + 2k + 2(k+1)=(k+1)(k+2) is true.
By Principle of Mathematical Induction.
2 + 4 + … + 2n = n(n+1) is true for every positive integer n.■
p.124, Problem №1 Chapter 2
Solved by 유가이 올렉산드르, 2018.09.23
Finalized by Muhammad/모하메드 2018.09.26
Final OK by SGLee
Problem №1
Distinguish between the terms axiom and definition.
Solution
By definition axioms (postulate) is a statement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments. (증명 없이 참으로 받아들이는 명제)(in simple words: things that are assumed to be true)
In my opinion, the distinctive feature of the axioms is that, it is the mainstay of mathematics, which don't require proof (Because they can't be proved, they simply exist, as a universe).
Definitons are used to create new concepts in terms of existing ones. Some terms are not explicitly defined, but rather are implicitly defined by the axioms. (뜻 : 수학용어나 기호에 대하여 그 의미를 규정한 것.) ■
*** In math, 공리와 정의, 정리의 차이
2) 공리
뜻 : 증명 없이 참으로 받아들이는 명제
예시 :
1. 임의의 점에서 임의의 점으로 직선을 그을 수 있다.
2. 유한인 직선(좀 애매함 선분이라고 생각하시는게좋음)은 연장할 수 있다.
3. 임의의 중심과 거리를 가지고 원을 가지고 원을 그릴 수 있다.
4. 모든 직각은 서로 같다.
5. 직선 밖의 한 점을 지나 이 직선에 평행하는 직선은 오직 하나뿐이다.
위와 같은 유클리드기하의 5대 공리가 예시이다.
1) 정의
뜻 : 수학용어나 기호에 대하여 그 의미를 규정한 것.
예시 : 직각삼각형 : 한 내각의 크기가 직각인 삼각형을 직각삼각형이라 한다.
정삼각형 : 세 변의 길이가 같은 삼각형을 정삼각형이라 한다.
3) 정리
수학적으로 증명된 참인 명제
예시 :피타고라스의 정리 ( )
Page : 124 Problem 10 Chapter2
Solved By : Muhammad/모하메드: 2018.09.24
Finalized by 유가이 올렉산드르: 2018.09.26
Re-Finalized By : Muhammad/모하메드05/Oct/2018
[Offline] In person meeting-Final Ok By Professor, 2018.10.05
Question 10 : Find an expression, which is the "and of clauses", equivalent to ( p ∨¬q) → ¬r s.
Discussion/Explanation:
Our Goal is to change the expression so that it becomes "and-clause",
* and-clause is a clause/statement of the form as following:
e.g. a^b^c^d^e
e.g.2. (!a∨b)^(c)^(d∨!e)
*Remember that in DM or Logic Design we can omit the “and” Symbol.
e.g. a^b is equivalent to ab
* Preparation Before Solving:
Refer to the resolution proof (Chapter 2 Section 3) and equivalent statements mentioned throughout the section.
*
Extra Info:
this question is essential in Digital Logic Design where we have to minimize a
Boolean expression to (and-clause) (also named maxterm).
* Solution:
*Note: rs = r^s
( p ∨¬q) → ¬rs ≡ ¬( p ∨¬q) ∨¬rs (by using equivalent statements/Resolution Proof)
≡ ¬pq ∨ ¬rs (using De Morgan’s Law )
≡ (¬pq∨ ¬r ) ^(¬pq∨ s) (Using equation 3.4 in chapter 2)
Page : 124 Problem 20 Chapter 2
Solved By : Muhammad/모하메드 25/sep/2018
Finalized by : 강병훈 27/sep/2018
Final OK by SGLee
20. Use the Well-Ordering Property to show that any nonempty set X of nonnegative integers that has an upper bound contains a largest element.
Hint: Consider the set of integer upper bounds for X.
----------------------------------------------------------------------------
Discussion/ Explanation:
We have to show that there exists an element in X (let’s call it x) which creates an upper bound for the set. In other words, the element x is greater than or equal to each element in the set X.
For example, 13934 is a lower bound for the set X= {5, 8, 42, 34, 13934}.
As far for the hint given, we can consider an arbitrary set that contains all values greater or equal to X.
For example, the set Y = {13934,13935,13936,...} is the set of integer upper bounds for X= {5, 8, 42, 34, 13934}.
----------------------------------------------------------------------------
Solution:
From the given question; we want to show that if there exists a nonempty set X of nonnegative integers that has an upper bound, then it contains a largest element.
Using the hint given, let’s assume there exists a set Y which is the set of integers upper bound for the set X. By this assumption, we can deduce that Y is a non-empty set of nonnegative integers following the properties of the Set X. Using the Well Ordering Property, the set Y has a least element (let’s call it y). By the previous deductions, we can say that y≧x for every x in the set X.
Now to ensure that the element y is
in the set X ,
we can assume that y is not in X then there
should be an element (y-1) ∈ Y which
is greater or equal to each element in X , but there isn’t
since y is the lowest element in the set Y that
makes an upper bound for X (contradiction).
Hence, y≧x for
every x ∈ X and y is
the largest element in X.
An example would further clarify: X= {3} , Y={3,4,5}.
Page 198 Problem 20 Chapter 3
Solved by 오동찬 : 2018.09.27
Finalized by Muhammad/모하메드 2018.09.28
Re-Finalized by 오동찬 2018.09.29
Final OK by SGLee
Exercises 17-20 refer to the relations
R₁= {(1,x), (2,x), (2,y), (3,y)},
R₂= {(x,a), (x,b), (y,a), (y,c)}.
Problem 20
Use the result of Exercise 19 to find the matrix of the relation R₂° R₁.
+) Result of Exercise 19
Solution
Problem 21 p.198(Chapter3 Self-Test)
Solved by Muhammad/모하드:2018.09.28
Finalized by 오동찬, Date: 2018.09.30
Re-Finalized By : Muhammed/모하메드:05/Oct/2018
[Offline] In person meeting-Final Ok By Professor, 2018.10.05
In Exercises 21–24, write a sequence of operations to answer
the query. Also, provide an answer to the query. Use Tables 3.6.1
and 3.6.2.
21. Find all teams.
Discussion/Explanation:
Table 3.6.1:(Player Table)
ID Number |
Name |
Position |
Age |
22012 |
Johnsonbaugh |
c |
22 |
93831 |
Glover |
of |
24 |
58199 |
Battey |
p |
18 |
84341 |
Cage |
c |
30 |
01180 |
Homer |
1b |
37 |
26710 |
Score |
p |
22 |
61049 |
Johnsonbaugh |
of |
30 |
39826 |
Singleton |
2b |
31 |
Table 3.6.2: (Assignment Table)
PID |
Team |
39826 |
Blue Sox |
26710 |
Mutts |
58199 |
Jackalopes |
01180 |
Mutts |
*These tables represent data base (collection of data)
*A query is a request for information from the database (Example: Find all the players with age of 22 years)
*To Solve/Answer a query we have to select certain data from the database using some operators:
-Selection Operator -> Row Selection
-Projection Operator -> Column Selection
-Join Operator -> merging all info for some related entries(in two tables)
*Key word "TEMP" is used to state an intermediate state (temporary)
Solution:
Operation :ASSIGNMENT [Team]
∴ Blue Sox, Mutts and Jackalopes ■
Note:
These Tables are a very simple example where we use basic operations(mentioned earlier) to extract some specific data of our choice , it can be extended to any complexity of your desire
Problem 22 p.198(Chapter3 Self-Test)
Solved by Muhammad/모하드:2018.09.28
Finalized by 오동찬, Date: 2018.09.30
Re-Finalized By : Muhammed/모하메드:05/Oct/2018
[Offline] In person meeting-Final Ok By Professor, 2018.10.05
In Exercises 21–24, write a sequence of operations to answer
the query. Also, provide an answer to the query. Use Tables 3.6.1
and 3.6.2.
22. Find all players’ names and ages.
Discussion/Explanation:
Table 3.6.1:(Player Table)
ID Number |
Name |
Position |
Age |
22012 |
Johnsonbaugh |
c |
22 |
93831 |
Glover |
of |
24 |
58199 |
Battey |
p |
18 |
84341 |
Cage |
c |
30 |
01180 |
Homer |
1b |
37 |
26710 |
Score |
p |
22 |
61049 |
Johnsonbaugh |
of |
30 |
39826 |
Singleton |
2b |
31 |
Table 3.6.2: (Assignment Table)
PID |
Team |
39826 |
Blue Sox |
26710 |
Mutts |
58199 |
Jackalopes |
01180 |
Mutts |
*These tables represent data base (collection of data)
*A query is a request for information from the database (Example: Find all the players with age of 22 years)
*To Solve/Answer a query we have to select certain data from the database using some operators:
-Selection Operator -> Row Selection
-Projection Operator -> Column Selection
-Join Operator -> merging all info for some related entries(in two tables)
*Key
word "TEMP" is used to state an intermediate state (temporary)
Solution:
Operation: PLAYER [Name, Age]
∴ Johnsonbaugh, 22;
Glover, 24;
Battey, 18;
Cage,30;
Homer, 37;
Score, 22;
Johnsonbaugh, 30;
Singleton, 31 ■
Note:
These Tables are a very simple example where we use basic operations(mentioned earlier) to extract some specific data of our choice , it can be extended to any complexity of your desire
Problem 23 p.198(Chapter3 Self-Test)
Solved by Muhammad/모하드 Date:2018.09.28
Finalized by 전종문 Date: 2018.09.28
Re-Finalized By : Muhammed/모하메드:05/Oct/2018
[Offline] In person meeting-Final Ok By Professor, 2018.10.05
Problem
In Exercises 21–24, write a sequence of operations to answer
the query. Also, provide an answer to the query. Use Tables 3.6.1 and 3.6.2.
23. Find the names of all teams that have a pitcher.
Discussion/Explanation:
Table 3.6.1:(Player Table)
ID Number |
Name |
Position |
Age |
22012 |
Johnsonbaugh |
c |
22 |
93831 |
Glover |
of |
24 |
58199 |
Battey |
p |
18 |
84341 |
Cage |
c |
30 |
01180 |
Homer |
1b |
37 |
26710 |
Score |
p |
22 |
61049 |
Johnsonbaugh |
of |
30 |
39826 |
Singleton |
2b |
31 |
Table 3.6.2:(Assignment Table)
PID |
Team |
39826 |
Blue Sox |
26710 |
Mutts |
58199 |
Jackalopes |
01180 |
Mutts |
*These tables represent data base (collection of data)
*A query is a request for information from the database (Example: Find all the players with age of 22 years)
*To Solve/Answer a query we have to select certain data from the database using some operators:
-Selection Operator -> Row Selection
-Projection Operator -> Column Selection
-Join Operator -> merging all info for some related entries(in two tables)
*Key
word "TEMP" is used to state an intermediate state (temporary)
Solution
Sequence of Operation:
TEMP1 := PLAYER [Position = p] ⇒players who are pitchers
TEMP2 := TEMP1 [ID Number = PID] ASSIGNMENT ⇒ pitchers and playing in teams
TEMP2 [Team] ⇒ select the name of those teams having a picther
∴ Mutts, Jackalopes ■
Note:
These Tables are a very simple example where we use basic operations(mentioned earlier) to extract some specific data of our choice , it can be extended to any complexity of your desire
Problem 24 p.198(Chapter3 Self-Test)
Solved by Muhammad/모하메드:2018.09.28
Finalized by 오동찬, Date: 2018.09.30
Re-Finalized By : Muhammed/모하메드:05/Oct/2018
[Offline] In person meeting-Final Ok By Professor, 2018.10.05
In Exercises 21–24, write a sequence of operations to answer
the query. Also, provide an answer to the query. Use Tables 3.6.1 and 3.6.2.
24. Find the names of all teams that have players aged 30 years or older.
Discussion/Explanation:
Table 3.6.1:(Player Table)
ID Number |
Name |
Position |
Age |
22012 |
Johnsonbaugh |
c |
22 |
93831 |
Glover |
of |
24 |
58199 |
Battey |
p |
18 |
84341 |
Cage |
c |
30 |
01180 |
Homer |
1b |
37 |
26710 |
Score |
p |
22 |
61049 |
Johnsonbaugh |
of |
30 |
39826 |
Singleton |
2b |
31 |
Table 3.6.2:(Assignment Table)
PID |
Team |
39826 |
Blue Sox |
26710 |
Mutts |
58199 |
Jackalopes |
01180 |
Mutts |
*These tables represent data base (collection of data)
*A query is a request for information from the database (Example: Find all the players with age of 22 years)
*To Solve/Answer a query we have to select certain data from the database using some operators:
-Selection Operator -> Row Selection
-Projection Operator -> Column Selection
-Join Operator -> merging all info for some related entries(in two tables)
*Key
word "TEMP" is used to state an intermediate state (temporary)
Solution:
Sequence of Operations:
TEMP1 := PLAYER [Age ≥ 30] ->Players older than 30
TEMP2 := TEMP1 [ID Number = PID] ASSIGNMENT -> older than 30 and in teams
TEMP2 [Team] -> name of teams having players older than 30
Thus,
The teams Blue Sox and Mutts have players which ages are equal or older than 30. ■
Note:
These Tables are a very simple example where we use basic operations(mentioned earlier) to extract some specific data of our choice , it can be extended to any complexity of your desire
Page 247 Problem 5 (Chapter 4 Self Test)
Solved by Muhammad/모하메드 : 2018.10.03
Finilized by 칭기즈 : 2018.10.03
Final OK by SGLee,
----------------------------------------------------------------------------
5.Trace Algorithm 4.2.1 for the input t = “111011” and
p = “110”.
*Explanation:
* The Algorithm stated in section 4.2.1 is called Text Search and it is defined as following:
- Text Search:
This algorithm searches for an occurrence of the pattern p in text t . It returns the smallest
index i such that p occurs in t starting at index i. If p does not occur in t, it returns 0.
Input: p (indexed from 1 to m), m, t (indexed from 1 to n), n
Output: i (the index of first match occurrence)
Pseudo Code:
text search( p, m, t, n) {
for (i = 1 to n − m + 1) //the starting point is 1, the ending point is (n-m+1)
{
j = 1
// i is the index in t of the first character of the substring
// to compare with p, and j is the index in p
// the while loop compares ti · · · ti+m−1 and p1 · · · pm
while (ti+j−1 == pj )
{
j = j + 1
if ( j > m) //reaching the end of substring p
return i
}
}
return 0
}
"
*Solution:
Given:
t= "111011"
p= "110"
* Following the code and tracing the loop iterations we can find:
1) For-Loop's First Iteration / i=1:
a) j is set to 1
b) we execute the while-loop , and since t[1]==p[1], j is incremented to compare t[2] and p[2] and since t[2]==p[2], j is incremented once again to compare t[3] and p[3] and since t[3]!=p[3] , the while loop is broken and we move to the next for-loop iteration
2) For-Loop's Second Iteration / i=2:
a) j is set to 1
b) we execute the while-loop , and because i=2 we start
with t[2], since t[2]==p[1], j is incremented to compare t[3] and p[2]
and since t[3]==p[2], j is incremented once again to compare t[4] and p[3]
and since t[4]==p[3] j is incremented once again to become (j=4) which is
greater than (m) , so i=2 is returned.
--------------------------------------------------------
t = "111011" n=6
p = "110" m=3
Hint:
if ( j > m) //reaching the end of substring p
return i
The algorithm terminates when j>m, m=3 => j=4
Trace table:
i |
j |
t[i+j-1]==p[j] |
Output |
1 |
1 |
true |
- |
1 |
2 |
true |
- |
1 |
3 |
false |
- |
2 |
1 |
true |
- |
2 |
2 |
true |
- |
2 |
3 |
true |
- |
2 |
4 |
|
2 |
Output:
2
□
p.247 problem 9 Chapter 4
Solved by Muhammad Date: 2018.10.03
finalized by 엄자균 Date: 2018.10.04
Re-Finalized by 서명원 Date: 2018.10.05
Final OK by SGLee
Problem
Select a theta notation from among Θ (1), Θ (n), Θ (n2), Θ (n3),Θ (n4), Θ (2n), or Θ (n!) for each of the expressions in Exercises 9 and 10.
9. 4n3 + 2n − 5
Discussion
f(n)= O (g(n)) if f(n) ≤ C_1 *g(n) for constant 'C_1 ' and n0 ≤ n
f(n)= Ω (g(n)) if f(n) >= C_2 *g(n) for constant 'C_2' and n0 ≤ n
f(n)= θ (g(n)) if f(n) is O(g(n)) and f(n) is Ω (g(n)).
The problem 9 '4n3 + 2n − 5' is θ(n3)
Sol.
Since 10n3 > 4n3 + 2n − 5, c_1 = 10 where C_1 = 10 and 4n3 + 2n − 5
> 1/10 n3 where C_2 = 1/10 (n0=1)
=> '4n3 + 2n − 5' is Θ(n3) □
Page 248 Problem 12 (Chapter 4 Self Test)
Solved by 강병훈 Date: 2018.10.3
Revised and finalized by Muhammad/모하메드 : 2018.10.03
Final Ok SGLEE
----------------------------------------------------------------------------
12. Write an algorithm that tests whether two n × n matrices are equal and find a theta notation for its worst-case time.
*Solution:
Input: A and B (n × n matrices) and n
Output: true (if A =
B ); false (if A ≠ B)
Code:
equal matrices(A, B, n)
{
for i = 1 to n
{
for j = 1 to n
{
if (Ai j != Bi j )
return
false
}
}
return true
}
-----------------------------------------------------------------------
The
worst-case time is theta of (n^2) why? because we have a
nested loop (2-step loop) where for each index in the i-loop the j-loop will be
executed n times, and since i is also executed n times then n*n =n^2 (in worst case O(n^2) and best case Omega(n^2)-> hence Theta(n^2)).
Note by Muhammad: Theta /O / Omega notations are read as " O/theta/Omega of
f(x)" ->
where f(x) is a function that counts the
number of operations executed and generally the most used notation is the Big
O-notation since it gives the upper bound-worst case- for an algorithm.
Since I am
from software department i thought this would be helpful.
Page 263 Problem № 2 (Chapter5 Self-Test)
Solved by AYSU OZGUNEKIM
Revized by 김주형
Finalized by 유가이 올렉산드르
Refinalized by Muhammad/모하메드
Final OK by SGLee
Date: 05.10.2018
07.10.2018
08.10.2018
08.10.2018
Problem № 2 Page 263 (Chapter 5)
Find the prime factorization of 539.
-----------------------------------------------------------------
*Discussion:
Important Terms :
-prime number(N) : natural number that is greater than 1 and that cannot be formed by multiplying two smaller natural numbers(x,y), where x,y are also greater than 1.
-prime factor : A factor that is a prime number (Prime Numbers that can be multiplied to form a composite number)
- prime factorization : the decomposition of a composite number into a product of prime numbers
*Algorithm/Pseudo Code for testing whether an integer(N) is prime:\
Check_Prime(int N) //N is the number to be checked
{
for d=2 to N1/2
if (N mod d == 0) //mod function returns the remainder
return d
return 0
}
*Solution:
Using the algorithm mentioned earlier, we can easily check whether an integer(N) is prime or not, so we combine the same algorithm with division to solve this problem as following.
Let's solve this task by using a factorial tree:
*The yellow marked numbers are prime.
So we get : 539=(7^2)*11
■
Comment: From this problem, I realized that Factors are the numbers you multiply together to get another number.
ex)
5*3 = 15. And Prime Factorization is finding which prime
numbers multiply together to make the original number. ■
Another Comment by Muhammad: when
you try to find Factorial tree , start checking the factors from smallest to
biggest (1,2,3,4,...)
Page 263 Problem № 8 (Chapter5 Self-Test)
Solved by 김희성 2018.10.07
Executed by 김영철 2018.10.08
Revised and Finalized Muhammad/모하메드 2018.10.08
* Problem:
Trace Algorithm 2.19 for the values a = 50, n =30, z =11.
* Discussion:
The algorithm is as following: Algorithm 2.19
(Exponentiation Mod By Repeated Squaring)
This algorithm computes using repeated squaring.
Input: a, n, z
Output:
exp_mod_via_repeated_squaring(a, n, z)
result
while ()
if( )
*
*
return result
* Solution (Step by Step plugging in):
result = 1
x=a mod z = 50 mod 11=6
-----------------------while Loop 1st iteration-------------
while(n>0) //While-loop executes since n=30>0
{
if( ) //If condition doesn't execute since 30 mod 2 !=1
*
x=6*6 mod 11 = 3
n=15
-----------------------while Loop 2nd iteration-------------
while(n>0) //While-loop executes since n=15>0
{
If ( ) //If condition executes since 15 mod 2 ==1
result=1*3 mod 11=3
x=3*3 mod 11 = 9
n=7
-----------------------while Loop 3rd iteration-------------
while(n>0) //While-loop executes since n=7>0
{
If ( ) //If condition executes since 7 mod 2 ==1
result=3*9 mod 11=5
x=9*9 mod 11 = 4
n = 3
-----------------------while Loop 4th iteration-------------
while(n>0) //While-loop executes since n=3>0
{
If ( ) //If condition executes since 3 mod 2 ==1
result = 5*4 mod 11 = 9
x=4*4 mod 11 = 5
n = 1
-----------------------while Loop 5th iteration-------------
while(n>0) //While-loop executes since n=1>0
{
If ( ) //If condition executes since 1 mod 2 ==1
result=9*5 mod 11 = 1
x=5*5 mod 11 = 3
n=0
}
Finally, Since n=0 is not greater
than 0 the loop is broken and we get result = 1.
* Solution Checking :
by simply plugging in the original formula :
(a^n) mod z = (50^30) mod 11 = 1. hence our answer is right.
* Comment by Muhammad:
After Solving this problem I realized how important is it to write a pseudo code before actual programming.
Final OK by SGLee/CH.6 page 370 Problem 1
solved by 김승연, 모하메드, 김주형
Problem 1
How many eight-bit strings begin with 0 and end with 101?
Solution
Let's consider the final layout for the number as following:
0 □ □ □ □ 1 0 1
Step A) The 1st and the 5th-8th bit already have specific values.so there is no selection involved in these fixed bits.
Step B) The number of remaining bits are 4 bits. Moreover, there are two ways to select each bit (either 0 or 1).
Step C) By the Multiplication Principle, the total number of eight-bit encoding is 24 = 16.
Answer
24 = 16. ■
Comment
이 문제는 빈 공간에 중복이 없는 두 가지 선택지가 있는 문제로 이 문제를 풀었다면 선택지가 두 개인 문제뿐만 아니라 간단한 선택 문제는 모두 풀 수 있다.
This problem has two choices with no duplication of blank
If you solve this problem, you can solve not only the two choices but also the simple ones.
Final OK by SGLee/CH.6 page 371 Problem 5
solved by오동찬, 김영철, 모하메드, 엄자균, 강병훈, 김주형
Problem 5
How many 3-combinations are there of six objects?
Solution
C (6 ,3 ) = 6 ! ÷ (3 ! × 3 ! ) = 20
Answer: 20 ■
Note Definition 2.15
Comment
콤비네이션 함수의 기본을 알고 있다면 다른 문제를 푸는데 큰 문제가 없을 것이다.
If you know definition of combination function (definition 2.15), there won't be much trouble solving other related problems.
Final OK by SGLee/CH.6 page 371 Problem 7
solved by 오동찬, 김영철, 모하메드, 엄자균, 강병훈, 정호진
Problem 7
How many
six-card hands chosen from an ordinary 52-card deck
contain three cards of one suit and three cards of another suit?
Solution
1. C (13, 3) = 286 (one suit)
2. C (13, 3) = 286 (another suit)
3. C (4 , 2) = 6 (2 suits)
4. 286 x 286 x 6 = 490,776.
Answer: 490,776 ■
Comment
52장 카드에 13개의 같은 문양이 있다는 것을 생각해서 콤비네이션 함수를 이용하면 쉽게 풀 수 있는 문제이다.
Thinking that there are 13 identical shape on the 52 cards, it is a problem that can be easily solved by using the combination function.
Final OK by SGLee/CH.6 page 371 Problem 8
solved by 오동찬, 김영철, 모하메드, 엄자균, 강병훈, 정호진
Problem 8
A shipment of 100 compact discs contains five defective discs. In how many ways can we select a set of four compact discs that contains more defective than non defective discs?
Solution
1. defective : 3, not defective : 1 C(5,3) × C(95,1).
2. defective : 4 C(5,4)
∴ C(5,3) × C(95,1)+ C(5,4) = 955
Answer: 955 ■
Comment
직접 답을 구하기 어려운 문제는 독립시행이라면 답을 더하거나 빼서 구할 수 있다.
The problem which is hard to finding the direct answer can be obtained by adding or subtracting the answer if it is independent trial.
Final OK by SGLee/CH.6 page 371 Problem 11
solved by 전종문, 김영철, 신혜수, 모하메드, 정호진, 강병훈
Problem 11
In how many ways can 12 distinct books be divided among four students if each student gets three books?
Solution
1st student: C(12,3)
2nd student: C(9,3)
3rd student:C(6,3)
4th student:C(3,3)
Answer
C(12,3) × C(9,3) × C(6,3)× C(3,3) = 12!/(3!)4 ■
Note
Definition 2.15
Given a set containing (distinct) elements,
(a) An -combination of is an unordered selection of -elements of (i.e. an -element subset of ).
(b) The number of -combination of a set of distinct elements is or .
Comment
선택 형 문제에서는 선택한 후에 선택지가 없어진다는 것을 알아두는 것이 중요하다.
It is important to know that, in a selective problem, the choice is lost after it is selected.
Final OK by SGLee/CH.6 page 371 Problem 12
solved by 신혜수, 전종문, 모하메드, 김주형, 강병훈, 정호진
Problem 12
How many integer solutions of
x1 + x2 + x3 + x4 = 17
Satisfy
x1 ≥ 0, x2 ≥ 1, x3 ≥ 2, x4 ≥ 3
Solution
x2 = x2'+ 1, x3 = x3'+ 2, x4 = x4' + 3
x1 + x2+ x3 + x4 = x1 + (x2'+1) + (x3'+2) + (x4'+3) = 17
x1 + x2' + x3' + x4' = 11
Satisfy
x1 ≥ 0, x2' ≥ 0, x3' ≥ 0, x4' ≥ 0
For combination for repetition,
nHr = n+r-1Cr = 11+4-1C4 = 14C4 = 14!/(4!×10!) = (14×13×12×11)/(4×3×2×1)=1001
Answer = 1001 ■
Comment
이 문제는 단순히 생각하면 어렵겠지만 변수를 변경해주어 11번 문제와 똑같이 만들어서 풀 수 있는 문제이다.
This is a problem that can be solved simply by changing the variable and making it the same as Problem 11, even if it is difficult to think.
Final OK SGLee/CH.6 page 371 Problem 16
solved by 김정주, 모하메드, 이양휘, 강병훈
Problem 16
Find the permutation that will be generated by Algorithm 4.14 after 6427135.
Solution
Step1: Algorithm 4.14 generates the permutation that follows 6427135 by supposing that
s1 = 6, s2 = 4, s3 = 2, s4 = 7, s5 = 1, s6 = 3, s7 = 5
Step2: At line 6, the largest index m satisfying sm < sm+1 is 6 (s6 = 3)
Step3: At lines 10–13, we find that the largest index k satisfying sk > sm is 7 (s7 = 5).
Step4: At line 14, swap sm and sk
s6 = 5 and s6 = 3
Step5: Swap 6 and 7 : 6427153
Answer : 6427153
Note
*what is lexicographic order?
it is an order that generalizes ordinary dictionary order.
*Algorithm 4.14 Generating Permutations
This algorithm lists all permutations of {1, 2, . . . , n} in an increasing lexicographic
order.
Input: n
Output: All permutations of {1, 2, . . . , n} in increasing lexicographic order
1. permutation(n) {
2. for i = 1 to n
3. si = i
4. println(s1, . . . , sn) // print the first permutation
5. for i = 2 to n! {
6. m = n − 1
7. while (sm > sm+1)
8. // find the first decrease working from the right
9. m = m − 1
10. k = n
11. while (sm > sk )
12. // find the rightmost element sk with sm < sk
13. k = k − 1
14. swap(sm, sk )
15. p = m + 1
16. q = n
17. while ( p < q) {
18. // swap sm+1 and sn, swap sm+2 and sn−1, and so on
19. swap(sp, sq )
20. p = p + 1
21. q = q − 1
22. }
23. println(s1, . . . , sn) // print the ith permutation
24. }
25. }
Comment:
It may
be a little bit difficult for people who do not know the code, but I think it
is good for me to solve some problems in the future.
[Final OK by TA] Ch. 7 P.424 Problem 1 solved by 전솔람 Finalized by 칭키즈, 김영철 , Muhammad
Solved by 전솔람 date 2018. 11. 06.
Finalized by 칭기즈 Date 2018.11.06
Re-Finalized by 김영철 Date 2018.11.07
Re-Finalized (fixed) by Muhammad Date 2018.11.10
Final OK by TA Date 2018.11.12
Problem
Answer part (a)-(c) for the sequence defined by rules:
1. The first term is 3.
2. The n th term is n plus the previous term.
(a) Write the first four terms of the sequence.
(b) Find an initial condition for the sequence.
(c) Find a recurrence relation for the sequence.
Solution
1. Let n-th term of the sequence be an, which logically makes the previous term an-1.
2. Hence, the formula of n-th term is an = n + an-1
3. Let me remind you that the first term is 3 ( a1=3 )
4. Hence to
find another three elements:
n = 2
-> a2 = 2 + a2-1 = 2 + a1 = 2 + 3
= 5
n = 3
-> a3 = 3 + a3-1 = 3 + a2 = 3 +
5 = 8
n = 4 -> a4 = 4 + a4-1 = 4 + a3 = 4 + 8
= 12
Answer:
(a) The first for terms of the sequence.
a1 = 3, a2 = 5, a3 = 8 , a4 = 12
(b) Initial condition for the sequence.
a1 = 3
(c) A recurrence relation for the sequence.
an = n + an-1 ■
Comment:
Recurrence relations are the same as recursive functions in Programming where we relate some term in a sequence to a previous term. Secondly, a hint for solving this problem can be using some values to plugin and check
Comment:
일정한 규칙의 조건을 가지고 단계별로 점화식으로 표현하는 방법에 대해 배우게 되었다.
[Final OK by TA] Ch. 7 P.424 Problem 2 Solved by 전솔람 finilized by 칭기즈 , 김영철, Muhammad
Solved by 전솔람 date 2018.11.06
finilized by 칭기즈 Date 2018.11.06
Finalized by 김영철 Date 2018.11.07
Re-Finalized by Muhammad Date 2018.11.10
Final OK by TA Date 2018.11.12
Problem
Assume that a person invest 4000 dollars at 17 percent interest compounded annually. Let A(n) represent the amount at the end of n years. Find a recurrence relation and an initial condition for the sequence A(0), A(1), ......
Definition 1.1
Solution
1. Let a0 be the initial amount
invested
--> a0=4000
2. After 1
year, a1 will be
--> a1 = a0 + 0.17 a0 = 1.17 a0
3. After
2 years, a2 will be
--> a2 = a1 + 0.17 a1 = 1.17 a1 = (1.17)2 a0
4. Thus,
after n years, an will be
--> an = an-1 + 0.17 an-1 = (1.17) an-1 = ... = (1.17)n a0
Answer:
Initial
state: a0=4000
Recurrence
relation: an = (1.17)an-1 ,
where a0=4000 ■
Comment:
복리계산에 대한 내용과 그것을 점화식으로 표현해 볼 수 있었다.
Comment:
Remember that recurrence relation should in the form of an represented by any predecessor term like (an-1). That’s why the relation/equation provided by the original answer (an = (1.17)n * 4000 )Is not a recurrence relation.
[Final OK by TA] Ch. 7 P.424 Problem 3 solved by 서명원 Finalized by 김영철, Muhammad, 전종문
Solved by 서명원 date 2018. 11.09
Finalized by 김영철 Date 2018.11.10
Refinalized by Muhammad Date 2018.11.10
RE- Finalized by 전종문 Date:2018.11.12
Final OK by TA Date:2018.11.12
Problem
Solution
1. Let X be an n-element set and choose x ∈ X and k be a fixed integer (0 ≤ k ≤ n - 1)
2. We can select a k-element subset Y from X - {x} in C(n-1, k) ways.
3. Next, we can partition Y in Pk ways.
4. This partition (from step 3) along with the set X - Y -> partitions X.
5. Since this works for every partition of X, the recurrence relationship is proven ■
Another Solution
To prove Pn satisfies the recurrence relation, we can find a relationship between Pn and Pn-1.
Pn = n-1∑n=0 C(n-1,k) Pk = ( n-2∑n=0 C(n-2,k) Pk )*n-1 +C(n-1,n-1)Pn-1 = (Pn-1) *n-1 + Pn-1= n*Pn-1
Then we showed that Pn = n *Pn-1 satisfies the recurrence relation ■
Comment:
일정한 규칙이 반복되는 구조일 때, 점화식으로 표현할 수 있다는 것을 알 수 있었다.
Comment:
When a certain rule was a repetitive structure, it could be expressed as recursive relation.
[Final OK by TA]Ch 7, P424, P.4 Solved by 서명원, Finalized by Muhammad
solved by 서명원 Date : 2018.11.09
Revised and Finalized by Muhammad, Date: 2018.11.09
Final OK by TA Date: 2018.11.12
Problem
Solution
If the first domino is placed as shown,
there are a n-1 ways to cover the 2 x (n-1) board that remains.
If the first two dominoes are placed as shown,
there are a n-2 ways to cover the 2 x (n-2) board that remains.
If follows that an = a n-1 + a n-2.
By inspection, a1 = 1 and a2 = 2.
Since (an} satisfies the same recurrence relation as the Fibonacci sequence
a1 = f2 and a2 = f3 ⇒ an = f n+1 ,where { f n } is the Fibonacci sequence. ■
Comment:
그림을 통해 점화식의 규칙을 알 수 있었고 피보나치 수열의 점화식에 대해서도 알 수 있었다.
Comment:
This question is an extremely easy question as long as you can make a diagram /sketch to understand what's happening under different circumstances.
[Final OK by SGLee] Ch. 7 P.424 Problem 6 전솔람, 김희성, 칭기즈 by Muhammad
Solved by 전솔람 date 2018. 11. 06.
Finalized by 김희성 date 2018.11.07
Re-Finalized by 칭기즈 and Muhammad date 2018.11.07/2018.11.10
Final OK by SGLee
Problem
Solve the recurrence relation subject to the initial conditions.
6. an = - 4 an-1 - 4 an-2 , a0 = 2 , a1 = 4
Solution
By using
the quadratic formula derived from theorem 2.14 we can see
that we can form a second power polynomial by replacing (an = x2, an-1 = x,
an-2 =1) as following:
x2 = -4x-4
x2+4x+4 = 0
D = b2-4*a*c = 16-16 = 0
x1 and x2 = -4/2 = -2
There is only one root 2 with multiplicity 2. So,
an=a*(-2n)+b*n(-2n)
* Our next step is to find the coefficients (a, b) using:
a0 = 2
a1 = 4
1. For n=0 : a0=a*(-20)+b*0(-20)=2
a =2
2. For n=1 : a1=2*(-21)+b*1(-21)=4 =-4-2b =4-2b =8
b=-4
Thus, an=2*(-2n)-4*n(-2n)
Answer:
an=2(-2n) - 4n(-2n) ■
Comment:
Second-order linear homogeneous recurrence relation with constant coefficients일 때 점화식을 푸는 방법에 대해 알 수 있었다.
Comment:
After this question we can see that no single information given in any mathematical problem is redundant, sooner or later we can use it
[Final OK by TA] Ch. 7 P.424 Problem 7 solved by 전솔람 Finalized by 김희성, 칭키즈, Muhammad
Solved by 전솔람 date 2018. 11. 06.
Finalized by 김희성 date 2018.11.07
Re-Finalized by 칭기즈 and Muhammad date 2018.11.07/2018.11.10
Final OK by TA Date 2018.11.12
Problem
Solve the recurrence relation subject to the initial conditions.
7. an = 3an-1 + 10an-2 , a(0) = 4 a(1) = 13
Solution
By using the quadratic formula derived from theorem 2.14 we can see that we can forma second power polynomial by replacing(an = x2, an-1 = x, an-2 =1) as following:
x2=3x+10
x2-3x-10=0
(x-5)(x+2)=0
X=5 x=-2
There are 2 roots so
an=a*(5n)+b*(-2n)
* Our next step is to find the coefficients(a,b) using:
a0=4
a1=13
*For n=0 : a0=a*(50)+b*(-20)=2 =a+b=4
*For n=1: a1=2*(51)+b*(-21)=13 =5a-2b=13
*Next: we will solve these equations for (a,b):
a+b=4 (1)
5a-2b=13 (2)
Let’s multiply equation (1) by 2: 2a+2b=8 (3)
Let’s add equation (3) and (2): a=3
Hence, 3+b=4 b=1
Thus,
an=3*(5n)+1*(-2n)
Answer:
an=3*(5n)+1*(-2n) ■
Comment:
Second-order linear homogeneous recurrence relation with constant coefficients일 때 점화식을 푸는 방법에 대해 알 수 있었다.
Comment:
After this question we can see that no single information given in any mathematical problem is redundant, sooner or later we can use it
[ReFinalized] Ch.7, P.424, Problem7, 칭기즈, Muhammad,김희성
solved by 칭기즈 Date 2018.11.09
Revised and Finalized by Muhammad date 2018.11.10
Re-Finalized by 김희성 date 2018.11.14
Problem
Let Cn denote the number of strings over {0,1,2} of length n that contain an even number of 1's.Write a recurrence relation and initial condition that define the sequence C1,C2 , ...
Solve the recurrence relation to obtain an explicit formula for Cn.
Solution
By the Addition Principle
Cn=(a)+(b)+(c) , where a,b,c are string types formed by {0,1,2}
there are 3 ways to form a n-length string with even number of 1's:
(a) An n-length string begins with 0 and contain an even number of 1's.
Since any (n-1)-length string containing even number of 1's can follow the initial 0 ⇒ Cn-1
(b) An n-lengths string begins with 2 and contain an even number of 1's.
Since any (n-1)-length string containing even number of 1's can follow the initial 2, ⇒Cn-1
(c) As n- length string that begins with 1 and (n-1)-length string should contain odd number of 1's
(n-1)-length string should contain odd number of 1's ⇒3n-1- Cn-1
Thus,
Cn= Cn-1+Cn-1+3n-1-Cn-1 = 3n-1+Cn-1
Initial condition : C1=2
Cn = 3n-1+Cn-1 = 31+32+33 + … + 3n-1+ C1 =2+(3n-3)/(3-1) =(3n+1)/2
Answer:
A recurrence relation and initial condition : Cn = 3n-1 + Cn-1
Initial condition : C1=2
Solution : Cn = (3n+1)/2 ■
Comment:
The idea of this questions is not simple . So I recommend you to go through the different theorems/principles mentioned through the solution before.
Comment:
점화식의 규칙이 잘 안 보일 때, 경우를 나누어서 생각하면 된다는 것을 알 수 있다.
…
Problem 22, Ch.8, P.496, Chapter-Self Test
Solved by 전종문 Date:2018.11.17
finilized by 칭기즈 Date:2018.11.17
Final OK by TA Date:2018.11.18
Final ok By Prof.Lee & Refinalized by Muhammad Date: 2018.11.28
Problem
In Exercises 21 and 22, determine whether the graphs G1 and G2 are isomorphic. Prove your answer.
22.
Definition:
---------------------------------------------------------------------
Definition 6.1
---------------------------------------------------------------------
Proof
The adjacency matrix of graph G1 relative to vertex ordering v1, v2, v3, v4, v5, v6
is equal to the adjacency matrix of graph G2 relative to the vertex ordering w1, w2, w3, w4, w5, w6
Conclusion:
∴G1 and G2 are isomorphic. ■
Comment:
This problem is quite straightforward but very useful to get better understanding of Chapter 8, especially isomorphic graphs. The idea of the problem is to check if orderings V1,V2,V3,V4,V5,V6 and W3,W6,W2,W5,W1,W4 make equal adjacency matrices.
Problem 23, Ch.8, P.496, Chapter-Self Test
Solved by 전종문 Date:2018.11.17
Finalized by 김영철 Date:2018.11.17
Final OK by TA Date:2018.11.18
Final ok By Prof.Lee & Refinalized by Muhammad Date: 2018.11.28
Problem
Answer:
To have 2 edges and 5 vertices, we have to first think about drawing one edge.
There is only 1 way to draw a graph with 1 edge. However, you try, they are
all isomorphic. Let's call the edge we have drawn as e1 and the vertices that are incident to e1 as v1 and v2.
Now let's draw the second and the last edge and call it as e2. There are only 2 choices:
(1) e2
is incident to only one vertex among v1 and v2.
--> No matter to which vertex it is incident
among v1 and v2, it counts as 1,
because the 2
cases are isomorphic.
(2) e2 is not incident to v1, nor v2.
--> Then we have e1 and e2,
and v1, v2 and v3, v4 and it counts
as 1.
(3) It is not possible that e2 is incident to both v1 and
v2.
Considering all the conditions above, we can draw total of 2 graphs, like below.
■
Comment:
This problem is quite straightforward but very useful to get better understanding of Chapter 8, especially isomorphic graphs.
Problem 24, Ch.8, P.496, Chapter-Self Test
Solved by 김승연 Date:2018.11.17
Finalized by 김정주 Date:2018.11.26
Refinalized by Muhammad. Date: 2018.11.27
Final ok By Prof.Lee & Refinalized by Muhammad Date: 2018.11.28
Problem
Draw all non isomorphic, simple graphs having exactly five vertices, two components, and no cycles.
Solution
To have such graphs there should be a clear two set of groups of vertices and each group should have different degree of vertices and in this case we have three options:
1) 2-3
vertices groups (degree of 1 – degree 2)
2) 1-4 vertices (degree 3- degree 0)
3) 1-4 vertices (degree 2 – degree 0)
■
Comment:
This problem is quite straightforward but very useful to get better understanding of Chapter 8, especially isomorphic graphs. The idea is we have to develop the thinking of considering all possible cases before sketching.
Problem 27, Ch.8, P.496, Chapter-Self Test
Solved by 전종문 Date:2018.11.17
Revised by 김영철 Date:2018.11.17
Finilized by 칭기즈 Date:2018.11.17
Final OK by TA Date:2018.11.20
Final ok By Prof.Lee & Refinalized by Muhammad Date: 2018.11.28
Problem
Proof
Euler’s formula is
v−e+f = 2
The sum of the degrees of the regions is equal to twice the number of edges.
But each region must have degree ≥ 3.
So we have
2e ≥ 3f.
Thus,
2e ≥ 3(2-v+e)
Therefore,
e ≤ 3v − 6.
31≤ 3(12)-6 = 30 is false.
Sage code:
g = graphs.CompleteBipartiteGraph(31,12)
g.show()
g.is_planar()
Practical image:
Conclusion:
So, 31 edges and 12 vertices is not planar. ■
Comment:
This problem is quite straightforward but very useful to get better understanding of Chapter 8, especially isomorphic graphs. The idea is we have to revise all the terminology then proceed to solving while keeping the graphs in mind.
Problem 28, Ch.8, P.496, Chapter-Self Test
Solved by 전종문 Date:2018.11.17
Revised by 김영철 Date:2018.11.17
Final OK by TA Date:2018.11.20
Final ok By Prof.Lee & Refinalized by Muhammad Date: 2018.11.28
Problem
Proof
0. In a planar graph, each edges belongs to at most two bounding cycles. Therefore, 2e ≥ 4f .
1. Euler’s formula is v−e+f = 2
2. Then, 2e≥ 4(e-v+2) ⇒ 2v ≥ e+4
3. For the n-cube, we have v=2n , e = n*2n-1
4. Then, 2n+1 ≥ n*2n-1 +4 ⇒ (n-4)2n-1 +4≤ 0
5. If n≤3, (n-4)2n-1 +4≤ 0 is true.
6. But n>3, (n-4)2n-1 ≥ 0 ⇒ (n-4)2n-1 +4> 0 .
∴ The n-cube is planar if n≤3 and not planar if n>3 ■
Comment:
This problem is quite straightforward but very useful to get better understanding of Chapter 8, especially isomorphic graphs. The idea is we have to revise all the terminology then proceed to solving while keeping the graphs in mind specially for the planar part.
Problem 29, Ch.8, P.496, Chapter-Self Test
Solved by 강병훈 Date.2018.11.17
Finilized by 칭기즈 Date.2018.11.17
Final OK by TA Date 2018.11.23
Final ok By Prof.Lee & Refinalized by Muhammad Date: 2018.11.28
Problem
Scheme:
Here is an image of four cubes just for convenience:
(see
next page)
Note:
Draw one vertex for each color and an edge between two vertices if those colors are opposite faces on the cube.
Solution
We will name the vertices as R, G, W and B. The edges will be named as 1, 2, 3 and 4 depending on which cube they come from.
Keeping these two points in mind, we will have the following:
1. Three edges labeled (1) can be drawn between vertices {B,G}, {G, R}, {G, B}. These edges come from the first cube.
2. Similarly, three edges labeled (2) can be drawn between vertices {R, B}, {G, B}, {W, W}. These edges come from the second cube.
3. Similarly, three edges labeled (3) can be drawn between vertices {R, W}, {B, R}, {W, G}. These edges come from the third cube.
4. Similarly, three edges labeled (4) can be drawn between vertices {W, B}, {W, R}, {R, B}. These edges come from the fourth cube.
5. Below is the corresponding graph:
■
Comment:
This problem is very easy but useful to understand the concept of graph theory. The key idea is to represent cubes by graph by drawing edges between two vertices if those colors are opposite faces on the cube.
Problem 31, Ch.8, P.496, Chapter-Self Test
Solved By 오동찬, Date: 2018.11.17
Finilized by 칭기즈Date: 2018.11.17
Re-finilized by 김정주 date:2018.11.22
Final ok By Prof.Lee & Refinalized by Muhammad Date: 2018.11.28
Problem
Find all subgraphs of the graph of Exercise 29 satisfying properties (8,1) and (8,2).
*Graph of Exercise 29
Definition:
-----------------------------------------------------------------------------
Definition 2.8
---------------------------------------------------------------------------
Property
■ Each vertex should have degree 2. (8.8.1)
■ Each cube should be represented by an edge exactly once in each graph. (8.8.2)
Solution
There are total six graphs.
I will denote as Gn (n= 1,2,3,4,5,6). ■
Comment:
This problem is a good exercise that helps to get better understanding of subgraphs where the idea is to from a subset of the vertices of the graph and all the edges connecting pairs of vertices in that subset.
Problem 32, Ch.8, P.496, Chapter-Self Test
Solved By 오동찬, Date: 2018.11.17
Revised by 칭기즈 Date: 2018.11.17
Final ok By Prof.Lee & Refinalized by Muhammad Date: 2018.11.28
Problem
Use Exercise 31 to determine how many solutions the puzzle of Exercise 29 has.
*Graph of Exercise 29
8 Graphs of Exercise 31.
Subgraphs:
Solution and Conclusion:
Using the notation of solution of Exercise 31,
There are four possible solutions in the puzzle.
i) G1, G5
ii) G2, G5
iii) G3, G6
iv) G4, G6 ■
Comment:
This problem is a good exercise that helps to get better understanding of subgraphs where the idea is to from a subset of the vertices of the graph and all the edges connecting pairs of vertices in that subset.
SKKU Discrete Mathematics (DM Ch 8, Graph Theory)
Prof : Sang-Gu Lee
Prob. and Solutions by Team 4
Muhammad Shakeel Zuhaib (Leader) 2017314461
Kim Jung Ju 2011312426
Yeog Chung Pyeong 2017315123
Hyung Jun Chang 2017314956
Lee Yun Sung 2013312352
• Collected by Kim Jung Ju (김정주)
• Finalized by Muhammad Shakeel Zuhaib 2017314461
DM Ch 8, Graph Theory Important Links/Websites:
Lecture Note and Ch 8 Lab http://matrix.skku.ac.kr/2018-DM/DM-Ch-8-Lab.html
Ch-8-Lab 2 http://matrix.skku.ac.kr/2014-Models/Graph-Project.html
http://discretetext.oscarlevin.com/dmoi/sec_gt-intro.html
(DM
Sec 8.1 동영상강의) Graph Theory https://youtu.be/TSFIJBU2dX8
(DM Sec 8.2 동영상강의) Path and Cycle https://youtu.be/iqUTT5C1TOs
(DM Sec 8.3 동영상강의) Hamiltonian cycle https://youtu.be/at7Hx5wxnYk
(DM Sec 8.4 동영상강의) Shortest Path https://youtu.be/MHDJ3rALtEU
http://matrix.skku.ac.kr/2018-DM/DM-Labs.htm Discrete Math Labs (실습실)
http://matrix.skku.ac.kr/2018-album/2018-Lectures-sglee.htm (강의실)
http://matrix.skku.ac.kr/2018-DM-QnA/ (질문과 답변)
http://matrix.skku.ac.kr/2018-DM-Sol/2018-DM-Sol.htm (문제풀이)
http://matrix.skku.ac.kr/2018-DM-PBL/ (PBL report 보고서)
http://matrix.skku.ac.kr/2018-DM-PBL-Eng/ (PBL report Eng, 영문 보고서)
Problem 1, Ch.8, P.495, Chapter-Self Test
Solved by 전종문 Date:2018.11.16
Finalized by 오동찬 Date:2018.11.16
Re-Finalized by 김영철 Date:2018.11.16
Final OK by TA Date:2018.11.18
Final OK By Prof.Lee & Refinalized by Muhammad Date: 2018.11.28
Problem
Answer:
We can see that we have to investigate the graph G made up of vertices of
subset V and subset E.
1. As v1, v2, v3, v4 are vertices of subset V and e1, e2, e3 are vertices of subset E,
we can say that V={v1, v2, v3, v4} and E={e1, e2, e3},
2. Both e1, e2 are edges that connect v2, v3 . So they are parallel edges.
3. There is no loop.
4. v1 is the only isolate vertex, as there is no edge coming out from v1 .
5. G is not a simple graph
6. 'Incident' means a vertex and an edge is connected directly.
So edge e3 incident on v2, v4 ,
and v2 is incident on e1, e2, e3 ■
Comment:
Graph Theory에서 배우는 Edge와 Vertices에 관해 이해하고 풀 수 있는 간단한 예제였습니다.
This is a simple example on edge theory with vertex and edges manipulation.
Problem 2, Ch.8, P.495, Chapter-Self Test
Solved by 전종문 Date:2018.11.16
Finalized by 김영철 Date:2018.11.16
Final OK by TA Date:2018.11.18
Final ok By Prof.Lee & Refinalized by Muhammad Date: 2018.11.28
Problem
Proof
As vertex a has 3 edges and e has 3 edges, we can say that they are of odd degrees.
If there exist vertices of odd degree, in a graph, that graph does not
have a
path from a to a that passes through each edge exactly one time, which is called
the 'Hamiltonian Cycle'.
■
Comment:
This is a simple example on edge theory with vertex and edges manipulation where knowing the terminology is the key to solve this question.
Problem 3, Ch.8, P.495, Chapter-Self Test
Solved by 전종문 Date:2018.11.16
Finalized by 김영철 Date:2018.11.16
Final OK by TA Date:2018.11.18
Final ok By Prof.Lee & Refinalized by Muhammad Date: 2018.11.28
Problem
Draw K2,5 , the complete bipartite graph on 2 and 5 vertices.
Answer
To draw a Bipartite Graph(이분 그래프), there should be
no edge between the vertices in a same subset.
So all edges must be between vertices from different subsets.
So here, as there are 2 subsets, who have 2 and 5 vertices each,
We can draw it as below:
■
Comment:
This is a simple example on edge theory with vertex and edges manipulation where knowing the terminology is the key to solve this question such as “Bipartite”.
Problem 4, Ch.8, P.495, Chapter-Self Test
Solved김주형 Date:2018.11.20
Finalized by 김승연 Date:2018.11.24
Refinalized by Muhammad Date:27.11.2018
Final ok By Prof.Lee & Refinalized by
Muhammad Date: 2018.11.28
Problem
Prove that n-cube is bipartite for all n≥1.
Solution
Step 1: When labeling n-cube, we can assign the vertices strings of length n from 00...0 to 11…1. (n is determined by n-cube’s n number.)
Step 2: Two subsets of the graph G =(V, E) could be defined.
*Where V1= {vertices who have an even number of 1's} and V2={vertices who have an odd number of 1's}
Step 3: By creating two edges {1, 0} or {0, 1} starting in V1 and ending in V2
all edges are accounted for. Thus, the graph is bipartite. ■
Diagram Representation:
The difference between any one vertex and its adjacent vertex is only one bit.(0,1)
Comment:
This is a simple example on edge theory with vertex and edges manipulation where knowing the terminology is the key to solve this question such as “Bipartite”.
Problem 5, Ch.8, P.495, Chapter-Self Test
Solved by 전종문 Date:2018.11.16
Revised by 김영철 Date:2018.11.16
Re-Finalized by 정호진 Date:2018.11.18
Final OK by TA Date:2018.11.18
Final ok By Prof.Lee & Refinalized by Muhammad Date: 2018.11.28
Problem
Solution
As you can see from the problem above, you can start from v2,
and then after visiting v3, v4, v2, v6 and v1 sequentially,
you can come back to v2. So, it is a cycle. And this path includes repeated vertices, so it is not a simple path and simple cycle.
Answer:
Path (v2 , v3 ,v4 ,v2 ,v6 ,v1 ,v2) is cycle. ■
Comment:
For solving such problems it’s really important to understand what a simple cycle means and how is drawn in a graph.
Problem 6, Ch.8, P.495, Chapter-Self Test
Solved by 김승연 Date:2018.11.17
Revised by 김영철 Date:2018.11.17
Final OK by TA Date:2018.11.20
Final ok By Prof.Lee & Refinalized by Muhammad Date: 2018.11.28
Problem
Solution
1. In the graph above, there are 3 edges.
2. So if you want to make a subgraph which has 2 edges,
there are 3C2 cases of choosing which edges to include in that subgraph (= 6 cases).
3. And in each of those cases, as there are 2 edges,
at least 2 vertices among v2, v3 and v4 should be included in that subgraph,
as they should be connected to those 2 edges.
4. And as now we know that at least 2 vertices among v2, v3 and v4 should be included,
we should decide whether we must include the remaining 1 vertex among those 3, or not.
5. Include or not, we have 2 cases. As there are 6 cases of choosing which edges to include,
we have total of 2 * 6 = 12 cases, and they are like below : (see next page)
Comment:
For solving such problems it’s really important to how to extract subgraphs from bigger graphs using specific options.
Problem 7, Ch.8, P.495, Chapter-Self Test
Solved by 김승연 Date: 2018.11.17
Revised and FInalized by Muhammad Date: 2018.11.27
Final ok By Prof.Lee & Refinalized by Muhammad Date: 2018.11.28
Problem
Find a connected subgraph of the graph of Exercise 5 containing all of the vertices of the original graph and having as few edges as possible.
Discussion
Here is definition of connected graph:
A connected graph is a graph in which we can get from any vertex to any other vertex on a path.
--------------------------------------------------------------------
Definition 2.4
A graph is connected if given any vertices and in , there is a path from to .
--------------------------------------------------------------
Solution
The number of edges must be equal to 'the number of vertex - 1 ' and there are 7 vertices here.Hence the number of edges is 6 and and could be graphed as following:
Comment:
This Problem shows how a simple graph problem could be continued to address different ideas.
Problem 11, Ch.8, P.495, Chapter-Self Test
Solved by 강병훈 Date.2018.11.17
Revised by 칭기즈 Date.2018.11.17
Finalized by Muhammad Date 2018.11.23
Final ok By Prof.Lee & Refinalized by Muhammad Date: 2018.11.28
Problem Show that the graph has no Hamiltonian cycle.
Note:
A Hamiltonian cycle, also called a Hamiltonian circuit, Hamilton cycle, or Hamilton circuit, is a graph cycle (i.e., closed loop) through a graph that visits each node exactly once .
Solution:
Since there are seven vertices, a Hamiltonian cycle must have seven edges. Suppose that we could eliminate edges from the graph, leaving just a Hamiltonian cycle:
We would have to eliminate three edges at vertex b and one edge at vertex f. This leaves 10−4=6 edges,
thus, it does not have enough number of edges for a Hamiltonian cycle.
Conclusion:
Therefore, the graph does not have a Hamiltonian cycle. ■
Comment: For solving such kind of problems it’s really important to know the terminology used in graphs.
Problem 13, Ch.8, P.495, Chapter-Self Test
Solved by 전종문
Date:2018.11.17
Finalized by 김영철 Date:2018.11.17
Final OK by TA Date:2018.11.18
Final ok By Prof.Lee & Refinalized by Muhammad Date: 2018.11.28
Problem
Solution
If you start from a, you can go to b, e and h.
So let's divide this problem into that 3 possible choices.
(1) a -> b
Now, as we
are at b, we can go to c, f or e.
But if we go to e, it will be an indirect path of a -> e, whose
length is 10 and it is longer than
the length of direct path of a -> e, which is 1.
So a -> b -> e is already longer than something.
As we are looking for a shortest path, we have to discard a -> b -> e.
So we only have to consider a -> b -> c and a -> b -> f.
Of course a -> b -> c -> f is an indirect path of a -> b -> f,
but as their length are both 4, so we don't have to discard one of them.
All the possible paths of such cases and their distances are like below : (see next page)
(a, b, f, i ) ⇒ 10
(a, b, c, f, i ) ⇒ 10
(2) a -> e
Now, as we
are at e, we can go to f or h.
But if we go to h, it will be an indirect path of a -> h, whose
length is 9 and it is longer than
the length of direct path of a -> h, which is 6.
So a -> e -> h is already longer than
something.
As we are looking for a shortest path, we have to discard a -> e -> h.
So we only have to consider a -> e -> f.
The only possible path of such case and its distance is like below :
(a, e, f, i ) ⇒ 9
(3) a -> h
The
only possible path of we have from h,
not repeating the cases already considered above, is like below :
(a , h, i ) ⇒ 14
Therefore, (a, e, f, i ) ⇒ 9 is shortest path from a to i.
Answer: 9 ■
Comment:
For solving such kind of problems it’s really important to go through different approaches/algorithms of shortest path problem.
Problem 14, Ch.8, P.495, Chapter-Self Test
Solved by 전종문 Date:2018.11.17
Finalized by 강병훈 Date:2018.11.17
Final OK by TA Date:2018.11.18
Final ok By Prof.Lee & Refinalized by Muhammad Date: 2018.11.28
Problem
14.Find the length of a shortest path from a to z.
Solution
The path i, g, z is the shortest path which has only 2 edges in the preceding graph.
And we know that the length of a shortest path from a to i is 9 at problem 13.
So, the length of a shortest path from a to z is (a, e, f, i, g, z )⇒ 11.
Answer: The length of a shortest path from a to z is 11. ■
Comment:
For solving such kind of problems it’s really important to go through different approaches/algorithms of shortest path problem.
Problem 15, Ch.8, P.495, Chapter-Self Test
Solved by 전종문 Date:2018.11.17
Finalized by 강병훈 Date:2018.11.17
Re-finalized by 조영은 Date:2018.11.19
Final OK by TA Date:2018.11.20
Final ok By Prof.Lee & Refinalized by Muhammad Date: 2018.11.28
Problem
15. Find a shortest path from a to z.
Solution
We know that the length of a shortest path from a to z is (a, e, f, i, g, z )⇒ 11.
Answer
The shortest path from a to z is (a, e, f, i, g, z ) ■
Comment:
For solving such kind of problems it’s really important to go through different approaches/algorithms of shortest path problem. Moreover, finding the shortest path easily leads to finding the vertices involved.
Problem 16, Ch.8, P.495, Chapter-Self Test
Solved by 전종문 Date:2018.11.17.
Finalized by 강병훈 Date:2018.11.17.
Re-Finalized by 조영은 Date:2018.11.19.
Final OK by TA Date:2018.11.20
Final ok By Prof.Lee & Refinalized by Muhammad Date: 2018.11.28
Problem
16.Find the length of a shortest path from a to z that passes through c.
Solution
The length of a shortest path from a to c is (a, b, c) ⇒ 5.
And, the length of a shortest path from c to z is (c, d, z) ⇒ 7.
So, the length of a shortest path from a to z is ( a, b, c, d, z) ⇒ 12.
Answer
The length of a shortest path from a to z is 12. ■
Comment:
For solving such kind of problems it’s really important to go through different approaches/algorithms of shortest path problem. Moreover, finding the shortest path easily leads to finding the vertices involved unless we have a specified vertex we have to move through.
Problem 20, Ch.8, P.496, Chapter-Self Test
Solved by 김주형 Date:2018.11.17
finilized by 권혁찬 Date:2018.11.17
Final OK by TA Date:2018.11.23
Final ok By Prof.Lee & Refinalized by Muhammad Date: 2018.11.28
Problem
20. Can a column of an incidence matrix consist only of zeros? Explain.
Solution
incidence matrix : row = vertex / column = edge
a column of an incidence matrix consist only of zeros
⇔ there is an edge that don't connect any vertices in the graph.
⇔ The edge does not exist.
∴ graph와 관련없는 column이 있을 필요가 없으므로 0으로만 구성된 column은 incidence matrix는 없을 것이다. ■
Comment
---------------------------------------------------------------------
Example 5.5: Incidence Matrix
To obtain the incidence matrix of the graph, we label the rows with the vertices and columns with the edges.
The entry for row and column is if is incident on and otherwise. Thus the incidence matrix for the graph of Figure 5.4.
Figure 5.4
A column such as is understood to represent a loop. As you can see from this example, there are not any incidence matrices have a column consisted only of zeros.
Problem 22, Ch.8, P.496, Chapter-Self Test
Solved by 전종문 Date:2018.11.17 finilized by 칭기즈 Date:2018.11.17 Final OK by TA
Final ok By Prof.Lee & Refinalized by Muhammad Date: 2018.11.28
Problem
In Exercises 21 and 22, determine whether the graphs G1 and G2 are isomorphic. Prove your answer.
22.
Definition:
---------------------------------------------------------------------
Definition 6.1
---------------------------------------------------------------------
Proof
The adjacency matrix of graph G1 relative to vertex ordering v1, v2, v3, v4, v5, v6
is equal to the adjacency matrix of graph G2 relative to the vertex ordering w1, w2, w3, w4, w5, w6
Conclusion:
∴G1 and G2 are isomorphic. ■
Comment:
This problem is quite straightforward but very useful to get better understanding of Chapter 8, especially isomorphic graphs. The idea of the problem is to check if orderings V1,V2,V3,V4,V5,V6 and W3,W6,W2,W5,W1,W4 make equal adjacency matrices.
Problem 23, Ch.8, P.496, Chapter-Self Test
Solved by 전종문 Date:2018.11.17
Finalized by 김영철 Date:2018.11.17
Final OK by TA Date:2018.11.18
Final ok By Prof.Lee & Refinalized by Muhammad Date: 2018.11.28
Problem
Answer:
To have 2 edges and 5 vertices, we have to first think about drawing one edge.
There is only 1 way to draw a graph with 1 edge. However, you try, they are
all isomorphic. Let's call the edge we have drawn as e1 and the vertices that are incident to e1 as v1 and v2.
Now let's draw the second and the last edge and call it as e2. There are only 2 choices:
(1) e2
is incident to only one vertex among v1 and v2.
--> No matter to which vertex it is incident
among v1 and v2, it counts as 1,
because the 2
cases are isomorphic.
(2) e2 is not incident to v1, nor v2.
--> Then we have e1 and e2,
and v1, v2 and v3, v4 and it counts
as 1.
(3) It is not possible that e2 is incident to both v1 and
v2.
Considering all the conditions above, we can draw total of 2 graphs, like below.
■
Comment:
This problem is quite straightforward but very useful to get better understanding of Chapter 8, especially isomorphic graphs.
Problem 24, Ch.8, P.496, Chapter-Self Test
Solved by 김승연 Date:2018.11.17
Finalized by 김정주 Date:2018.11.26
Refinalized by Muhammad. Date: 2018.11.27
Final ok By Prof.Lee & Refinalized by Muhammad Date: 2018.11.28
Problem
Draw all non isomorphic, simple graphs having exactly five vertices, two components, and no cycles.
Solution
To have such graphs there should be a clear two set of groups of vertices and each group should have different degree of vertices and in this case we have three options:
1) 2-3
vertices groups (degree of 1 – degree 2)
2) 1-4 vertices (degree 3- degree 0)
3) 1-4 vertices (degree 2 – degree 0)
■
Comment:
This problem is quite straightforward but very useful to get better understanding of Chapter 8, especially isomorphic graphs. The idea is we have to develop the thinking of considering all possible cases before sketching.
Problem 27, Ch.8, P.496, Chapter-Self Test
Solved by 전종문 Date:2018.11.17
Revised by 김영철 Date:2018.11.17
Finilized by 칭기즈 Date:2018.11.17
Final OK by TA Date:2018.11.20
Final ok By Prof.Lee & Refinalized by Muhammad Date: 2018.11.28
Problem
Proof
Euler’s formula is
v−e+f = 2
The sum of the degrees of the regions is equal to twice the number of edges.
But each region must have degree ≥ 3.
So we have
2e ≥ 3f.
Thus,
2e ≥ 3(2-v+e)
Therefore,
e ≤ 3v − 6.
31≤ 3(12)-6 = 30 is false.
Sage code:
g = graphs.CompleteBipartiteGraph(31,12)
g.show()
g.is_planar()
Practical image:
Conclusion:
So, 31 edges and 12 vertices is not planar. ■
Comment:
This problem is quite straightforward but very useful to get better understanding of Chapter 8, especially isomorphic graphs. The idea is we have to revise all the terminology then proceed to solving while keeping the graphs in mind.
Problem 28, Ch.8, P.496, Chapter-Self Test
Solved by 전종문 Date:2018.11.17
Revised by 김영철 Date:2018.11.17
Final OK by TA Date:2018.11.20
Final ok By Prof.Lee & Refinalized by Muhammad Date: 2018.11.28
Problem
Proof
0. In a planar graph, each edges belongs to at most two bounding cycles. Therefore, 2e ≥ 4f .
1. Euler’s formula is v−e+f = 2
2. Then, 2e≥ 4(e-v+2) ⇒ 2v ≥ e+4
3. For the n-cube, we have v=2n , e = n*2n-1
4. Then, 2n+1 ≥ n*2n-1 +4 ⇒ (n-4)2n-1 +4≤ 0
5. If n≤3, (n-4)2n-1 +4≤ 0 is true.
6. But n>3, (n-4)2n-1 ≥ 0 ⇒ (n-4)2n-1 +4> 0 .
∴ The n-cube is planar if n≤3 and not planar if n>3 ■
Comment:
This problem is quite straightforward but very useful to get better understanding of Chapter 8, especially isomorphic graphs. The idea is we have to revise all the terminology then proceed to solving while keeping the graphs in mind specially for the planar part.
Problem 29, Ch.8, P.496, Chapter-Self Test
Solved by 강병훈 Date.2018.11.17
Finilized by 칭기즈 Date.2018.11.17
Final OK by TA Date 2018.11.23
Final ok By Prof.Lee & Refinalized by Muhammad Date: 2018.11.28
Problem
Scheme:
Here is an image of four cubes just for convenience:
(see
next page)
Note:
Draw one vertex for each color and an edge between two vertices if those colors are opposite faces on the cube.
Solution
We will name the vertices as R, G, W and B. The edges will be named as 1, 2, 3 and 4 depending on which cube they come from.
Keeping these two points in mind, we will have the following:
6. Three edges labeled (1) can be drawn between vertices {B,G}, {G, R}, {G, B}. These edges come from the first cube.
7. Similarly, three edges labeled (2) can be drawn between vertices {R, B}, {G, B}, {W, W}. These edges come from the second cube.
8. Similarly, three edges labeled (3) can be drawn between vertices {R, W}, {B, R}, {W, G}. These edges come from the third cube.
9. Similarly, three edges labeled (4) can be drawn between vertices {W, B}, {W, R}, {R, B}. These edges come from the fourth cube.
10. Below is the corresponding graph:
■
Comment:
This problem is very easy but useful to understand the concept of graph theory. The key idea is to represent cubes by graph by drawing edges between two vertices if those colors are opposite faces on the cube.
Problem 31, Ch.8, P.496, Chapter-Self Test
Solved By 오동찬, Date: 2018
Finilized by 칭기즈Date: 2018.11.17 Re-finilized by 김정주 date:2018.11.22
Final ok By Prof.Lee & Refinalized by Muhammad Date: 2018.11.28
Problem
Find all subgraphs of the graph of Exercise 29 satisfying properties (8,1) and (8,2).
*Graph of Exercise 29
Definition: Definition 2.8
---------------------------------------------------------------------------
Property
■ Each vertex should have degree 2. (8.8.1)
■ Each cube should be represented by an edge exactly once in each graph. (8.8.2)
Solution
There are total six graphs.
I will denote as Gn (n= 1,2,3,4,5,6).
■
Comment:
This problem is a good exercise that helps to get better understanding of subgraphs where the idea is to from a subset of the vertices of the graph and all the edges connecting pairs of vertices in that subset.
Problem 32, Ch.8, P.496, Chapter-Self Test
Solved By 오동찬, Date: 2018.11.17 Revised by 칭기즈 Date: 2018.11.17
Final ok By Prof.Lee & Refinalized by Muhammad Date: 2018.11.28
Problem
Use Exercise 31 to determine how many solutions the puzzle of Exercise 29 has.
*Graph of Exercise 29
8 Graphs of Exercise 31.
Subgraphs:
Solution and Conclusion:
Using the notation of solution of Exercise 31,
There are four possible solutions in the puzzle.
i) G1, G5
ii) G2, G5
iii) G3, G6
iv) G4, G6 ■
Comment:
This problem is a good exercise that helps to get better understanding of subgraphs where the idea is to from a subset of the vertices of the graph and all the edges connecting pairs of vertices in that subset.
------------------- Chapter 8 Done ---------------------
Copyright @ 2018 SKKU Matrix Lab. All rights reserved.
Made by Manager: Prof. Sang-Gu Lee and
Dr. Jae Hwa Lee
*This research was supported by Basic Science Research
Program through the National Research Foundation of Korea (NRF) funded by the
Ministry of Education (2017R1D1A1B03035865).