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, 영문 보고서)

 

PBL report of Mr. Muhammad Shakeel Zuhaib

Major: Software (2학년)

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

[Team 4] Leader 모하메드  with 김정주, 역충평, 장형준, 이윤성 (Ch 8) 
          Ch-8-PBL-Solution-모하메드 https://youtu.be/f7_WFw6AtAE
     SKKU DM Ch 8, Graph Theory (review part 2)
     (Review Lecture)   https://youtu.be/do4UjVAplp0

 

General Academic Knowledge (Ch.1 – Ch.9)

(1)  State more than 10 DM Definitions and concepts what you learned in Ch. 1, 2, 3, 4, 5, 6, 7, 8, 9.

·        Chapter 1: Power Set, Cardinality, Intersection, Relative component, Proposition, De    Morgan’s law, Rules of Inference, Deductive Reasoning, Quantifiers and Domain of Discourse.

·         Chapter 2: Axioms, Definitions, Proof by Contradiction, Proof by Contrapositive, Proof by Cases, Mathematical Induction and Well Ordering Property.

·        Chapter 3: Functions, Pseudo Random Numbers, One to One Function (Injective), On to One Function (Bijective), String, Binary Relation, Symmetric/Anti-Symmetric relation, Equivalence Classes, Matrix of Relation, Relational Data Base.

·        Chapter 4: Finiteness, Determinism, Insertion Sort, Big O notation, Theta Notation, Omega Notation and Recursive Function.

·        Chapter 5: Prime Numbers, Composite numbers, Greatest Common Devisor, Prime Factorization, Least Common Multiple and The Euclidean Algorithm.

·        Chapter 6: Multiplication Principle, Addition Principle, Inclusion-Exclusion Principle, Permutation, Combination, Binomial Theorem, Combinatorial Identity and The Pigeonhole Principle.

·        Chapter 7: Recurrence Relation, Cobweb and Ackermann’s Function.

·        Chapter 8: Graph, Bacon Numbers, Hypercube, Complete Graph, Bipartite Graph, Isomorphism, Hamiltonian Cycle and the Shortest Path Problem.

·        Chapter 9: Free Tree, Huffman Code, Spanning Trees, Breadth-First Search, Depth-First Search, Prim’s Algorithm and In order Traversal.

(2)  State more than 9 things that you know/can/find after you studied the 9 Chapters.

Since every chapter is a follow up for the chapter before it; it would be better to put a clear distinction between the academic and the mathematical things I have learnt from each part as following:

·        Part 1: In chapter 1, I have filled and revised the knowledge I had back in school times about Sets and the functions related to them. Moving on we learnt new notations to describe any mathematical or real-life proposition by using Quantifiers.

·        Part 2: in chapter 2, the most essential technique, that I have always been struggling with, which I have learnt is proving any mathematical statement using various methods from direct proofing to mathematical induction.

·        Part 3: in chapter3, this chapter broadened my horizon with new terminology. In addition, I discovered different ways to resemble a relation. For instance, by using a matrix or a data base table.

·        Part 4: in chapter4, this chapter I would say was the most interesting chapter for me since I relate to Software department. As far as for the things I have learnt and revised were around the area of analyzing any given algorithm using the three notations mentioned earlier.

·        Part 5: in chapter 5, it became easier to identify basic quantities related to any given number like the Greatest Common Devisor and Least Common Multiple.

·        Part 6: after studying chapter 6, the whole curriculum changed where I could actually relate the book topics to real world problems or my other courses directly. For instance, I can use Pigeonhole principle to analyze how statistics of a certain property work. E.g. “there are at least two students in SKKU who have the same grade”

·        Part 7: in chapter 7, this chapter opened a new world of possibilities for me specifically in programming where I could use recursive functions or recurrence relations to simplify my code instead of depending on the iterative method.

·        Part 8: in chapter 8, I learnt about applying Dijkstra’s Algorithm to solve the shortest path problem which a very famous problem in Computer Science. Moreover, through the different set of problems I discovered different types of graphs/subgraphs.

·        Part 9: chapter 9 is a follow up chapter for the previous one where I connected my previous knowledge of graphs and Data structure with book’s material to learn more about tree representation and tree traversal methods.

* Personal Reflection Note

(1) Do you understand the most of contents of this learning process?

