Giáo trình Toán rời rạc - Ngành/nghề: Lập trình máy tính

BỘ NÔNG NGHIỆP VÀ PHÁT TRIỂN NÔNG THÔN

TRƯỜNG CAO ĐẲNG NGHỀ CƠ GIỚI NINH BÌNH

GIÁO TRÌNH

MÔN HỌC: TOÁN RỜI RẠC

NGÀNH/NGHỀ: LẬP TRÌNH MÁY TÍNH

TRÌNH ĐỘ: CAO ĐẲNG

Ban hành kèm theo Quyết định số:

/QĐ-TCGNB ngày…….tháng…...năm

201.... của Trường cao đẳng nghề Cơ giới Ninh Bình

Ninh Bình, năm 2018

1

TUYÊN BỐ BẢN QUYỀN

Tài liệu này thuộc loại sách giáo trình nên các nguồn thông tin có thể được

phép dùng nguyên bản hoặc trích dùng cho các mục đích về đào tạo và tham

khảo.

Mọi mục đích khác mang tính lệch lạc hoặc sử dụng với mục đích kinh

doanh thiếu lành mạnh sẽ bị nghiêm cấm.

2

LỜI GIỚI THIỆU

Toán rời rạc là một lĩnh vực của toán học nghiên cứu các đối tượng rời

rạc, đặc biệt vai trò của Toán rời rạc trong lĩnh vực tin học. Khi phải đếm các

đối tượng rời rạc, khi nghiên cứu quan hệ giữa các đối tượng rời rạc và đặc biệt

là việc cất giữ và sử lý thông tin trên máy tính.

Cuốn sách nhằm giới thiệu các kiến thức cơ bản về: Lý thuyết tổ hợp, lý

thuyết đồ thị nhằm giúp các em ngành Lập trình có tài liệu tham khảo, đồng thời

cũng là tài liệu học tập cho các em.

Tài liệu này được biên soạn gồm 5 chương:

Chương 1. Trình bày các vấn đề của lý thuyết tổ hợp, soay quanh các bài

toán cơ bản: Bài toán đếm, bài toán tồn tại. Nội dung chương I không những

giúp nâng cao tư duy toán học mà còn làm quen với thuật toán để giải quyết các

bài toán trong thực tế.

Chương 2. Trình bày các kiến thức cơ bản về lý thuyết đồ thị. Chương này

cung cấp các kiến thức cơ bản về lý thuyết đồ thị, giúp người học có kiến thức

cơ sở để nghiên cứu về đồ thị trong các chương tiếp theo.

Chương 3. Biểu diễn đồ thị trên máy tính và các thuật toán tìm kiếm. Sau

khi người học đã tìm hiểu những kiến thức cơ bản về đồ thị thì tiến hành xây

dựng cấu trúc dữ liệu để biểu diễn đồ thị trên máy tính, đồng thời xây dựng các

thuật toán tìm kiếm đồ thị được tổ chức trên máy tính.

Chương 4. Trình bày các kiến thức về cây và cây khung của đồ thị, cách

xây dựng chu trình của đồ thị.

Chương 5. Giúp người học xây dựng đường đi, tìm đường đi ngắn nhất

trong đồ thị.

Mặc dù tác giả đã cố gắng rất nhiều nhưng tài liệu cũng không tránh khỏi

những thiếu sót. Tác giả rất mong nhận được ý kiến đóng góp của bạn đọc quan

tâm để tài liệu ngày càng hoàn thiện hơn.

Ninh Bình, ngày…..........tháng…...... năm 2018

Tham gia biên soạn

1. Nguyễn Văn Thái

2. Nguyễn Xuân Khôi

3. Vũ Ánh Dương

3

MỤC LỤC

TRANG

Lời giới thiệu.............................................................................................. 3

Chương 1. Lý thuyết tổ hợp ...................................................................... 6

1. Sơ lược về tổ hợp ................................................................................... 6

2. Bài toán đếm và phương pháp giải………… ........................................ 8

3. Bài toán tồn tại và phương pháp giải………....................................... 17

Chương 2. Các khái niệm cơ bản của lý thuyết đồ thị.............................. 20

1. Định nghĩa đồ thị................................................................................... 20

2. Các thuật ngữ cơ bản............................................................................. 20

3. Đường đi, chu trình đồ thị liên thông.................................................... 21

Chương 3. Biểu diễn đồ thị và các thuật toán tìm kiếm ........................... 25

1. Ma trận kề, ma trận trọng số ................................................................. 25

2. Danh sách cạnh, danh sách liên kết ...................................................... 26

3. Tìm kiếm theo chiều rộng và chiều sâu ................................................ 27

4. Một số ứng dụng ................................................................................... 30

5. Bài tập ................................................................................................... 33

Chương 4. Cây và cây khung của đồ thị................................................... 34

1. Cây và các tính chất của cây................................................................. 34

2. Cây khung nhỏ nhất .............................................................................. 37

3. Đồ thị Euler và đồ thị Hamilton............................................................ 40

4. Bài tập ................................................................................................... 44

Chương 5. Đường đi ngắn nhất................................................................. 46

1. Các khái niệm mở đầu........................................................................... 46

2. Thuật toán Dijkstra................................................................................ 47

3. Thuật toán Floy ..................................................................................... 49

4. Bài tập ................................................................................................... 50

4

GIÁO TRÌNH MÔN HỌC

Tên môn học: Toán rời rạc

Mã môn học: MH12

Vị trí, tính chất, ý nghĩa và vai trò của môn học/mô đun:

- Vị trí: Đây là môn học bắt buộc giúp người học có kiến thức để học các

môn về lập trình và các môn có tính logic.

- Tính chất: Môn học này là môn học dựa trên nền tảng toán học và kiến

thức về lập trình căn bản.

- Ý nghĩa và vai trò của môn học/mô đun:

Toán rời rạc là nền tảng của thuật toán và nhiều mô hình quan trọng trong

máy tính (Logic, đại số bool, lý thuyết đồ thị, xác suất, tổ hợp…). Nó là cái nền

toán học quan trọng của máy tính.

Mục tiêu của môn học:

- Về kiến thức:

Vận dụng các kiến thức đã sinh viên viên xây dựng các thuật toán tính : tổ

hợp, hoán vị, giải hệ phương trình, phương trình, tính tích phân.

- Về kỹ năng:

+ Sử dụng các kiến thức đã sinh viên viên xây dựng thuật toán quay lại, các

bài toán tối ưu, bài toán tồn tại;

+ Là nền tảng để sinh viên học môn cấu trúc dữ liệu và giải thuật, cài đặt

các thuật toán trong tin học.

- Về năng lực tự chủ và trách nhiệm:

Có khả năng tổ chức, thực hiện các nhiệm vụ và chịu trách nhiệm đối với

