<span class="text_page_counter">Trang 1</span><div class="page_container" data-page="1">

BÁO CÁO CUỐI KỲ

MÔN CẤU TRÚC RỜI RẠC

Người hướng dẫn: TS NGUYỄN THỊ HUỲNH TRÂMNgười thực hiện: NGUYỄN VÕ CÔNG HUY

Lớp : 20050301Khoá : 24

THÀNH PHỐ HỒ CHÍ MINH, NĂM 2021

</div><span class="text_page_counter">Trang 2</span><div class="page_container" data-page="2">

BÁO CÁO CUỐI KỲ

MÔN CẤU TRÚC RỜI RẠC

Người hướng dẫn: TS NGUYỄN THỊ HUỲNH TRÂMNgười thực hiện: NGUYỄN VÕ CÔNG HUY

Lớp : 20050301Khoá : 24

THÀNH PHỐ HỒ CHÍ MINH, NĂM 2021

</div><span class="text_page_counter">Trang 3</span><div class="page_container" data-page="3">

LỜI CẢM ƠN

Em xin chân thành cảm ơn đến cô Nguyễn Thị Huỳnh Trâm, và đội ngũ giảngviên trường đại học Tơn Đức Thắng đã tận tình giảng dạy trong suốt đại dịch giúp emhoàn thành bài cáo này.

</div><span class="text_page_counter">Trang 4</span><div class="page_container" data-page="4">

CƠNG TRÌNH ĐƯỢC HỒN THÀNHTẠI TRƯỜNG ĐẠI HỌC TƠN ĐỨC THẮNG

Tơi xin cam đoan đây là cơng trình nghiên cứu của riêng tôi và được sự hướngdẫn khoa học của TS Nguyễn Thị Huỳnh Trâm;. Các nội dung nghiên cứu, kết quảtrong đề tài này là trung thực và chưa cơng bố dưới bất kỳ hình thức nào trước đây.Những số liệu trong các bảng biểu phục vụ cho việc phân tích, nhận xét, đánh giá đượcchính tác giả thu thập từ các nguồn khác nhau có ghi rõ trong phần tài liệu tham khảo.

Ngoài ra, trong luận văn còn sử dụng một số nhận xét, đánh giá cũng như số liệucủa các tác giả khác, cơ quan tổ chức khác đều có trích dẫn và chú thích nguồn gốc.

Nếu phát hiện có bất kỳ sự gian lận nào tơi xin hồn tồn chịu trách nhiệmvề nội dung luận văn của mình. Trường đại học Tơn Đức Thắng không liên quan đếnnhững vi phạm tác quyền, bản quyền do tơi gây ra trong q trình thực hiện (nếu có).

TP. Hồ Chí Minh, ngày 25 tháng 12 năm 2021 Tác giả

Nguyễn Võ Công Huy

</div><span class="text_page_counter">Trang 5</span><div class="page_container" data-page="5">

TÓM TẮT

Bài báo cáo bao gồm các nội dung cốt lõi, chung nhất của môn Cấu Trúc RờiRạc, giúp nắm vững nền móng các hướng tư duy thuần cơ bản nhằm giúp sinh viên ghinhớ và hiểu sâu hơn về bộ môn này.

</div><span class="text_page_counter">Trang 6</span><div class="page_container" data-page="6">

Question 1 – Euclid’s algorithm and Bezout’s identity...4

Question 2 – Recurrence relation...5

Question 3 – Set...7

Question 4 – Relations...8

Question 5 – Multiplicative inversion...9

Question 6 – Kruskal’s algorithm...11

Question 7 – Eulerian circuit...15

Question 8 – Map coloring...18

TÀI LIỆU THAM KHẢO...25

PHỤ LỤC...26

</div><span class="text_page_counter">Trang 7</span><div class="page_container" data-page="7">

DANH MỤC KÍ HIỆU VÀ CHỮ VIẾT TẮT

CÁC KÝ HIỆU

CÁC CHỮ VIẾT TẮT

</div><span class="text_page_counter">Trang 8</span><div class="page_container" data-page="8">