Yes, due to the fact that the professor already uploads the lectures beforehand and then revise it with us in an offline lecture makes the understanding ability higher. Moreover, in class discussion makes a significant difference on the overall learning and understanding process. In addition, after the midterm we started to have a weekly one-hour offline discussion where we can revise what we studied and clear any misconceptions we have regarding any topic.

 

(2) What did you learn through the learning activities of this course?

Other than the academic and mathematical knowledge that I mentioned above. The learning curriculum and environment made me more confident about my answers knowing the fact that I can always improvise and revise my own solutions. In addition, I got more familiar with the team work spirit shown by the other students which can be reflected in their quick replies that are intended to enhance the courses’ output for everyone. Moreover, I realized that online discussion could bring a whole new world of possibilities where everyone could use abundant resources to strengthen their point of views

 

(3)  What have you learned from other colleagues?

I have leant how to stay organized and follow the rules instead of being extra quick and inefficient. At the same time, I learnt that working and learning in a group is far better than learning individually since there is always a chance to improvise by learning from others and sharing different ideas.

 

(4)  How do you apply newly learned information to real world problems?

As a foreigner and a Software College student, applying the mathematical laws to a real-world problem is an important thing but what is more important is applying the skills that I am learning from this course onto real-life problems and issues. For instance, I am now always trying to put myself in different discussions rather than staying in the shadows even if it was discussions done by my Korean colleagues. Plus, I always tackle any given deadline by the time-management skills I have learnt from this courses’ curriculum. Moreover, my general programming skills got better through applying discrete mathematics techniques on computer science related problems.

 

 

(5)  What kind of learning materials have you used to study?

 

I basically studied the Prof. Lee’s online/YouTube lectures and notes provided by the professor, followed by discussions on QnA where other students can clarify any doubts I might have. Next, the offline lectures made a drastic change where we can have a one to one discussion with the professor and the other students which is finally finished by practicing our knowledge through solving different exercise problems from the text book on the QnA section.

 

 

(6)  Self-Evaluation for Q/A Activities.

My Score: Although it is hard to criticize myself I would give myself a score of  */10. Which is higher than my last month’s evaluation because I believe I have grew to become a better DM student.

Self-Evaluation [Your Opinions]

(1) Satisfaction according to the self-evaluation.

I would say I am satisfied with my overall performance which was very good since I tried my best to ask, solve, revise and finalize as many inquiries as possible. Moreover, I tried to share as much experience with the other as I can. In addition, I changed my approach of learning from questions to discussion which attracted more people and lent me more knowledge.

(2) Sorrow according to the self-evaluation.

The thing that I would definitely have an issue with and I would criticize myself for is the late replies, sometimes I can’t keep up with the number of posts. Which eventually makes my responses come out with a little bit of latency and this is why I deducted 0.5 in my self-evaluation score. Yet Am still improving and I have significantly got better than my last PBL report.

 

Colleague who helped you learning [Your Opinions]

 * Name of Your Class Mate: Chingis Oinar

  (1) Reasons to recommend him

He has been extremely active through the QnA, which is very interesting to see it coming from a foreigner freshman from my major. Moreover, he has been always helpful in different discussions whether it was offline or online which encouraged me to be more active so that I could play a vital role in this experience.

   (2) Your suggestions for him to improve his contributions to other

Although he has been doing an excellent job, the only thing I would recommend him is to try to have more explanation/comments for the people who don’t have any background about coding. Since his forte is coding and solving algorithms.

 

Colleagues who helped you learn [Your Opinions]

 *Note: this part is more of a general response rather than picking a specific person as above mentioned.

  (1) Satisfaction according to the evaluation

Judging from the online performance of my class mates, I would certainly say that everyone is quite satisfied with the system and the environment that the professor provided us with, as long as they are putting enough effort.

   (2) Sorrow according to the self-evaluation

The only sorrow I noticed that others are having is that sometimes a good number of students are too late, so they start solving the questions that have already been solved which causes confusion and leads to an unorganized manner.

 

PBL Feedback for Students

(1)            What is the merit/importance/Significance of this PBL class?

The PBL-Flipped Class is playing a vital role in changing the learning experience as it shows the power of online discussions and following the online material. I want to really appreciate the professor to design such a fantastic course outline which is very different from traditional teaching styles. This kind of learning should be applied on other courses since it gives the chance for us as students to interact with each other way more than just sitting in a class and following the old-styled material.

(2)             What do you want to improve this PBL system?