kết quả công việc của mình.

Nội dung môn học:

5

CHƯƠNG 1: LÝ THUYẾT TỔ HỢP

Mã chương: Mh12.1

Giới thiệu:

Trình bày các vấn đề của lý thuyết tổ hợp, soay quanh các bài toán cơ bản:

Bài toán đếm, bài toán tồn tại.

Mục tiêu:

- Trình bày được các khái niệm của tổ hợp;

- Thực hiện được các bài toán về lý thuyết tổ hợp;

- Nghiêm túc trong học tập, đảm bảo an toàn cho người và trang thiết bị.

Nội dung chính:

1. S¬ l îc vÒ tæ hîp

Tæ hîp nh lµ mét lÜnh vùc cña to¸n häc rêi r¹c, xuÊt hiÖn vµo ®Çu thÕ kû

17. HiÖn nay lý thuyÕt tæ hîp ® îc ¸p dông trong nhiÒu lÜnh vùc kh¸c nhau: lý

thuyÕt sè, h×nh häc, thèng kª x¸c suÊt, …

1.1. ChØnh hîp lÆp

§Þnh nghÜa: Mét chØnh hîp lÆp chËp k cña n phÇn tö lµ mét bé cã thø tù

gåm cã k thµnh phÇn, mçi thµnh phÇn lÊy tõ tËp n phÇn tö ®· cho tr íc vµ cã thÓ

A^k n^k

trïng nhau. K/h:

n

VÝ dô: TÝnh sè d·y nhÞ ph©n ®é dµi 3

Gi¶i: Mçi d·y nhÞ ph©n ®é dµi 3 lµ mét bé gåm 3 thµnh phÇn (mçi thµnh

phÇn chØ nhËn mét trong hai gi¸ trÞ 0 hoÆc 1)  Sè x©u nhÞ ph©n ®é dµi 3 lµ 2³

Suy réng: sè d·y nhÞ ph©n cã ®é dµi n lµ 2ⁿ

1.2. ChØnh hîp kh«ng lÆp

Mét chØnh hîp kh«ng lÆp chËp k cña n phÇn tö lµ mét bé cã thø tù gåm k

phÇn tö, mçi phÇn tö lÊy tõ tËp n phÇn tö cho tr íc vµ kh«ng trïng nhau

n!

P^k

k/h:

n

(n  k)!

1.3. Tæ hîp

§Þnh nghÜa: Mét tæ hîp chËp k cña n phÇn tö (k n) lµ tËp hîp k phÇn tö



n!

C^k

chän tõ tËp n phÇn tö cho tr íc. k/h :

n

k!(n  k)!

Chøng minh: XÐt tËp c¸c chØnh hîp kh«ng lÆp chËp k cña n phÇn tö, tËp

n!

(n  k)!

nµy cã

phÇn tö vµ chia thµnh c¸c líp. Mµ mçi líp gåm c¸c bé cã thø tù

6

n!

k!(n  k)!

kh¸c nhau  sè phÇn tö trong mçi líp lµ k!



sè líp b»ng

còng

chÝnh lµ tæ hîp.

_{TÝnh chÊt: -}C_n^kC_n^nk

_-C_n^k C_n^k_^₁¹C_n^k_1

* C¸c sè tæ hîp cã quan hÖ víi biÓu thøc khai triÓn nhÞ thøc Newton

n

(x  y)ⁿ C⁰xⁿ C¹x^n1y¹ C²x^n2y²... C^n1x¹y^n1 Cⁿyⁿ Cⁱx^niyⁱ



n

i0

3

10

_{VÝ dô: TÝnh hÖ sè khai triÓn cña x y cña (x+y) lµ:}C  C⁷

3

7

10

1.4. Ho¸n vÞ lÆp

VÝ dô: Cho ch÷ ACCESS Hái cã bao c¸ch s¾p xÕp tÊt c¶ c¸c ch÷ c¸i thµnh

c¸c ch÷ kh¸c nhau?

Gi¶i: Ch÷ ACCESS gßm cã 6 ch÷ ® îc ®¸nh thø tù nh sau:

A C C E S S

1 2 3 4 5 6

C¹

- Ta thÊy trong chuçi ACCESS, cã 1 ch÷ A  cã

mét trong 6 vÞ trÝ

- Ta thÊy trong chuçi ACCESS, cã 2 ch÷ C  cã

vÞ trÝ cßn l¹i

- Ta thÊy trong chuçi ACCESS, cã 1 ch÷ E  cã

vÞ trÝ cßn l¹i

- Cuèi cïng cßn l¹i 2 ch÷ S ®Æt vµo 2 vÞ trÝ cßn l¹i  cã

vµo vÞ trÝ

c¸ch ®Æt ch÷ A vµo

6

C²

c¸ch ®Æt ch÷ C vµo 5

c¸ch ®Æt ch÷ A vµo 3

C²

5

C¹

3

c¸ch ®Æt ch÷ S

2

_{Nh• vËy: Cã}C¹.C².C¹.C²

₂=180 c¸ch

6

5

3

Tæng qu¸t:

n sè phÇntö lo¹i1





1

n₂sè phÇntö lo¹i2



n sè phÇntö lo¹i3 víi n  n  n ... n  n

Cho n phÇn tö trong ®ã cã:





3

1

2

3

m





n sè phÇntö lo¹i m



m



7

n!

n!.n₂!.....n_m!

n

n₂

n_m

Sè ho¸n vÞ lÆp = C_n.C_nn.....C_{(nn ...n )}

1



1

m

1

1.5. Tæ hîp lÆp

Tæng qu¸t: CÇn lÊy ra k vËt tõ tËp n lo¹i (phÇn tö)

_{ Sè c¸ch lÊy=}C_n^k_1k

_{VÝ dô: Cho ph ¬ng tr×nh}x₁ x₂ x₃10_{®Õm sè nghiÖm nguyªn cña}

ph ¬ng tr×nh.

Gi¶i:

Ta cã: víi mçi c¸ch lÊy nghiÖm øng víi viÖc lÊy ra x₁phÇn tö lo¹i 1;

x₂phÇn tö lo¹i 2;

x₃phÇn tö lo¹i 3;

12!

10

10(31)

Sè lÇn chän lµ 10  Sè c¸ch lÊy:

C



 66

10!.2!

2. Bµi to¸n ®Õm vµ ph ¬ng ph¸p gi¶i

2.1. Nguyªn lý céng

Quy t¾c céng: Gi¶ sö cã A c«ng viÖc A₁, A₂, ..., A_k. C¸c viÖc nµy cã thÓ lµm

t ¬ng øng b»ng n₁, n₂, ..., n_kc¸ch vµ gi¶ sö kh«ng cã hai viÖc nµo cã thÓ lµm

