CHƯƠNG I. MỘT SỐ KHÁI NIỆM CƠ BẢN Trong chương này trình bày một số khái niệm cơ bản cần thiết cho các chương tiếp theo. TẬP XÂU KÝ HIỆU VÀ MỘT SỐ PHÉP TOÁN I. Tập xâu ký hiệu.
Tập ∑ ≠ gồm hữu hạn hoặc vô hạn các đối tượng được gọi là bảng chữ cái (hay tự điển). Mỗi phần tử a ∑ được gọi là ký hiệu hoặc chữ cái (thuộc bảng chữ cái ∑). Ví dụ: P= 0,1 là bảng chữ cái nhị phân. Q= 0,1, 2,3, 4,5,6,7,8,9 là bảng chữ cái thập phân.
R= , , , , là bảng chữ cái gồm: Hình tam giác, hình vuông, hình tròn, hình chữ nhật, hình thoi. Giả sử có bảng chữ cái ∑= a1,a 2 ,.,a n Dãy α gồm các ký hiệu thuộc bảng chữ cái ∑ α= ai1 ai2 .a it ,a is (1 s t) được gọi là một xâu ký hiệu hay một xâu trên bảng chữ cái ∑. TIEU LUAN MOI download : skknchat@gmail.com 2 Tổng số vị trí của tất cả các ký hiệu xuất hiện trong α được gọi là độ dài của xâu α và ký hiệu bằng . Xâu có độ dài bằng 0 (tức xâu không chứa một ký hiệu nào) được gọi là xâu rỗng hay xâu trống đồng thời được ký hiệu bằng hoặc .
Xâu rỗng là xâu thuộc bất kỳ bảng chữ cái nào. Dễ dàng thấy rằng: Nếu α là xâu thuộc bảng chữ cái ∑, thì nó cũng là xâu trên bảng chữ cái tùy ý chứa ∑. Ví dụ: β= 101011 là xâu trên bảng chữ cái nhị phân P= 0,1 và = 6, còn = 1223233 là xâu trên bảng chữ cái S= 1, 2,3 và =7 Các xâu β, đều là các xâu trên bảng chữ cái thập phân. Tập gồm tất cả các xâu trên bảng chữ cái ∑ được ký hiệu bằng ∑*, còn tập gồm tất cả các xâu khác rỗng trên bảng chữ cái ∑ được ký hiệu bằng ∑+.
Dễ dàng thấy rằng ∑+ = ∑*\ 3. Tập xâu ký hiệu. Giả sử có bảng chữ cái ∑. Mỗi tập con A ∑* được gọi là một tập xâu ký hiệu trên bảng chữ cái ∑ (nếu ∑ là bảng chữ cái số và các xâu ký hiệu thuộc A đều là các số, thì A còn được gọi là tập số trên ∑).
Tập được gọi là tập xâu trống. Tập xâu trống là tập xâu trên bất kỳ bảng chữ cái nào. Hiển nhiên rằng tập xâu trống khác với tập xâu chỉ gồm xâu rỗng. Ví dụ: L= { ,1,0,10,011 } là tập xâu trên bảng chữ cái nhị phân P= 0,1 , còn L1= {a,bc,bac} là tập xâu trên bảng chữ cái ∑={a,b,c}.
TIEU LUAN MOI download : skknchat@gmail. Đây là phép toán thực hiện trên xâu ký hiệu. Tích ghép của các xâu không rỗng α= a1a2…am và β=b1b2…bn là xâu = c1c2…cm+n, trong đó c1= a1, c2= a2 ,…, cm= am , cm+1= b1, cm+2= b2,…, cm+n= bn. Ngoài ra, đối với xâu tùy ý α tích ghép của α với xâu rỗng bằng tích ghép của với α và bằng α.
Dễ dàng thấy rằng, tích ghép có tính chất kết hợp, song nó chỉ giao hoán khi các xâu trên bảng chữ cái một ký hiệu. Ta viết αn thay cho cách viết αα…α(n lần) và quy ước rằng α1= α, còn α0 là xâu rỗng. Ví dụ 1: Cho các xâu α= ab, β= cde, µ= 543, = 21. Nếu đối với các xâu µ,α,β,γ trên bảng chữ cái ∑, mà µ= αβγ thì xâu α*β*γ với ký hiệu * không thuộc ∑ được gọi là một vị trí của xâu β trong xâu µ.
Xâu β được gọi là một xâu con trong xâu µ (hay của xâu µ), nếu tồn tại ít nhất một vị trí của β trong µ. Nếu α= , tức µ= βγ, thì xâu β còn được gọi là phần đầu. Còn nếu γ= tức là µ= αβ thì xâu β được gọi là phần cuối của xâu µ. Khi β= , ta có µ= α γ= µ= µ , nên xâu rỗng là xâu con, là phần đầu, phần đuôi của bất kỳ xâu nào và được gọi là xâu con tầm thường.
Trong trường hợp độ dài của xâu β= 1, tức là nó gồm một ký hiệu. Chẳng hạn β= b, b thuộc ∑, thì *b* được gọi là vị trí của ký hiệu b trong xâu µ. Đôi khi vị trí của ký hiệu còn được gọi là điểm. Người ta dùng la(µ) để chỉ số vị trí của ký hiệu a trong xâu µ.
TIEU LUAN MOI download : skknchat@gmail.com 4 Nếu α= t1*at2*, β= s1*bs2* là các điểm của cùng một xâu µ= t1at2= s1bs2. Và t1 < s1 , thì ta viết α< β, đồng thời nói rằng α nằm (hoặc được đặt) bên trái β, còn β nằm bên phải α. Nếu α< β< γ, thì ta nói rằng β nằm giữa α và γ. Đối với hai điểm tùy ý α, β của xâu µ, mà α≤ β, tập hợp các điểm δ thỏa mãn bất đẳng thức α≤ δ≤ β được gọi là một đoạn của xâu µ và được ký hiệu bằng [α, β], còn tập hợp các điểm mà α< δ< β được gọi là một khoảng của xâu µ và được ký hiệu bằng (α, β).
Đôi khi chúng ta cũng cần những khoảng đặc biệt (-, α) và (α, -) là các tập hợp điểm thỏa mãn bất đẳng thức δ< α và α> δ. Khoảng khác với đoạn ở chỗ nó có thể rỗng. Ví dụ 2: Xâu µ= abcbcb chứa 2 vị trí của xâu bcb: a*bcb*cb và abc*bcb*, một vị trí của ký hiệu a: *a*bcbcb, 7 vị trí của xâu rỗng : **abcbcb, a**bcbcb, ab**cbcb, abc**bcb, abcb**cb, abcbc**b, abcbcb**. Nếu ký hiệu các vị trí của chữ cái trong xâu µ bằng α, β, δ, thì α< β< δ.
Các đoạn [α, β] và [β, δ] tương ứng với hai vị trí khác nhau của cùng xâu con bcb. Các phép toán trên các tập xâu ký hiệu. Trên các tập xâu ký hiệu, ngoài các phép toán của lý thuyết tập hợp như: phép hợp, phép giao, phép lấy phần bù. Còn có các phép toán đặc thù như: tích ghép, lặp.
Giả sử L1, L2, L3 là các tập xâu ký hiệu trên bảng chữ cái ∑. TIEU LUAN MOI download : skknchat@gmail.com 5 Tập xâu ký hiệu {x ∑*/ x L1 hoặc x L2} được gọi là hợp của các tập xâu ký hiệu L1 và L2, đồng thời được ký hiệu bằng L1 L2 hoặc L1 L2 Ví dụ: Cho các tập xâu ký hiệu L1= { , a, ab, bc}, L2= {a,b,ca,ab,cb}. Khi đó: L1 L2= { , a, b, ab, bc, ca, cb}. Giao hoán, nghĩa là L1 L2= L2 L1 b.
Kết hợp, nghĩa là (L1 L2) L3= L1 (L2 L3) c. Định nghĩa: Tập xâu ký hiệu {x ∑*/ x L1 và x L2} được gọi là giao của các tập xâu ký hiệu L1 và L2, đồng thời ký hiệu bằng L1∩ L2 hoặc L1 L2 Ví dụ: Với L1, L2 được cho bởi ví dụ trên có giao là L1∩L2 = {a, ab}. Giao hoán, nghĩa là L1∩ L2=L2∩ L1 b. Kết hợp, nghĩa là (L1∩ L2)∩ L3= L1∩ (L2∩ L3) c.
TIEU LUAN MOI download : skknchat@gmail. Phép lấy phần bù. Tập xâu ký hiệu {x ∑* / x L} được gọi là tập xâu ký hiệu phần bù của tập xâu ký hiệu L, đồng thời được ký hiệu bằng C∑L hoặc CL. Ví dụ: Cho L= {a, bc}.
Khi đó: CL= {x ∑*/ x≠ a, x≠ bc}. Hệ thức De Morgan: L1∩ L2= C(CL1 CL2) D. Phép tích ghép. Định nghĩa: Tập xâu ký hiệu {x ∑*/ y L1, y L2, x= y.z= yz} được gọi là tích ghép của các tập xâu ký hiệu L1 và L2, đồng thời ký hiệu bằng L1.
Đối với tích ghép L.L…L(n lần) ta viết dưới dạng thu gọn Ln với quy ước: L1= L và L0= { } Ví dụ 1: Cho các tập xâu ký hiệu L1= { , a, bc, cab}, L2= {b, ca}.L2= {b, ca, ab, aca, bcb, bcca, cabb, cabca}.L1= {b, ca, ba, caa, bbc, cabc, bcab, cacab}. Quy ước rằng: Nếu xâu rỗng xuất hiện trên tập số, thì nó được gọi là số rỗng. Ví dụ 2: Cho các tập số S1= { , 1, 2, 4}, S2= {2, 3, 5}. TIEU LUAN MOI download : skknchat@gmail.
Không giao hoán, tức là: L1. Kết hợp, tức là: (L1. Hợp vô hạn các tập xâu ký hiệu: { } L L.L…L … = Li i0 được gọi là lặp của tập xâu ký hiệu L, đồng thời được ký hiệu bằng L*, còn hợp vô hạn Li được gọi là lặp cắt của tập xâu ký hiệu L, đồng thời i 1 được ký hiệu bằng L+. Cho tập xâu ký hiệu L= {a, b, bc, cba}.L…L …= { } {a, b, bc, cba} {aa, ab, abc, acba, ba, bb, bbc, bcba, bca, bcb, bcbc, bccba, cbaa, cbab, cbabc, cbacba} … = { , a, b, bc, cba, aa, ab, abc, acba, ba, bb, bbc, bcba, bca, bcb, bcbc, bccba, cbaa, cbab, cbabc, cbacba, …}.L…L …= {a, b, bc, cba, aa, , ab, abc, acba, ba, bb, bbc, bcba, bca, bcb, bcbc, bccba, cbaa, cbab, cbabc, cbacba, …}.
Từ định nghĩa ta thấy rằng: Dù tập L có chứa xâu rỗng hay không thì lặp L* vẫn chứa xâu rỗng. TIEU LUAN MOI download : skknchat@gmail. Cho tập số nguyên dương S= {1, 3, 8, 12}. TIEU LUAN MOI download : skknchat@gmail.
Trên mặt phẳng hay trong không gian lấy n điểm khác nhau, được ký hiệu bằng x1, x2, …, xn. Giữa một số cặp điểm (có thể trùng nhau ) được nối bằng các đoạn thẳng hoặc đoạn cong được định hướng (có thể theo chiều khác nhau ). Người ta gọi hình nhận được là một đa đồ thị có hướng (có thể có khuyên), đồng thời ký hiệu bằng G. Các điểm xi (1≤ i≤ n) đã chọn được gọi là các đỉnh.
Các đoạn thẳng và đoạn cong đã nối được gọi là các cung của đồ thị G. Nếu cung có hai đầu trùng nhau, thì nó còn được gọi là một khuyên của đồ thị G. Nếu cung u xuất phát từ đỉnh xi và đi tới đỉnh xj, thì xi được gọi là đỉnh đầu, còn xj được gọi là đỉnh cuối của cung u. (u) xi xJ Nếu cung v có hai đầu đều là xk thì nó được gọi là một khuyên tại đỉnh xk (v) xk Để cho gọn trong các phần tiếp theo ta sẽ gọi đa đồ thị có hướng là đồ thị.
TIEU LUAN MOI download : skknchat@gmail.Đường trên đồ thị. Dãy cung ui1 ui2 .