For me, the Professor, the TA and the Students are doing a great job in keeping an efficient environment that everyone can benefit from. On the other hand, I would really suggest focusing on the students that are lagging and not doing a great job by assigning them tasks rather than waiting for them to start a discussion. The reason I am saying that is the fact that some students have troubles in understanding the fast pace of others plus some students are too shy to post anything online. Although the team leaders tried to minimize this issue, but still it needs more work.

Participation Part

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.

 

* PBL Participation Part

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.

 r

∨¬q

 q

-----------------

 q

 

Solution

By using Truth Table.

 

Case

p

q

r

-q

∨ r

∨ r

 

q

 

∨ 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, lets 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 (pq)  ((p r) q))​​

 

Solution:

pq - true; p r - false;

(p r) q) - true; ((p r) q))​​​ - false;

(pq)  ((p r) q))​​ - false

 

-------------------------------------------------------------------

Truth Table: 

p

q

r

-p

p∨q

∧ r

(∧ ∨ q

 ((∧ ∨ q)

∨ q((∧ ∨ 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, band c are real numbers. Represent the statement

 

a<b or (b<c and  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 = {1, 3, 4, 5, 6, 7}= {is an even integer},

= {2, 3, 4, 5, 6}, find (∩ B C.

 

Solution

 

 = {1, 3, 4, 5, 6, 7}

= {is an even integer}=2,4,6,8,10,...

= {2, 3, 4, 5, 6}

 ∩ B​= {4,6}​ 

 

Since, (∩ B​)  C

 (∩ 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, ≥ c is same to the reverse of ​q ( b < c )​, so ≥ c represents  q

 

As a result, " ( a ≥ c or b < c ), then ( b ≥ c ) ​" can be represented as " (  ​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

Re​​Finalized 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, 공리와 정의, 정리의  차이

http://blog.naver.com/PostView.nhn?blogId=young040511&logNo=220492536490&parentCategoryNo=&categoryNo=&viewDate=&isShowPopularPosts=false&from=postView

 

2) 공리

: 증명 없이 참으로 받아들이는 명제

 

예시 :

1. 임의의 점에서 임의의 점으로 직선을 그을 있다.

2. 유한인 직선( 애매함 선분이라고 생각하시는게좋음) 연장할 있다.

3. 임의의 중심과 거리를 가지고 원을 가지고 원을 그릴 있다.

4. 모든 직각은 서로 같다.

5. 직선 밖의 점을 지나 직선에 평행하는 직선은 오직 하나뿐이다.

위와 같은 유클리드기하의 5 공리가 예시이다.

 

 

1) 정의

  : 수학용어나 기호에 대하여 의미를 규정한 .

 

예시 : 직각삼각형 : 내각의 크기가 직각인 삼각형을 직각삼각형이라 한다.

정삼각형 : 변의 길이가 같은 삼각형을 정삼각형이라 한다.

3) 정리

수학적으로 증명된 참인 명제

 

예시 :피타고라스의 정리 (%5Ccombi%20%5E%7B%202%20%7D%7B%20a%20%7D%2B%5Ccombi%20%5E%7B%202%20%7D%7B%20b%20%7D%3D%5Ccombi%20%5E%7B%202%20%7D%7B%20c%20%7D%20 )

 

 

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. (!ab)^(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 Morgans Law )

            (¬pq ¬r ) ^(¬pq s         (Using equation 3.4 in chapter 2)

         (¬p ¬r )^(¬p  s)^(q ¬r )^(q  s) 

(Using  the 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 = {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 which is the set of integers upper bound for the set XBy 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 yx 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,
 yx for every 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

2018_09_29_133218.JPG 

 

 

Solution 

2018_09_30_111114.JPG

 

 

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 2124, 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 2124, 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 2124, 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 2124, 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), mt (indexed from 1 to n), n

 

Output: (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+m1 and p1 · · · pm

while (ti+j1 == 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.

--------------------------------------------------------
= "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                      

                                                                 

Comment by Muhammad: Always try to do a step by step plugging in- don’t rush.

 

 

 

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 an(n × n matrices) and n


Output: true (if A = B ); false (if  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 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:

 

2018_10_08_141224.png

*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 PICB15D.gif By Repeated Squaring)

 

 This algorithm computes PICB16D.gif PICB16E.gif using repeated squaring.

      Input:  a, n, z

    Output:  PICB16D.gif PICB16E.gif 

    exp_mod_via_repeated_squaring(a, n, z) http://matrix.skku.ac.kr/2018-DM/Ch-5/PICB1A6.gif

       result http://matrix.skku.ac.kr/2018-DM/Ch-5/PICB1A7.gif

       PICB1B8.gifPICB16E.gif

       while (PICB1CA.gif)http://matrix.skku.ac.kr/2018-DM/Ch-5/PICB1CB.gif

          if(PICB1CC.gif PICB1DC.gif)

          PICB1DD.gif*PICB1EE.gif PICB1EF.gif

          PICB1F0.gif*PICB200.gif PICB201.gif

          PICB202.gif

      PICB213.gif

     return result

   PICB214.gif

* 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(http://matrix.skku.ac.kr/2018-DM/Ch-5/PICB1CC.gif PICB1DC.gif)                           //If condition doesn't execute since 30 mod 2 !=1   

          PICB1DD.gif*PICB1EE.gif PICB1EF.gif

          x=6*6 mod 11 = 3 

          n=15 

 

-----------------------while Loop 2nd iteration-------------

 

while(n>0)                               //While-loop executes since n=15>0

{

 If (PICB1CC.gif PICB1DC.gif)                   //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    (PICB1CC.gif PICB1DC.gif)                 //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  (PICB1CC.gif PICB1DC.gif)        //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 (PICB1CC.gif PICB1DC.gif)           //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 2= 16.  

 

Answer 

 

2= 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 (133) = 286 (one suit)

2.    C (133) = 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 http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC8300.gif containing http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC8301.gif (distinct) elements,

 (a) An http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC8312.gif-combination of http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC8313.gif is an unordered selection of http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC8314.gif-elements of http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC8325.gif(i.e. an http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC8326.gif -element subset of http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC8327.gif).

 (b) The number of http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC8337.gif-combination of a set of http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC8338.gif distinct elements is http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC8339.gif or http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC834A.gif.

http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC834B.gif

 

 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 1013, 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 sn1, 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.

Fina​lized b​y 칭기즈​ 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 anwhich 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 + a= 2 + 3 = 5
     n = 
3     ->   a3 = 3 + a3-1 = 3 + a2 = 3 + 5 = 8
     n = 
4     ->   a4 = 4 + a4-1 = 4 + a= 4 + 8 = 12

Answer:                                                                                 ​​

(a) The first for terms of the sequence.      

a1​ = 3,  a2​ = 5,  a3​ = 8 ,  a​= 12

(b) Initial condition for the sequence.     

a​= 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

그림입니다.
원본 그림의 이름: CLP000022e80002.bmp
원본 그림의 크기: 가로 806pixel, 세로 107pixel

 

Solution

1.    Let a0 be the initial amount invested  
   -->  
a0=4000

2.    After 1 year, a1 will be  
    -->  a
1 = a+ 0.17 a= 1.17 a0

3.    After 2 years, a2 will be
    -->  a
2 = a+ 0.17 a​​1.17 a1 = (1.17)a0

4.    Thus, after n years, an will be   
    -->  a
n = an-1 + 0.17 an-1 = (1.17) an-1 = ... = (1.17)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). Thats why the relation/equation provided by the original answer (an = (1.17)* 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

Fina​lized b​y 김영철 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

2018_11_09_161406.JPG

           

 

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)  P​k = ( ​n-2​n=0​   C(n-2,k)  P​k )*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

 

2018_11_09_162001.JPG

 

Solution

 

If the first domino is placed as shown, 

there are n-1 ways to cover the 2 x (n-1) board that remains. 

2018_11_09_162151.JPG

If the first two dominoes are placed as shown,

there are n-2 ways to cover the 2 x (n-2) board that remains. 

2018_11_09_162317.JPG  

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 = f 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 a= 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 = x2an-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:

a= 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. a​n= 3a​n-1+ 10a​n-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 = x2an-1 = x, an-2 =1) as following:

x​2​=3x+10 

x​2​-3x-10=0 

(x-5)(x+2)=0 

X=5   x=-2

There are 2 roots so​

 a​n​=a*(5n​)+b*(-2​n​)

* Our next step is to find the coefficients(a,b) using:

a0=4

a1=13

 

*For n=0 : a​0​=a*(5​0​)+b*(-2​0​)=2 =a+b=4

*For n=1: a​1​=2*(5​1​)+b*(-2​1)=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, 

a​n​=3*(5n​)+1*(-2​n​)

Answer:

a​n​=3*(5n​)+1*(-2​n​)                                           

 

​​ 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.

2018_11_14_215640.PNG


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 C​n-1  

 

(b) An n-length​s 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, C​n-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 3​n-1​​C​n-1     

 

Thus, 

C​n​=​ Cn-1​​+Cn-1​​+3​n-1​​-Cn-1​ = 3​n-1​​+Cn-1

Initial condition : C​1​=2 

C​n =​  3​n-1​​+Cn-1​​ = ​3​1​​​+​3​2​​+3​3  ​+ + 3​n-1​​+ C1 =2+(3​n​-3)/(3-1) =(3​n​+1)/2

 

Answer:

A recurrence relation and initial condition : C​n = 3​n-1​​ + Cn-1

Initial condition : C​1=2

Solution :  C​n​ ​= (3​n​+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.

 2018_11_17_113257.png 

 

Definition:

---------------------------------------------------------------------

Definition  6.1

그림입니다.
원본 그림의 이름: CLP00000d6c000e.bmp
원본 그림의 크기: 가로 807pixel, 세로 139pixel

---------------------------------------------------------------------

Proof

The adjacency matrix of graph G1​​ relative to vertex ordering v1, v2, v3v4, v5, v6 

2018_11_17_114121.gif

is equal to the adjacency matrix of graph G2 relative to the vertex ordering w1, w2​​, w3​​, w4, w5, w6​​

2018_11_17_114121.gif

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,Wmake 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

  

2018_11_17_160000.jpg 

 

 

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.

 

 2018_11_17_102016.png   

 

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)

2018_11_26_033409.PNG 

 

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

2018_11_17_154911.jpg

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:

http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_11_17_205144.PNG

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

 

2018_11_17_155304.jpg

 

Proof

0. In a planar graph, each edges belongs to at most two bounding cycles. Therefore, 2e  4f .


1. Euler
s formula is ve+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 n3(n-4)2n-1 +4 0 is true.

6. But n>3, (n-4)2n-1  (n-4)2n-1 +4> 0 .

 The n-cube is planar if n3 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: 

2018_11_17_192911.PNG
(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:

 

2018_11_17_144054.png  

 

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

2018_11_17_144054.png​​

Definition:

-----------------------------------------------------------------------------

 Definition 2.8

 그림입니다.
원본 그림의 이름: CLP00001fd00001.bmp
원본 그림의 크기: 가로 801pixel, 세로 105pixel

 ---------------------------------------------------------------------------

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) 

 

2018_11_17_173112.JPG

 

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

2018_11_17_144054.png

8 Graphs of Exercise 31.

Subgraphs:

2018_11_17_173112.JPG​​

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.

 


 

Part VI. Collection of Sol for Ch 8. (1st version)

 

Here there are two parts:

A) QnA activity – Next Page

B) Team Project – Page 119

 

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

 

2018_11_16_212754.jpg
Answer:

We can see that we have to investigate the graph G made up of vertices of

subset V and subset E.

1. As v1v2v3v4   are vertices of subset V and  e1e2e3  are vertices of subset E,

    we can say that V={v1v2v3v4and E={e1e2e3}

2. Both e1e2  are edges that connect v2v. 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. 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

 

2018_11_16_211003.jpg 

 

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:

 2018_11_16_180851.png  

 

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 n1.

 

Solution

Step 1: When labeling n-cube, we can assign the vertices strings of length n from 00...0 to 111. (is determined by n-cubes n number.)

 

Step 2: Two subsets of the graph =(VE) 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 {10} or {01} starting in V1 and ending in V2 

2018_11_24_204216.png

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

 

2018_11_16_205350.png 

 

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 (v, 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

 

 

http://www.icampus.ac.kr/repository/attachfiles/operation/notice/kyc0816/2018_11_17_145017.jpg 

 

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 (= 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)

 

2018_11_17_152143.jpg

 

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:

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 http://matrix.skku.ac.kr/2018-DM/Ch-8/PICAEB8.gif is connected if given any vertices http://matrix.skku.ac.kr/2018-DM/Ch-8/PICAEB9.gif and http://matrix.skku.ac.kr/2018-DM/Ch-8/PICAEC9.gif in http://matrix.skku.ac.kr/2018-DM/Ch-8/PICAECA.gif, there is a path from   http://matrix.skku.ac.kr/2018-DM/Ch-8/PICAEDB.gif to http://matrix.skku.ac.kr/2018-DM/Ch-8/PICAEDC.gif. 

--------------------------------------------------------------

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:

 2018_11_27_020646.PNG

 

 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

  

2018_11_17_124034.jpg
 

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.

2018_11_17_092923.png

 

Solution

The path igz 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.

2018_11_17_092923.png

 

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.

2018_11_17_092923.png

 

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 http://matrix.skku.ac.kr/2018-DM/Ch-8/PICBC79.gif and column http://matrix.skku.ac.kr/2018-DM/Ch-8/PICBC7A.gif is http://matrix.skku.ac.kr/2018-DM/Ch-8/PICBC8A.gif if http://matrix.skku.ac.kr/2018-DM/Ch-8/PICBC8B.gif is incident on http://matrix.skku.ac.kr/2018-DM/Ch-8/PICBC9C.gif and http://matrix.skku.ac.kr/2018-DM/Ch-8/PICBC9D.gif otherwise. Thus the incidence matrix for the graph of Figure 5.4.

PICBCAD.png     PICBCBE.gif

          Figure 5.4

 A column such as http://matrix.skku.ac.kr/2018-DM/Ch-8/PICBCEE.gif 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.

 2018_11_17_113257.png 

 

Definition:

---------------------------------------------------------------------

Definition  6.1

그림입니다.
원본 그림의 이름: CLP00000d6c000e.bmp
원본 그림의 크기: 가로 807pixel, 세로 139pixel

---------------------------------------------------------------------

Proof

The adjacency matrix of graph G1​​ relative to vertex ordering v1, v2, v3v4, v5, v6 

2018_11_17_114121.gif

is equal to the adjacency matrix of graph G2 relative to the vertex ordering w1, w2​​, w3​​, w4, w5, w6​​

2018_11_17_114121.gif

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,Wmake 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

  

2018_11_17_160000.jpg 

 

 

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.

 

 2018_11_17_102016.png    

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)

2018_11_26_033409.PNG 

 

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

2018_11_17_154911.jpg

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:

2018_11_17_205144.PNG

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

2018_11_17_155304.jpg

 

Proof

0. In a planar graph, each edges belongs to at most two bounding cycles. Therefore, 2e  4f .


1. Euler
s formula is ve+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 n3(n-4)2n-1 +4 0 is true.

6. But n>3, (n-4)2n-1  (n-4)2n-1 +4> 0 .

 

 The n-cube is planar if n3 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: 

2018_11_17_192911.PNG
(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:

 

2018_11_17_144054.png   

 

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.17Re-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

2018_11_17_144054.png​​

Definition:  Definition 2.8

 그림입니다.
원본 그림의 이름: CLP00001fd00001.bmp
원본 그림의 크기: 가로 801pixel, 세로 105pixel

 ---------------------------------------------------------------------------

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) 

 

2018_11_17_173112.JPG

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

2018_11_17_144054.png

8 Graphs of Exercise 31.

Subgraphs:

2018_11_17_173112.JPG​​

 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 ---------------------

 

* Comment after my Nov. PBL report

 

As far it goes for the academic part, I will certainly say that after studying chapter one to five am quite confident with my mathematical skills whether it is related to algorithms or proving. Of course, this kind of knowledge is one of the basics in Software Engineering which makes me happier for taking this course as it has a direct connection with my Major.

Moreover, as a foreigner I want to really appreciate this flipped class system offered by our Professor because it makes us feel more connected to other students and to the Professor himself. Furthermore, I am enthused to see more outcomes of this environment hoping it only gets better and by the end of this semester I hope we will have acquired many skills other than just academic ones. Once again thanks to everyone for making this experience way more effective.

Here I am dividing my feelings, notes and comments based on we did progress month wise:

 

·           September: I took this course as recommendation from my friend, but I didn’t really know what Discrete Mathematics was or what was a flipped class. It took me one full month to adjust but thankfully with professor’s guidance and other students’ activity I got motivated and started to learn from the overall experience.

 

·           October: I got fully immersed into the flipped class system and I started to really get the hang of being a part of such broad and valuable experience where I have to learn, teach and discuss at the same time.

 

 

·           November: This month has been the most active month so far as we were asked to handle a specific chapter and work as team which actually enlightened me with the team work spirit.

 

·           Expectations for December: The only thing I hope for is to walk out of this course with a lot DM knowledge in addition to a lot of flipped class handling skills.

 

 

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).