®ång thêi. Khi ®ã sè c¸ch lµm mét trong k viÖc ®ã lµ n₁+n₂+ ... + n_k.

VÝ dô:

1. Mét sinh viªn cã thÓ chän bµi thùc hµnh m¸y tÝnh tõ mét trong ba danh

s¸ch t ¬ng øng cã 23, 15 vµ 19 bµi. V× vËy, theo quy t¾c céng cã 23 + 15 + 19 =

57 c¸ch chän bµi thùc hµnh.

2. Gi¸ trÞ cña biÕn m b»ng bao nhiªu sau khi ®o¹n ch ¬ng tr×nh sau ® îc

thùc hiÖn?

m := 0

for i₁:= 1 to n₁

m := m+1

for i₂:=1 to n₂

m := m+1

...

for i_k:= 1 to n_k

m := m+1

8

Gi¸ trÞ khëi t¹o cña m b»ng 0. Khèi lÖnh nµy gåm k vßng lÆp kh¸c nhau.

Sau mçi b íc lÆp cña tõng vßng lÆp gi¸ trÞ cña k ® îc t¨ng lªn mét ®¬n vÞ. Gäi

T_ilµ viÖc thi hµnh vßng lÆp thø i. Cã thÓ lµm T_ib»ng n_ic¸ch v× vßng lÆp thø i cã

n_ib íc lÆp. Do c¸c vßng lÆp kh«ng thÓ thùc hiÖn ®ång thêi nªn theo quy t¾c

céng, gi¸ trÞ cuèi cïng cña m b»ng sè c¸ch thùc hiÖn mét trong sè c¸c nhiÖm vô

T_i, tøc lµ m = n₁+n₂+ ... + n_k.

Quy t¾c céng cã thÓ ph¸t biÓu d íi d¹ng cña ng«n ng÷ tËp hîp nh sau:

NÕu A₁, A₂, ..., A_klµ c¸c tËp hîp ®«i mét rêi nhau, khi ®ã sè phÇn tö cña hîp c¸c

tËp hîp nµy b»ng tæng sè c¸c phÇn tö cña c¸c tËp thµnh phÇn. Gi¶ sö T_ilµ viÖc

chän mét phÇn tö tõ tËp A_ivíi i =1,2, ..., k. Cã |A_i| c¸ch lµm T_ivµ kh«ng cã hai

viÖc nµo cã thÓ ® îc lµm cïng mét lóc. Sè c¸ch chän mét phÇn tö cña hîp c¸c

tËp hîp nµy, mét mÆt b»ng sè phÇn tö cña nã, mÆt kh¸c theo quy t¾c céng nã

b»ng | A₁|+|A₂|+ ... +|A_k|. Do ®ã ta cã:

|A₁ A₂... A_k| = |A₁| + |A₂| + ... + |A_k|.







Tæng qu¸t: Cho hai tËp A, B X vµ A B =  khi ®ã N(A B) = N(A) + N(B)

2.2. Nguyªn lý nh©n

2.2.1 Nguyªn lý: Gi¶ sö mét nhiÖm vô T nµo ®ã ® îc t¸ch ra thµnh k viÖc

T₁, T₂, ..., T_k. NÕu viÖc T_icã thÓ lµm b»ng n_ic¸ch sau khi c¸c viÖc T₁, T₂, ... T_i-1

®· ® îc lµm, khi ®ã cã n₁.n₂....n_kc¸ch thi hµnh nhiÖm vô ®· cho.

2.2.2. VÝ dô:

2.2.2.1. Ng êi ta cã thÓ ghi nh·n cho nh÷ng chiÕc ghÕ trong mét gi¶ng

® êng b»ng mét ch÷ c¸i vµ mét sè nguyªn d ¬ng kh«ng v ît qu¸ 100. B»ng

c¸ch nh vËy, nhiÒu nhÊt cã bao nhiªu chiÕc ghÕ cã thÓ ® îc ghi nh·n kh¸c

nhau?

Thñ tôc ghi nh·n cho mét chiÕc ghÕ gåm hai viÖc, g¸n mét trong 26 ch÷ c¸i

vµ sau ®ã g¸n mét trong 100 sè nguyªn d ¬ng. Quy t¾c nh©n chØ ra r»ng cã

26.100=2600 c¸ch kh¸c nhau ®Ó g¸n nh·n cho mét chiÕc ghÕ. Nh vËy nhiÒu

nhÊt ta cã thÓ g¸n nh·n cho 2600 chiÕc ghÕ.

2.2.2.2. Cã bao nhiªu x©u nhÞ ph©n cã ®é dµi n.

Mçi mét trong n bit cña x©u nhÞ ph©n cã thÓ chän b»ng hai c¸ch v× mçi bit

hoÆc b»ng 0 hoÆc b»ng 1. Bëi vËy theo quy t¾c nh©n cã tæng céng 2ⁿx©u nhÞ

ph©n kh¸c nhau cã ®é dµi b»ng n.

2.2.2.3. Cã thÓ t¹o ® îc bao nhiªu ¸nh x¹ tõ tËp A cã m phÇn tö vµo tËp B

cã n phÇn tö?

9

Theo ®Þnh nghÜa, mét ¸nh x¹ x¸c ®Þnh trªn A cã gi¸ trÞ trªn B lµ mét phÐp

t ¬ng øng mçi phÇn tö cña A víi mét phÇn tö nµo ®ã cña B. Râ rµng sau khi ®·

chän ® îc ¶nh cña i - 1 phÇn tö ®Çu, ®Ó chän ¶nh cña phÇn tö thø i cña A ta cã n

c¸ch. V× vËy theo quy t¾c nh©n, ta cã n.n...n =n^m¸nh x¹ x¸c ®Þnh trªn A nhËn gi¸

trÞ trªn B.

2.2.2.4. Cã bao nhiªu ®¬n ¸nh x¸c ®Þnh trªn tËp A cã m phÇn tö vµ nhËn gi¸

trÞ trªn tËp B cã n phÇn tö?

NÕu m > n th× víi mäi ¸nh x¹, Ýt nhÊt cã hai phÇn tö cña A cã cïng mét

¶nh, ®iÒu ®ã cã nghÜa lµ kh«ng cã ®¬n ¸nh tõ A ®Õn B. B©y giê gi¶ sö m  n vµ

gäi c¸c phÇn tö cña A lµ a₁,a₂,...,a_m. Râ rµng cã n c¸ch chän ¶nh cho phÇn tö a₁.

V× ¸nh x¹ lµ ®¬n ¸nh nªn ¶nh cña phÇn tö a₂ph¶i kh¸c ¶nh cña a₁nªn chØ cã n -

1 c¸ch chän ¶nh cho phÇn tö a₂. Nãi chung, ®Ó chän ¶nh cña a_kta cã n - k + 1