DANH MỤC CÁC BẢNG BIỂU, HÌNH VẼ, ĐỒ THỊ

DANH MỤC HÌNH

DANH MỤC BẢNG

</div><span class="text_page_counter">Trang 9</span><div class="page_container" data-page="9">

Question 1: Euclid’s algorithm and Bezout’s identity

a. Using Euclid’s algorithm to calculate gcd(2021, 1000 + m) and lcm(2021, 1000 +m), where m is the last 3 digits of your student ID.

SolveStudent ID : 52000765 m = 765

Let’s trace Euclid’s algorithm to calculate gcd(2021;1765) gcd(2021;1765)

2021 = 1765*1 + 256 gcd(1765;256)1765 = 256*6 + 229 gcd(256;229) 256 = 229*1 + 27 gcd(229;27) 229 = 27*8 + 13 gcd(27;13) 27 = 13*2 + 1 gcd(13;1) 13 = 1*13 + 0 gcd(1;0)Thus gcd(2021;1765) = 1gcd(a;b) * lcm(a;b) = a * b

lcm(a;b) = = = = 3567065

b. Apply above result(s) in to find 5 integer solution pairs (x,y) of this equation: 2021x + (1000 + m)y = gcd(2021; 1000 + m)

SolveStudent ID : 52000765 m = 765

Equation : 2021x + 1765y = gcd(2021; 1765)1 = 27 – 13*2 = 27 + 13*(–2)

</div><span class="text_page_counter">Trang 10</span><div class="page_container" data-page="10">

= 27 + (229 – 27*8)*(–2) = 229*(–2) + 27*17 = 229*(–2) + (256 – 229)*17

= 229*(–19) + 256*17 = (1765 – 256*6)*(-19) + (2021 – 1765)*17 = [1765 – (2021 – 1765)*6]*( –19) + (2021 – 1765)*17

= [2021*(–6) + 1765*7]*( –19) + (2021 – 1765)*17 = 2021*131 + 1765*(–150)

Thus 1 = 2021*131 + 1765*(–150)Due to the form of equation: ax + by = d, so

Once a solution pair (x, y) is found, additional pairs may be generated by , where k is any integer.

Proof steck:

1 = 2021*131 + 1765*(–150)

k = 1 => = (1896; –2171)k = 19 => = (35431; –40570)k = 11 => = (54846; –62801)k = 2 => = (58376; –66843)k = 2002 => = (3591906; –4112885)

Question 2: Recurrence relation

Solve the recurrence relation

a<small>n</small> = 8a – 15a<small>n−1n−2 </small>

with a0 = 5 and a1 = m, where m is the last 2 digits of your student ID.Solve

Student ID : 520007 m = 65 65

</div><span class="text_page_counter">Trang 11</span><div class="page_container" data-page="11">

Suppose a sequence a , a , a ,… satisfies the recurrence relation<small>012</small>

a<small>n</small> = 8a – 15a<small>n−1n−2</small> for every integer n 2,with initial conditions

a<small>0 </small>= 5 and a = m = 65.<small>1 </small>

This sequence sitisfies part of the hypothesis of the single-root theorem becauseit satisfies a second-order linear homogeneous recurrence relation with constantcoefficients(A = 8 and B = –15). To check that it satisfies the second part of thehypothesis, examine the characteristic equation.

t<small>2</small> – 8t + 15 = 0

By the quadratic formula t = 5, t = 3 [since t<small>2</small> – 8t + 15 = (t – 5)*(t – 3)] and so theroots are distinct. Thus it follows from the distinct-roots theorem that the sequence isgiven by the explicit formula.

a<small>n</small> = C*5 + D*3<small>nn</small> for each integer n 0

Where C and D are the numbers whose values are determined by the fact that a = 5; <small>0 </small>

a<small>1</small> = 65. To find C and D, write a = 5 = C + D and a = 65 = 5*C + 3*D<small>01 </small>

Now substitute C = 25 and D = 20 into formula to conclude that –a<small>n</small> = 5<small>2 + n</small> – 20*3<small>n</small> for each integer n 0