c¸ch. Theo quy t¾c nh©n, ta cã

n!

n(n  1)(n  2)...(n  m + 1) =

®¬n ¸nh tõ tËp A ®Õn tËp B.

(n  m)!

2.2.2.5. Gi¸ trÞ cña biÕn k b»ng bao nhiªu sau khi ch ¬ng tr×nh sau ® îc

thùc hiÖn?

m := 0

for i₁:= 1 to n₁

for i₂:= 1 to n₂

.......................

for i_k:= 1 to n_k

k := k+1

Gi¸ trÞ khëi t¹o cña k b»ng 0. Ta cã k vßng lÆp ® îc lång nhau. Gäi T_ilµ

viÖc thi hµnh vßng lÆp thø i. Khi ®ã sè lÇn ®i qua vßng lÆp b»ng sè c¸ch lµm c¸c

viÖc T₁, T₂, ..., T_k. Sè c¸ch thùc hiÖn viÖc T_jlµ n_j(j=1, 2,..., k), v× vßng lÆp thø j

® îc duyÖt víi mçi gi¸ trÞ nguyªn i_jn»m gi÷a 1 vµ n_j. Theo quy t¾c nh©n vßng

lÆp lång nhau nµy ® îc duyÖt qua n₁.n₂....n_klÇn. V× vËy gi¸ trÞ cuèi cïng cña k lµ

n₁.n₂....n_k.

Tãm l¹i: Nguyªn lý nh©n th êng ® îc ph¸t biÓu b»ng ng«n ng÷ tËp hîp nh

sau. NÕu A₁, A₂,..., A_klµ c¸c tËp h÷u h¹n, khi ®ã sè phÇn tö cña tÝch Descartes

10

cña c¸c tËp nµy b»ng tÝch cña sè c¸c phÇn tö cña mäi tËp thµnh phÇn. Ta biÕt

r»ng viÖc chän mét phÇn tö cña tÝch Descartes A₁x A₂x...x A_k® îc tiÕn hµnh

b»ng c¸ch chän lÇn l ît mét phÇn tö cña A₁, mét phÇn tö cña A₂, ..., mét phÇn tö

cña A_k. Theo quy t¾c nh©n ta cã:

|A₁x A₂x ... x A_k| = |A₁|.|A₂|...|A_k|.

Tæng qu¸t: N(A.B) = N(A).N(B)

2.3. Nguyªn lý bï trõ:

Khi hai c«ng viÖc cã thÓ ® îc lµm ®ång thêi, ta kh«ng thÓ dïng quy t¾c

céng ®Ó tÝnh sè c¸ch thùc hiÖn nhiÖm vô gåm c¶ hai viÖc. §Ó tÝnh ®óng sè c¸ch

thùc hiÖn nhiÖm vô nµy ta céng sè c¸ch lµm mçi mét trong hai viÖc råi trõ ®i sè

c¸ch lµm ®ång thêi c¶ hai viÖc. Ta cã thÓ ph¸t biÓu nguyªn lý ®Õm nµy b»ng

ng«n ng÷ tËp hîp. Cho A₁, A₂lµ hai tËp h÷u h¹n, khi ®ã

|A₁ A₂| = |A₁| + |A₂|  |A₁ A₂|.

Tõ ®ã víi ba tËp hîp h÷u h¹n A₁, A₂, A₃, ta cã:

|A₁A₂A₃|= |A₁| +|A₂|+ |A₃|  |A₁A₂|  |A₂A₃| |A₃A₁| + |A₁A₂A₃|

vµ b»ng quy n¹p, víi k tËp h÷u h¹n A₁, A₂, ..., A_kta cã:

| A₁ A₂ ...  A_k| = N₁ N₂+ N₃ ... + (1)^k-1N_k,

Trong ®ã N_m(1  m  k) lµ tæng phÇn tö cña tÊt c¶ c¸c giao m tËp lÊy tõ k tËp ®·

cho, nghÜa lµ:

| A  A  ... A |

N_m=



i₁

1i₁i₂...i_mk

i₂

i_m

B©y giê ta ®ång nhÊt tËp A_m(1  m  k) víi tÝnh chÊt A_mcho trªn tËp vò trô

h÷u h¹n U nµo ®ã vµ ®Õm xem cã bao nhiªu phÇn tö cña U sao cho kh«ng tháa

N

m·n bÊt kú mét tÝnh chÊt A_mnµo. Gäi

lµ sè cÇn ®Õm, N lµ sè phÇn tö cña U.

Ta cã:

N

= N  | A₁ A₂ ...  A_k| = N  N₁+ N₂ ... + (1)^kN_k

trong ®ã N_mlµ tæng c¸c phÇn tö cña U tháa m·n m tÝnh chÊt lÊy tõ k tÝnh chÊt ®·

cho. C«ng thøc nµy ® îc gäi lµ nguyªn lý bï trõ. Nã cho phÐp tÝnh

N

qua c¸c

N_mtrong tr êng hîp c¸c sè nµy dÔ tÝnh to¸n h¬n.

VÝ dô: Cã n l¸ th vµ n phong b× ghi s½n ®Þa chØ. Bá ngÉu nhiªn c¸c l¸ th

vµo c¸c phong b×. Hái x¸c suÊt ®Ó x¶y ra kh«ng mét l¸ th nµo ®óng ®Þa chØ.

11

Mçi phong b× cã n c¸ch bá th vµo, nªn cã tÊt c¶ n! c¸ch bá th . VÊn ®Ò

cßn l¹i lµ ®Õm sè c¸ch bá th sao cho kh«ng l¸ th nµo ®óng ®Þa chØ. Gäi U lµ

tËp hîp c¸c c¸ch bá th vµ A_mlµ tÝnh chÊt l¸ th thø m bá ®óng ®Þa chØ. Khi ®ã

theo c«ng thøc vÒ nguyªn lý bï trõ ta cã:

N

= n!  N₁+ N₂ ... + (1)ⁿN_n,

trong ®ã N_m(1  m  n) lµ sè tÊt c¶ c¸c c¸ch bá th sao cho cã m l¸ th ®óng ®Þa

chØ. NhËn xÐt r»ng, N_mlµ tæng theo mäi c¸ch lÊy m l¸ th tõ n l¸, víi mçi c¸ch

lÊy m l¸ th , cã (n-m)! c¸ch bá ®Ó m l¸ th nµy ®óng ®Þa chØ, ta nhËn ® îc:

1

 ... + (1)ⁿ),

n!

k!

1

N_m= C_n^m(n - m)! =

vµ