Question 3: Set

a. Create a set Γ of characters from your case-insensitive non-diacritical full name. For example, the set corresponding with “Tôn Đức Thắng” is Δ = {A, C, D, G, H, N, O, T, U}.

SolveMy full name: “Nguyễn Võ Công Huy”

</div><span class="text_page_counter">Trang 12</span><div class="page_container" data-page="12">

Γ = {C, E, G, H, N, O, U, V, Y}

b. Find the union, intersect, non-symmetric difference, and symmetric difference of Γ and Δ, where Γ and Δ are from question 3a.

SolveRewrite : Γ = {C, E, G, H, N, O, U, V, Y}and Δ = {A, C, D, G, H, N, O, T, U}The union:

Γ ∪ Δ = {x U| x Γ ∈ ∈ ꓦ x Δ }∈

=> Γ Δ = {A, C, D, E, G, H, N, O, T, U, V, Y}The intersect:

Γ ∩ Δ = {x U| x Γ ∈ ∈ ꓦ x Δ }∈ => Γ Δ = {C, G, H, N, O, U}The non-symmetric difference:

Δ \ Γ = {x U| x Δ ∈ ∈ ꓦ x Γ }∉ => Δ \ Γ = {E, V, Y}

The symmetric difference:

Γ ⊖ Δ = {x U| x Δ x Γ }∈ ∉ ⊕ ∉ => Γ Δ = {A, E, D, T, V, Y}⊖

</div><span class="text_page_counter">Trang 13</span><div class="page_container" data-page="13">

Question 4: Relations

Let be a binary relation defined on 2 integers as follow: ℜ∀∀ , � ∈ N (aRb↔� |(�.�))where m is the last 2 digits of your student ID.

Is R reflexive, symetric, anti-symetric, transitive? Prove your answer.Solve

By definition of R, this means that

For every a N , 65|(a.a),∈

which is false because a.a = a and a N such that 65 a . As a counterexample, let a<small>2</small>

∃ ∈ ∤ <small>2</small>

= 4 a = 16 and 65<small>2</small> .∤16Hence R is not reflexive.

R is symmetric: To show that R is symmetric, it is necessary to show that For every a N, if aRb then bRa∈

By definition of R, this means that

For every a N, if 65|(a.b) then 65|(b.a)∈

which is true because a.b = b.a by the commutative law of multiplication F1(A-1 Epp)Hence R is symmetric.

</div><span class="text_page_counter">Trang 14</span><div class="page_container" data-page="14">

R is not anti-symmetric: To show that R is anti-symmetric, it is necessary to show that For every a N, if aRb and bRa then b = a∈

By definition of R, this means that

For every a N, if 65|(a.b) and 65|(b.a) then b = a∈

which is false because 65|(a.b) and 65|(b.a) but a and b can be different. As acounterexample, a = 1 and b = 65 then 65|(a.b) and 65|(b.a) but 1 ≠ 65.

Hence R is not anti-symmetric.

R is not transitive: To show that R is transitive, it is necessary to show thatFor every a ,b, c N, if a R b and b R c then a R c∈By definition of R, this means that:

For every a,b,c N, if 65|(a + b) and 65|(b+ c) then 65|(a + c).∈

which is false because a = 42, b = 23, c = 107 then 2|(a + b) and 2|(b+ c) but 65 (a + c).∤Hence R is not transitive.

Question 5: Multiplicative invertion

a. Study and present your knowledge about Extended Euclidean algorithm to compute multiplicative inverses in modular structures.

The version of the Euclidean algorithm described above (and by Euclid) can take many subtraction steps to find the GCD when one of the given numbers is much bigger than the other. A more efficient version of the algorithm shortcuts these steps, instead replacing the larger of the two numbers by its remainder when divided by the smaller of the two (with this version, the algorithm stops when reaching a zero remainder). With this improvement, the algorithm never requires more steps than five times the number of digits (base 10) of the smaller integer.

</div><span class="text_page_counter">Trang 15</span><div class="page_container" data-page="15">

b. Apply the algorithm to find (m+1) (mod 101) where m is the last 2 digits of your<small>-1</small>

student ID.

SolveStudentID : 52000765 m = 66

(m+1) (mod 101) = 66 (mod 101)<small>–1-1</small>

Let’s trace Euclid’s algorithm to calculate gcd(66,101)101 = 66 + 35

66 = 35 + 31 35 = 31 + 4 31 = 4*7 + 3 4 = 1*3 + 1Thus gcd(66,101) = 1 1 = 4 – 1.3 = 4*8 – 31 = 8*35 – 9*31

= 8*(101 – 66) – 9*(66 – 35) = 8*(101 – 66) – 9*[66 – (101 – 66)] = –26*16 + 17*101

Thus 1 = (-26)*66 + 17*1011 = (-26)*66 + 17*101(mod 101)=> 1 ≡ (-26)*66 (mod 101)

66<small>-1 </small> = -26 mod 101 = (-26 + 101) mod 101 = 75 mod 101

</div><span class="text_page_counter">Trang 16</span><div class="page_container" data-page="16">

Question 6: Kruskal’s Algorithm

Propose a solution for circuit-checking in Kruskal's algorithm.Solve

This is a graph example to find a solution for circuit-checking in Kruskal’s algorithm as follow:

</div><span class="text_page_counter">Trang 17</span><div class="page_container" data-page="17">

Step 1: Remove all loops and ParallelEdges (*Note: In case of parallel edges, keep theone which has the least cost associated and remove all others).

Step 2: Create a set of edges and weight, and arrange them in an ascending order ofweightage (cost).

B,D D,T A,C C,D C,B B,T A,B S,A S,C

Step 3: Add the edge which has the least weightage.

Now we start adding edges to the graph. The least cost is 2 and edges involved are B,Dand D,T. We add them. Adding them does not violate spanning tree properties, so wecontinue to our next edge selection.

</div><span class="text_page_counter">Trang 18</span><div class="page_container" data-page="18">

Next cost is 3, and associated edges are A,C and C,D. We add them again

</div><span class="text_page_counter">Trang 19</span><div class="page_container" data-page="19">

Next cost in the table is 4, and we observe that adding it will create a circuit in thegraph. So we ignore it. In the process we shall avoid all edges that create a circuit.

We observe that edges with cost 5 and 6 also create circuits. We ignore them and moveon. Now we are left with only one node to be added. Between the two least cost edgesavailable 7 and 8, we shall add the edge with cost 7. By add edge S,A we haveminimumcos spanning tree.

</div><span class="text_page_counter">Trang 20</span><div class="page_container" data-page="20">

Question 7: Eulerian circuit

a. Does the following graph have an Eulerian circuit or Eulerian path? Why?

The graph have Eulerian circuit the graph have an Eulerian path that starts and ends onthe same vertex (this thing is proven in c) and a necessary conditional for the existenceof Eulerian circuit is that all vertives in the graph have an even degree, and statedwithout proof that connected graphs with all vertives of even degree have an Euleriancircuit. The first complete proof of this latter claim was published posthumously in1873 by Carl Hierholzer.

Thus, the graph don’t have Eulerian path.

</div><span class="text_page_counter">Trang 21</span><div class="page_container" data-page="21">

b. Study and present your knowledge about Hierholzer’s algorithm to find an Eulerian circuit.

We start with a random node and then follows an arbitrary unvisited edge to a neighbour. This step is repeated until one returns to the starting node. This yields a firstcircle in the graph. If this circle covers all nodes it is an Eulerian cycle and the algorithm is finished.

Otherwise, one chooses another node among the cycles' nodes with unvisited edges and constructs another circle, called subtour. By choice of edges in the construction the new circle does not contain any edge of the first circle, both are disjunct. However, both circles must intersect in at least one node by choice of the starting node of the second circle. Therefore one can represent both circles as one new circle. To do so, one iterates the nodes of the first circle and replaces the subtour's starting node by the complete node sequence of the subtour. Thus, one inegrates additional circles into the first circle. If the extended cycle does include all edges the algorithm is finished. Otherwise, we can find another cycle to include.