= n!(1 

+

N

1! 2!

n!

C^m

trong ®ã

=

lµ tæ hîp chËp m cña tËp n phÇn tö (sè c¸ch chän m

n

m!(n  m)!

1

®èi t îng trong n ®èi t îng ® îc cho). Tõ ®ã x¸c suÊt cÇn t×m lµ: 1 

+



1! 2!

1

n!

1

... + (1)ⁿ. Mét ®iÒu lý thó lµ x¸c suÊt nµy dÇn ®Õn e ^-1(nghÜa lµ cßn > ) khi

3

n kh¸ lín.

Sè

D íi ®©y lµ mét vµi gi¸ trÞ cña D_n, cho ta thÊy D_nt¨ng nhanh nh thÕ nµo so

víi n:

N

trong bµi to¸n nµy ® îc gäi lµ sè mÊt thø tù vµ ® îc ký hiÖu lµ D_n.

n

2

1

3

2

4

5

6

7

8

9

10

11

D_n

9 44 265 1854 14833 133496 1334961 14684570

2.4. Nguyªn lý Dirichlet

2.4.1. Më ®Çu:

Gi¶ sö cã mét ®µn chim bå c©u bay vµo chuång. NÕu sè chim nhiÒu h¬n

sè ng¨n chuång th× Ýt nhÊt trong mét ng¨n cã nhiÒu h¬n mét con chim.

Nguyªn lý nµy dÜ nhiªn lµ cã thÓ ¸p dông cho c¸c ®èi t îng kh«ng ph¶i lµ

chim bå c©u vµ chuång chim.

MÖnh ®Ò (Nguyªn lý): NÕu cã k +1 (hoÆc nhiÒu h¬n) ®å vËt ® îc ®Æt vµo

trong k hép th× tån t¹i mét hép cã Ýt nhÊt hai ®å vËt.

Chøng minh: Gi¶ sö kh«ng cã hép nµo trong k hép chøa nhiÒu h¬n mét

®å vËt. Khi ®ã tæng sè vËt ® îc chøa trong c¸c hép nhiÒu nhÊt lµ b»ng k. §iÒu

nµy tr¸i gi¶ thiÕt lµ cã Ýt nhÊt k + 1 vËt.

12

Nguyªn lý nµy th êng ® îc gäi lµ nguyªn lý Dirichlet, mang tªn nhµ

to¸n häc ng êi §øc ë thÕ kû 19. ¤ng th êng xuyªn sö dông nguyªn lý nµy

trong c«ng viÖc cña m×nh.

2.4.2. VÝ dô:

1) Trong bÊt kú mét nhãm 367 ng êi thÕ nµo còng cã Ýt nhÊt hai ng êi cã

ngµy sinh nhËt gièng nhau bëi v× chØ cã tÊt c¶ 366 ngµy sinh nhËt kh¸c nhau.

2) Trong kú thi häc sinh giái, ®iÓm bµi thi ® îc ®¸nh gi¸ bëi mét sè

nguyªn trong kho¶ng tõ 0 ®Õn 100. Hái r»ng Ýt nhÊt cã bao nhiªu häc sinh dù

thi ®Ó cho ch¾c ch¾n t×m ® îc hai häc sinh cã kÕt qu¶ thi nh nhau?

Theo nguyªn lý Dirichlet, sè häc sinh cÇn t×m lµ 102, v× ta cã 101 kÕt qu¶

®iÓm thi kh¸c nhau.

3) Trong sè nh÷ng ng êi cã mÆt trªn tr¸i ®Êt, ph¶i t×m ® îc hai ng êi cã

hµm r¨ng gièng nhau. NÕu xem mçi hµm r¨ng gåm 32 c¸i nh lµ mét x©u nhÞ

ph©n cã chiÒu dµi 32, trong ®ã r¨ng cßn øng víi bit 1 vµ r¨ng mÊt øng víi bit

0, th× cã tÊt c¶ 2³²= 4.294.967.296 hµm r¨ng kh¸c nhau. Trong khi ®ã sè

ng êi trªn hµnh tinh nµy lµ v ît qu¸ 5 tØ, nªn theo nguyªn lý Dirichlet ta cã

®iÒu cÇn t×m.

2.4.3. Nguyªn lý Dirichlet tæng qu¸t:

MÖnh ®Ò: NÕu cã N ®å vËt ® îc ®Æt vµo trong k hép th× sÏ tån t¹i mét hép

N

k

 

N

k

 

chøa kh«ng Ýt h¬n

®å vËt.(hay tån t¹i hép cã Ýt nhÊt

®å vËt)

 

(ë ®©y, [x] ®ã lµ sè nguyªn nhá nhÊt cã gi¸ trÞ lín h¬n hoÆc b»ng x. Kh¸i niÖm

nµy ®èi ngÉu víi [x] gi¸ trÞ cña hµm sµn hay hµm phÇn nguyªn t¹i x lµ sè

nguyªn lín nhÊt cã gi¸ trÞ nhá h¬n hoÆc b»ng x.)

N

 

Chøng minh: Gi¶ sö mäi hép ®Òu chøa Ýt h¬n

vËt. Khi ®ã tæng sè ®å

 

k

 

N

k

 

 

k.

vËt tèi ®a lµ

®å vËt

 

§iÒu nµy m©u thuÈn víi gi¶ thiÕt lµ cã N ®å vËt cÇn xÕp.

VËy ta cã ®iÒu ph¶i chøng minh

VÝ dô:

1. Chøng minh r»ng trong 100 ng êi, cã Ýt nhÊt 9 ng êi sinh cïng mét

th¸ng.

13

XÕp nh÷ng ng êi sinh cïng th¸ng vµo mét nhãm. Cã 12 th¸ng tÊt c¶. VËy