In the case of an undirected, semi-Eulerian graph the algorithm starts with one of the two nodes with odd degree. In the directed case with the node with one additional outgoing edge. One of the subtours to be found will then not form a cycle, instead it will also be a path. When integrating this "subtour" into the circle one has to make surethat start and end node of this path also form start and end of the complete Eulerian path.

</div><span class="text_page_counter">Trang 22</span><div class="page_container" data-page="22">

c. If the graph has an Eulerian circuit, use Hierholzer's algorithm to find an Eulerian circuit of that graph when the initial circuit R1 is:

SolveStudent ID : 52000765 abcd % 4 = 1 R1 is abhga.The initial circuit R1: a b h g a

Circuit R2: a U V P Q L R F A L K A J K P O U T N O J I A E I N M E B M S B Y e B G e f k G D k l D m n D H

n i j C H j d c b V W Q R F C R X C d X W c i h m l g f Z Y S T Z a.Completed Eulerian circuit:

a b h g a U V P Q L R F A L K A J K P O U T N O J I A E I N M E B M S B Y e B G e f k G D k l D m

n D H n i j C H j d c b V W Q R F C R X C d X W c i h m l g f Z Y S T Z a.

</div><span class="text_page_counter">Trang 23</span><div class="page_container" data-page="23">

Question 8: Map Coloring

Give this map:

</div><span class="text_page_counter">Trang 24</span><div class="page_container" data-page="24">

a. Modeling this map by a graph.

</div><span class="text_page_counter">Trang 25</span><div class="page_container" data-page="25">

Step 1: Choose Orissa vertex and color it with Red.

</div><span class="text_page_counter">Trang 27</span><div class="page_container" data-page="27">

Detail: Look at the graph, we can see vertices like: West Bengal, Jharkhand,Chhattisgarh, Telangana, Andhra Prahdesh adjacent with Orissa so we can colour themsame color.

Repeat this thing and priority is given to vertices of higher degree. So we colorUttar Pradesh(9), Maharashtra(7), Assam(7) same colour with Orrisa, and we checkcontinue to the non-adjacent vertices, and we can colour vertices like: Laskshadweep,Andaman and Nicobar Islands, Tamil Nadu, Daman and Diu, Punjab and Sikkim samecolour with Orrisa

</div><span class="text_page_counter">Trang 28</span><div class="page_container" data-page="28">

Step 3: Choose a new color (Yellow, Blue, Green,…v.v), and repeat what we did inStep 2 for vertices not already colored.(The second color is Yellow, the third color isGreen and the final color is Blue).

</div><span class="text_page_counter">Trang 29</span><div class="page_container" data-page="29">

Step 4: Repeat Step 2 until all vertices are colored.

</div><span class="text_page_counter">Trang 30</span><div class="page_container" data-page="30">

All vertices is colored.

</div><span class="text_page_counter">Trang 31</span><div class="page_container" data-page="31">

TÀI LIỆU THAM KHẢO

Tiếng Việt

1. Đại học Tôn Đức Thắng – Tài liệu lý thuyết môn Cấu Trúc Rời Rạc.

2. Thien Hoang (tvhoang.com) – Thuật toán Euclid mở rộng, Nghịch đảo Modulo, và Định lý số dư Trung Quốc.

3. Chuong Le Hoang (wordpress.com) – Thuật toán Kruskal – Tìm cây bao trùmnhỏ nhất.

Tiếng Anh

4. GeeksforGeeks – Euclidean algorithms (Basic and Extended).

5. Javatpoint – Kruskal's Algorithm.

6. GeeksforGeeks – Eulerian path and circuit for undirected graph.

7. GeeksforGeeks – Hierholzer's Algorithm for directed graph.8. Dr Rhyd Lewis – Cardiff School of Mathematics, Cardiff University.9. Lewis, R. (2015) – A Guide to Graph Colouring: Algorithms and

Applications. Berlin, Springer.

</div><span class="text_page_counter">Trang 32</span><div class="page_container" data-page="32">

PHỤ LỤC

</div>