theo nguyªn lý Dirichlet, tån t¹i mét nhãm cã Ýt nhÊt ]100/12[= 9 ng êi.

2. Cã n¨m lo¹i häc bæng kh¸c nhau. Hái r»ng ph¶i cã Ýt nhÊt bao nhiªu

sinh viªn ®Ó ch¾c ch¾n r»ng cã Ýt ra lµ 6 ng êi cïng nhËn häc bæng nh nhau.

Gäi N lµ sè sinh viªn, khi ®ã ]N/5[ = 6 khi vµ chØ khi 5 < N/5  6 hay 25

< N  30. VËy sè N cÇn t×m lµ 26.

3. Sè m· vïng cÇn thiÕt nhá nhÊt ph¶i lµ bao nhiªu ®Ó ®¶m b¶o 25 triÖu m¸y

®iÖn tho¹i trong n íc cã sè ®iÖn tho¹i kh¸c nhau, mçi sè cã 9 ch÷ sè (gi¶ sö sè

®iÖn tho¹i cã d¹ng 0XX - 8XXXXX víi X nhËn c¸c gi¸ trÞ tõ 0 ®Õn 9).

Cã 10⁷= 10.000.000 sè ®iÖn tho¹i kh¸c nhau cã d¹ng 0XX - 8XXXXX. V×

vËy theo nguyªn lý Dirichlet tæng qu¸t, trong sè 25 triÖu m¸y ®iÖn tho¹i Ýt nhÊt

cã ]25.000.000/10.000.000[ = 3 cã cïng mét sè. §Ó ®¶m b¶o mçi m¸y cã mét

sè cÇn cã Ýt nhÊt 3 m· vïng.

2.4.4. Mét sè øng dông cña nguyªn lý Dirichlet.

L•u ý: Trong nhiÒu øng dông cña nguyªn lý Dirichlet, kh¸i niÖm ®å vËt vµ

hép cÇn ph¶i ® îc lùa chän mét c¸ch kh«n khÐo.

VÝ dô 1. Trong mét phßng häp cã n ng êi, bao giê còng t×m ® îc 2 ng êi

cã sè ng êi quen trong sè nh÷ng ng êi dù häp lµ nh nhau.

Sè ng êi quen cña mçi ng êi trong phßng häp nhËn c¸c gi¸ trÞ tõ 0 ®Õn

n1. Râ rµng trong phßng kh«ng thÓ ®ång thêi cã ng êi cã sè ng êi quen lµ 0

(tøc lµ kh«ng quen ai) vµ cã ng êi cã sè ng êi quen lµ n  1 (tøc lµ quen tÊt c¶).

V× vËy theo sè l îng ng êi quen, ta chØ cã thÓ ph©n n ng êi ra thµnh n 1 nhãm.

VËy theo nguyªn lý Dirichlet tån tai mét nhãm cã Ýt nhÊt 2 ng êi, tøc lµ lu«n t×m

® îc Ýt nhÊt 2 ng êi cã sè ng êi quen lµ nh nhau.

VÝ dô 2. Trong mét th¸ng gåm 30 ngµy, mét ®éi bãng chuyÒn thi ®Êu mçi

ngµy Ýt nhÊt 1 trËn nh ng ch¬i kh«ng qu¸ 45 trËn. Chøng minh r»ng t×m ® îc

mét giai ®o¹n gåm mét sè ngµy liªn tôc nµo ®ã trong th¸ng sao cho trong giai

®o¹n ®ã ®éi ch¬i ®óng 14 trËn.

Gäi a_jlµ sè trËn mµ ®éi ®· ch¬i tõ ngµy ®Çu th¸ng ®Õn hÕt ngµy j. Khi ®ã

1  a₁< a₂< ... < a₃₀< 45

15  a₁+14 < a₂+14 < ... < a₃₀+14 < 59.

S¸u m ¬i sè nguyªn a₁, a₂, ..., a₃₀, a₁+ 14, a₂+ 14, ..., a₃₀+14 n»m gi÷a 1 vµ 59.

Do ®ã theo nguyªn lý Dirichlet cã Ýt nhÊt 2 trong 60 sè nµy b»ng nhau. V× vËy

14

tån t¹i i vµ j sao cho ai = aj + 14 (j < i). §iÒu nµy cã nghÜa lµ tõ ngµy j + 1 ®Õn

hÕt ngµy i ®éi ®· ch¬i ®óng 14 trËn.

VÝ dô 3. Chøng tá r»ng trong n + 1 sè nguyªn d ¬ng kh«ng v ît qu¸ 2n,

tån t¹i Ýt nhÊt mét sè chia hÕt cho sè kh¸c.

2^k

Ta viÕt mçi sè nguyªn a₁, a₂,..., a_n+1d íi d¹ng a_j= ^jq_jtrong ®ã k lµ sè

j

lÎ nhá h¬n 2n nªn theo nguyªn lý Dirichlet tån t¹i i vµ j sao cho q_i= q_j= q. Khi

®ã a_i= 2^kq vµ aj = 2^k^jq. V× vËy, nÕu k_i k_jth× a_jchia hÕt cho a_icßn trong

i

tr êng hîp ng îc l¹i ta cã a_ichia hÕt cho a_j.

VÝ dô cuèi cïng tr×nh bµy c¸ch ¸p dông nguyªn lý Dirichlet vµo lý thuyÕt tæ

hîp mµ vÉn quen gäi lµ lý thuyÕt Ramsey, tªn cña nhµ to¸n häc ng êi Anh. Nãi

mét tËp c¸c phÇn tö.

VÝ dô 4. Gi¶ sö trong mét nhãm 6 ng êi mçi cÆp hai hoÆc lµ b¹n hoÆc lµ

thï. Chøng tá r»ng trong nhãm cã ba ng êi lµ b¹n lÉn nhau hoÆc cã ba ng êi lµ

kÎ thï lÉn nhau.

Gäi A lµ mét trong 6 ng êi. Trong sè 5 ng êi cña nhãm hoÆc lµ cã Ýt nhÊt

ba ng êi lµ b¹n cña A hoÆc cã Ýt nhÊt ba ng êi lµ kÎ thï cña A, ®iÒu nµy suy ra

tõ nguyªn lý Dirichlet tæng qu¸t, v× ]5/2[ = 3. Trong tr êng hîp ®Çu ta gäi B, C,

D lµ b¹n cña A. nÕu trong ba ng êi nµy cã hai ng êi lµ b¹n th× hä cïng víi A lËp

thµnh mét bé ba ng êi b¹n lÉn nhau, ng îc l¹i, tøc lµ nÕu trong ba ng êi B, C, D

kh«ng cã ai lµ b¹n ai c¶ th× chøng tá hä lµ bé ba ng êi thï lÉn nhau. T ¬ng tù cã

thÓ chøng minh trong tr êng hîp cã Ýt nhÊt ba ng êi lµ kÎ thï cña A.

2.5. Bµi tËp

2.5.1. Trong tæng sè 2504 sinh viªn cña mét khoa c«ng nghÖ th«ng tin, cã

1876 theo häc m«n ng«n ng÷ lËp tr×nh Pascal, 999 häc m«n ng«n ng÷ Fortran vµ

345 häc ng«n ng÷ C. Ngoµi ra cßn biÕt 876 sinh viªn häc c¶ Pascal vµ Fortran,

232 häc c¶ Fortran vµ C, 290 häc c¶ Pascal vµ C. NÕu 189 sinh viªn häc c¶ 3

m«n Pascal, Fortran vµ C th× trong tr êng hîp ®ã cã bao nhiªu sinh viªn kh«ng

häc m«n nµo trong 3 m«n ng«n ng÷ lËp tr×nh kÓ trªn.

2.5.2. Mét cuéc häp gåm 12 ng êi tham dù ®Ó bµn vÒ 3 vÊn ®Ò. Cã 8 ng êi

ph¸t biÓu vÒ vÊn ®Ò I, 5 ng êi ph¸t biÓu vÒ vÊn ®Ò II vµ 7 ng êi ph¸t biÓu vÒ vÊn

15

®Ò III. Ngoµi ra, cã ®óng 1 ng êi kh«ng ph¸t biÓu vÊn ®Ò nµo. Hái nhiÒu l¾m lµ

cã bao nhiªu ng êi ph¸t biÓu c¶ 3 vÊn ®Ò.

2.5.3. Trong tËp sè nguyªn {1, 2, , 100} cã bao nhiªu sè kh«ng chia hÕt

cho bÊt kú sè nµo trong c¸c sè 3, 4, 7

2.5.4. Cã bao nhiªu

a. Kh«ng chøa cïng mét ch÷ sè 3 lÇn

b. B¾t ®Çu b»ng ch÷ sè lÎ

c. Cã ®óng hai ch÷ sè 4

thóc b»ng 111

2.5.7. Cã bao nhiªu sè nguyªn kh«ng lín h¬n 1000 chia hÕt cho 7 hoÆc 11

2.5.8. Trong sè c¸c sè nguyªn d ¬ng cã 3 ch÷ sè, cã bao nhiªu sè:

a. Chia hÕt cho 7

e. Kh«ng chia hÕt cho 4

f. Chia hÕt cho 3 hoÆc 4

g. Kh«ng chia hÕt cho 3 hoÆc cho 4

h. Chia hÕt cho 3 nh ng kh«ng chia

hÕt cho 4

b. LÎ

c. Cã 3 ch÷ sè ®«I mét kh¸c nhau

d. Chia hÕt cho 3 vµ cho 4

2.5.10. T×m hÖ sè cña x⁵y⁸trong khai triÓn (x + y)¹³

ACCESS, yªu cÇu ph¶i dïng tÊt c¶ c¸c ch÷?

2.5.12. Mét gi¸o s cÊt bé s u tËp gåm 40 sè b¸o to¸n häc vµo 4 chiÕc ng¨n

tñ, mçi ng¨n ®ùng 10 sè. Cã bao nhiªu c¸ch cã thÓ cÊt c¸c tê b¸o vµo c¸c ng¨n

nÕu:

2) C¸c ng¨n lµ gièng hÖt nhau?

16

3. Bµi to¸n tån t¹i vµ ph ¬ng ph¸p gi¶i

Khi nghiªn cøu vÒ bµi to¸n ®Õm, c«ng viÖc chñ yÕu cña chóng ta lµ ®Õm sè

cÊu h×nh tho¶ ®iÒu kiÖn bµi to¸n ®Æt ra, vµ c¸c bµi to¸n ®ã sù tån t¹i cña c¸c cÊu

h×nh lµ hiÓn nhiªn. Tuy nhiªn trong rÊt nhiÒu bµi to¸n viÖc chØ ra sù tån t¹i cña

mét cÊu h×nh lµ rÊt khã kh¨n. ViÖc chØ ra cÊu h×nh tho¶ ®iÒu kiÖn cña bµi to¸n th×

tr íc hÕt cÇn ph¶i x¸c ®Þnh xem cÊu h×nh ®ã cã tån t¹i hay kh«ng.

3.1. Ph ¬ng ph¸p ph¶n chøng

VÝ dô: CÇn t×m mét c¸ch kÕt nèi 15 m¸y tÝnh víi nhau sao cho mçi m¸y

® îc kÕt nèi víi ®óng 5 m¸y kh¸c.

Ta chøng minh kh«ng cã c¸ch nµo kÕt nèi ® îc

Gi¶ sö tån t¹i mét c¸ch nèi tho¶ yªu cÇu

15*5

Z 

Sè ® êng nèi:

m©u thuÉn

2

VËy kh«ng t×m ® îc c¸ch nèi nµo sao cho mçi m¸y kÕt nèi ® îc víi ®óng 5

m¸y.

3.2. Ph ¬ng ph¸p sö dông nguyªn lý Dirichlet

* Nguyªn Lý: Bá n +1 ®å vËt vµo trong n c¸i lä

nhiÒu h¬n 1 ®å vËt

* Nguyªn lý tæng qu¸t: Bá n.k + 1 ®å vËt vµo n hép

nhiÒu h¬n k ®å vËt.



tån t¹i mét hép chøa



VÝ dô 1: Mét líp häc cã 45 häc sinh. Chia líp ra lµm 4 tæ. Chøng minh lu«n

tån t¹i mét tæ cã Ýt nhÊt 12 häc sinh.

Gi¶i:

ThËt vËy, líp häc cã 45 häc sinh, nÕu chia ®Òu ra c¸c tæ th× mçi tæ sÏ cã 11

häc sinh vµ d 1 häc sinh. Häc sinh nµy sÏ ® îc sÕp vµo 1 trong 4 tæ, khi ®ã nÕu

® îc sÕp vµo tæ nµo th× tæ ®ã sÏ cã 12 häc sinh. VËy cã ®iÒu ph¶i chøng minh

VÝ dô 2: LÊy n +1 sè nguyªn tuú ý. Chøng minh r»ng t×m ® îc hai sè cã

hiÖu cña chóng chia hÕt cho n.

Gi¶i: gäi c¸c sè lµ: x₁, x₂, ..., x_n+1

x_ia (mod n)



0  a_i n1

i

theo nguyªn lý Dirichlet: i, j : a_i a_j x_i x_j 0(modn)

3.3. Mét sè bµi to¸n

17

Bài toán 1) Nèi 6 ®iÓm víi nhau tõng cÆp thµnh c¸c ®o¹n th¼ng t« mµu

xanh hoÆc ®á. CMR t×m ® îc mét tam gi¸c cã 3 c¹nh cïng mµu.

Ta lÊy mét ®iÓm tuú ý (gi¶ sö A)

A

KÎ 5 ®o¹n th¼ng tõ A ®Õn 5 ®iÓm cßn l¹i vµ ® îc t« mµu

xanh hoÆc ®á

B

Theo Dirichlet: cã Ýt nhÊt 3 ®o¹n th¼ng cïng mµu, gi¶ sö lµ

AB, AC, AD.

C

D

NÕu mét trong c¸c ®o¹n th¼ng BC, CD, BD mµu xanh

th× ta ® îc tam gi¸c t ¬ng øng ®Ønh A toµn xanh

ng îc l¹i, ta ® îc tam gi¸c BCD ®á

Bài toán 2) Trong mét phßng häp bao giê còng t×m ® îc hai ng êi cã sè

ng êi quen trong sè nh÷ng ng êi dù häp lµ b»ng nhau.

Gi¶i: Gäi sè ng êi dù häp lµ n  sè ng êi quen cña mét ng êi n_inµo ®ã

={0,..n-1}.

Ta thÊy: mét ng êi kh«ng thÓ ®ång thêi cã sè ng êi quen lµ 0 hoÆc n -1 

thµnh n -1 nhãm  ph¶i cã Ýt nhÊt hai ng êi cã cïng sè ng êi quen.

Bài toán 3) Chøng minh r»ng kh«ng thÓ nèi 31 m¸y vi tÝnh thµnh mét

m¹ng sao cho mçi m¸y ® îc nèi víi ®óng 5 m¸y kh¸c

Gi¶i:

Gi¶ sö ta lu«n t×m ® îc c¸ch nèi 31 m¸y tÝnh l¹i thµnh m¹ng sao cho mçi

31

2

5*  75,5

lµ ®óng.

3.4. Bµi tËp

n

3.4.1. Chøng minh r»ng kC^k n2^n1



n

k1

v ît qu¸ m, n ta

r

C^r C^kC^rk

cã:



mn

n

m

k0

18

3.4.3. ChØ ra r»ng cã Ýt nhÊt 4 ng êi trong sè 25 triÖu ng êi cã cïng tªn hä

viÕt t¾t b»ng 3 ch÷ c¸i sinh cïng ngµy trong n¨m (kh«ng nhÊt thiÕt trong cïng

mét n¨m).

3.4.4. Mét tay ®« vËt tham gia thi ®Êu giµnh chøc v« ®Þch trong 75 giê. Mçi

giê anh ta cã Ýt nhÊt mét trËn ®Êu, nh ng toµn bé anh ta cã kh«ng qu¸ 125 trËn.

Chøng tá r»ng cã nh÷ng giê liªn tiÕp anh ta ®· ®Êu ®óng 24 trËn.

3.4.5. Cho n lµ sè nguyªn d ¬ng bÊt kú. Chøng minh r»ng lu«n lÊy ra ® îc

tõ n sè ®· cho mét sè sè h¹ng thÝch hîp sao cho tæng cña chóng chia hÕt cho n.

3.4.6. Trong mét cuéc lÊy ý kiÕn vÒ 7 vÊn ®Ò, ng êi ® îc hái ghi vµo mét

víi 7 vÊn ®Ò ®· nªu.

Chøng minh r»ng víi 1153 ng êi ® îc hái lu«n t×m ® îc 10 ng êi tr¶ lêi

gièng hÖt nhau.

3.4.7. Cã 17 nhµ b¸c häc viÕt th cho nhau trao ®æi 3 vÊn ®Ò. Chøng minh

r»ng lu«n t×m ® îc 3 ng êi cïng trao ®æi mét vÊn ®Ò.

® îc 5 ®iÓm.

3.4.9. Ph ¬ng tr×nh x₁+ x₂+ x₃+ x₄+ x₅= 21 cã bao nhiªu nghiÖm nguyªn

kh«ng ©m?

3.4.10. Cho n lµ mét sè nguyªn d ¬ng. Chøng tá r»ng trong mäi tËp n sè

nguyªn d ¬ng liªn tiÕp cã ®óng mét sè chia hÕt cho n

3.4.11. Trong mét m¹ng m¸y tÝnh, mçi m¸y nèi trùc tiÕp hoÆc kh«ng nèi víi

c¸c m¸y kh¸c. ChØ ra r»ng cã Ýt nhÊt hai m¸y mµ sè c¸c m¸y kh¸c nèi víi chóng lµ

b»ng nhau.

3.4.12.Trong kh«ng gian cho 9 ®iÓm cã to¹ ®é nguyªn, Chøng tá r»ng bao

giê còng cã mét cÆp ®iÓm cã trung ®iÓm nguyªn

3.4.13. Chøng minh r»ng trong 5 sè chän tõ 8 sè nguyªn ®Çu tiªn tån t¹i

mét cÆp sè cã tæng b»ng 9. §iÒu kh¼ng ®Þnh nµy cßn ®óng nÕu chän 4 chø kh«ng

ph¶i chän 5

3.4.14. Chøng minh r»ng trong 7 sè chän tõ 10 sè nguyªn ®Çu tiªn tån t¹i

mét cÆp sè cã tæng b»ng 11. §iÒu kh¼ng ®Þnh nµy cßn ®óng nÕu chän 6 chø

kh«ng ph¶i chän 7

19

ch ¬ng 2: c¸c kh¸i niÖm c¬ b¶n cña lý thuyÕt ®å thÞ

M· ch ¬ng: Mh12.2

Giới thiệu:

Trình bày các kiến thức cơ bản về lý thuyết đồ thị. Cung cấp các kiến thức

cơ bản về lý thuyết đồ thị, giúp người học có kiến thức cơ sở để nghiên cứu về

đồ thị trong các chương tiếp theo.

Mục tiêu:

- Trình bày được các khái niệm của đố thị

- Xác định được các loai đồ thị, chu trình, đồ thị liên thông.

- Nghiêm túc trong học tập, đảm bảo an toàn cho người và trang thiết bị.

Nội dung chính:

1. §Þnh nghÜa ®å thÞ

§å thÞ lµ mét cÊu tróc rêi r¹c bao gåm c¸c ®Ønh vµ c¸c c¹nh nèi c¸c ®Ønh

nµy l¹i víi nhau.

§å thÞ G lµ mét cÆp G = (V,E)

E: Lµ tËp c¸c cÆp (u,v) nµo ®ã (gäi lµ c¹nh cña ®å thÞ) víi u,v  V,(u,v) 

E  (v,u)  E vµ coi (u,v) (v,u):

+ §å thÞ G gäi lµ v« h íng nÕu  u,v V: (u,v)  E  (v,u)  E

+ §å thÞ G gäi lµ cã h íng nÕu  u,v V: (u,v)  (v,u)

quy íc: NÕu bµi to¸n chØ nãi ®å thÞ mµ kh«ng nãi râ lµ v« h íng hay cã

h íng th× ta ngÇm hiÓu lµ ®å thÞ v« h íng.

+ §å thÞ G gäi lµ ®¬n ®å thÞ nÕu V = u,v,x,y,z

E = (u,x),(u,y),(u,v),(u,z) 

2. C¸c thuËt ng÷ c¬ b¶n

+ §å thÞ G = (V,E) víi ®Ønh v  V, e = (u,v)  E

Khi ®ã: u,v lµ hai ®Ønh ®Çu, cuèi cña c¹nh e

e _ c¹nh liªn thuéc u,v

+ Hai ®Ønh u,v cña ®å thÞ v« h íng G = (V,E) ® îc gäi lµ kÒ nhau nÕu (u,v)

lµ c¹nh cña ®å thÞ .

+ BËc cña ®Ønh: BËc cña ®Ønh u V lµ sè c¹nh liªn th éc víi u kÝ hiÖu

deg(u)

20