quan hệ thứ tự trong toán rời rạc

3.1 Các lăm le nghĩa

- Đinh nghĩa 1: Một mối quan hệ 2 ngơi R bên trên một tụ tập X (khác rỗng) được gọi là 1 trong những quan hệ loại tưï (hay vắn tắt, là 1 trong những loại tự) nếu và chỉ nếu như nĩ cĩ 3 tính chất: bản năng, phản xứng, truyền. Khi đĩ tớ cũng nĩi tụ tập X là 1 trong những tập luyện cĩ trật tự. Nếu cĩ tăng tính chất: với từng x, nó  X tớ cĩ xRy hoặc yRx thì tớ nĩi R là một

Bạn đang xem: quan hệ thứ tự trong toán rời rạc

quan hệ trật tự tồn phầntrên X.

Ghi chú :

 Trong tình huống bên trên X cĩ nhiều mối quan hệ trật tự thì Khi xét đến thứ tự động bên trên X tớ cần nĩi rõ rệt trật tự nào là, và tớ thông thường viết lách tập luyện hợp X cĩ trật tự bên dưới dạng một cặp (X,R); nhập đĩ thõa R là mối quan hệ thứ tự đang được xét bên trên X.

 Với 2 tụ tập cĩ trật tự X và Y tớ cĩ thể lăm le đi ra một trật tự trên tích Descartes XxY phụ thuộc vào những trật tự bên trên X và bên trên Y. Từ đĩ thõa ta XxY trở nên một tụ tập trật tự (xem phần bài xích tập).

Ví dụ:

1. Quan hệ bên trên tụ tập những số thựcRlà một mối quan hệ loại tự tồn phần.

2. Cho E là 1 trong những tụ tập. Quan hệtrên

P

3. Trên tụ tập những số nguyên vẹn Z, xét qna hệ “chia hết” hay “ước số của”, ký hiệu là, được khái niệm như sau:

ab  kZ: a = k.b

Dễ dàng kiểm hội chứng rằng mối quan hệ  cĩ 3 tính chất: phản xạ, phản xứng, truyền. Từ đĩ thõa tớ cĩ (Z,) là 1 trong những tụ tập cĩ thứ tự động.

Ta cĩ 2 số nguyên vẹn 2 và 3, khơng cĩ mối quan hệ cùng nhau theo quan hệ. Do đĩkhơng cần là trật tự tồn phần trênZ.

Nhận xét:Nếu (X,R) là 1 trong những tụ tập cĩ trật tự và A X thì quan liêu hệ thứ R thu hẹp bên trên tập luyện A, cũng khá được ký hiệu là R (nếu khơng gây đi ra sai sót lẫn), là 1 trong những mối quan hệ trật tự bên trên A. Nĩi một cách khác, tớ cĩ:

(X,R) trật tự và AX  (A,R) loại tự

Đối với cùng 1 tụ tập cĩ trật tự thì việc nói đến những định nghĩa như “phần tử nhỏ nhất”, “phần tử rộng lớn nhất”, ... là vấn đề rất rất đương nhiên. Dưới đây, tất cả chúng ta tiếp tục trình làng một số trong những định nghĩa cần thiết Khi xét một tập thích hợp cĩ trật tự.

- Định nghĩa 2:Cho (X,) là 1 trong những tụ tập cĩ trật tự, và AX.  Ta gọi một thành phần a  A là 1 trong những phần tử nhỏ nhất của tập

hợp A nếu như và chỉ nếu như với từng xA tớ cĩ : ax.

 Ta gọi một thành phần aA là mộtphần tử rộng lớn nhấtcủa tập luyện hợp A nếu như và chỉ nếu như với từng xA tớ cĩ : xa.

 Ta gọi một thành phần a A là mộtphần tử tối tiểucủa tập luyện hợp A nếu như và chỉ nếu như khơng tồn bên trên xA sao mang lại xa và xa.  Ta gọi một thành phần aA là mộtphần tử tối đại của tập luyện hợp

A nếu như và chỉ nếu như khơng tồn bên trên xA sao mang lại xa và ax.

Nhận xét:

(1) Phần tử nhỏ nhất (lớn nhất) của một tụ tập, nếu như cĩ, là duy nhất.Ta ký hiệu thành phần nhỏ nhất của một tụ tập A là min A hoặc min (A), và ký hiệu thành phần lớn số 1 của A là max A hoặc max (A).

(2) Phần tử tối đái (tối đại) của một tụ tập cĩ trật tự khơng nhất thiết là có một không hai. Ví dụ: xét tụ tập X = 1,2,3 với quan hệ 2 ngơi  được mang lại vì thế  = (1,1), (2,2), (3,3), (1,2), (3,2). Chúng tớ cĩ thể kiểm hội chứng rằng (X, ) là một tụ tập cĩ trật tự. Với loại tựnầy, X cĩ 2 thành phần tối tiểu là một trong và 3.

(3) Phần tử lớn số 1 (nhỏ nhất) của một tụ tập, nếu như cĩ, là phần tử tối đại (tối tiểu) có một không hai của tụ tập đĩ thõa.

Ví dụ:

1. Trong tụ tập cĩ trật tự (Z,), tụ tập A = mZm2 < 100cĩ thành phần nhỏ nhất là -9, và thành phần lớn số 1 là 9. Ta cĩ thể viết: min(A) = -9; max(A) = 9.

2. Trong tụ tập cĩ trật tự (R, ), tụ tập A = xRx2 < 100khơng cĩ thành phần nhỏ nhất và cũng khơng cĩ phần tử lớn nhất.

3. Cho E là 1 trong những tụ tập. Ta đang được biết (

P

P

- Định nghĩa 3:Cho (X,) là 1 trong những tụ tập cĩ trật tự, và AX.  Ta gọi một thành phần x  X là 1 trong những chận dưới của tụ tập A

nếu và chỉ nếu như với từng a  A tớ cĩ : x  a. Chận bên dưới lớn nhất (nếu cĩ), tức là thành phần lớn số 1 nhập tụ tập vớ cả những chận bên dưới của A được ký hiệu làinf (A).

 Ta gọimộtphần tử xX là mộtchận trêncủa tụ tập A nếu và chỉ nếu như với từng a  A tớ cĩ : a  x. Chận bên trên nhỏ nhất

(nếu cĩ), tức là thành phần nhỏ nhất nhập tụ tập toàn bộ những chận bên trên, của A được ký hiệu làsup (A).

Ví du: Trong (R,), A = xRx2< 100. Ta cĩ sup(A) = 10 và inf(A) = -10.

Nhận xét : Nếu nhập một tụ tập A tồn bên trên thành phần max(A) thì đĩ cũng đó là sup(A). Tương tự động, nếu như nhập một tụ tập A tồn bên trên thành phần min(A) thì đĩ thõa cũng đó là inf(A).

- Định nghĩa 4: (Thứ tự động tốt)

Một tụ tập cĩ trật tự được gọi là cĩthứ tự động tốt (hay được sắp tốt) nếu như và chỉ nếu như từng tập luyện thành viên khác trống rỗng đều cĩ thành phần nhỏ nhất.

Ví du:

1. Tập thích hợp cĩ trật tự (N,) là 1 trong những tụ tập được chuẩn bị chất lượng.

2. Tập thích hợp cĩ trật tự (Z, ) khơng cần là 1 trong những tụ tập được sắp chất lượng vìZkhơng cĩ thành phần nhỏ nhất.

3.2 Biểu vật Hasse.

Một trong mỗi cách thức trình diễn cho 1 mối quan hệ là người sử dụng các đồ thị lý thuyết (directed graph). Một đồ thị lăm le hướng bao gồm một tập thích hợp những đỉnh cùng theo với một tụ tập những cặp đỉnh được gọi là các cạnh (hay những cung). Đồ thị trình diễn cho 1 mối quan hệ 2 ngơi R trên một tụ tập X cĩ tụ tập những đỉnh đó là X, và tụ tập những cung chính là R. Nếu (a,b)  R thì bên trên biểu vật tớ vẽ một cung phía từ đỉnh a cho tới đỉnh b. Đồ thị lý thuyết ứng của một mối quan hệ hai ngơi bên trên một tụ tập tiếp tục cung ứng mang lại tớ những thơng tin tưởng về quan liêu hệ một cơ hội rất rất trực quan liêu. Do đĩ thõa người tớ thường được sử dụng những vật thị định phía nhằm nghiên cứu và phân tích những mối quan hệ và những đặc thù của bọn chúng.

Ví dụ: X =a,b,c,d, R =(a,d), (b,b), (b,d), (c,a), (c,b), (d,b). Đồ thị lý thuyết (X,R) cĩ thể được vẽ đi ra như sau:

Cạnh (b,b) được vẽ bên trên biểu vật vì thế cung khởi đầu từ đỉnh b và xoay quay về chủ yếu đỉnh b. Cạnh nầy được gọi là một “vịng” bên trên b.

Chúng tớ cĩ thể thấy rằng một mối quan hệ 2 ngơi bên trên một tụ tập là đối xứng Khi và chỉ Khi bên trên vật thị trình diễn ứng từng cặp đỉnh đều cĩ 2 cung nối theo đuổi 2 phía ngược nhau. Như vậy vật thị của quan hệ nhập ví dụ bên trên tớ Kết luận mối quan hệ nầy khơng cĩ tính đối xứng.

Đối với cùng 1 tụ tập X (hữu hạn) cĩ trật tự thì bên trên vật thị định hướng ứng cĩ nhiều cạnh khơng nhất thiết cần vẽ đi ra vì thế vì chúng được hiểu ngầm. Nĩi một cách tiếp, những đặc thù của quan hệ trật tự đỡ đần ta hiểu rằng cĩ những cạnh đương nhiên cĩ bên trên vật thị của quan liêu hệ; và những cạnh đĩ thõa tiếp tục khơng được vẽ đi ra bên trên vật thị. Trước không còn tớ thấy rằng bên trên từng đỉnh của vật thị cần cĩ một vịng do tính bản năng của mối quan hệ trật tự, nên những vịng nầy tiếp tục khơng được vẽ ra bên trên vật thị. Ngồi đi ra mối quan hệ trật tự cịn cĩ tính truyền, nên tớ sẽ khơng cần thiết vẽ đi ra cạnh (a,c) nếu như bên trên vật thị cĩ những cạnh (a,b) và (b,c) với b là 1 trong những đỉnh nào là đĩ thõa. Hơn nữa, nếu như (a,b), (b,c), và (c,d) là các cạnh thì tớ cũng loại đi ra cạnh (a,d). Chúng tớ cũng khơng ghi mũi tên định phía bên trên những cạnh với qui ước rằng : những đỉnh của vật thị được bố trí bên trên hình vẽ sao mang lại phía mũi thương hiệu của những cạnh là “hướng lên”.

Xem thêm: công thức tính sai số tuyệt đối

Như vậy vật thị lý thuyết (dạng biểu đồ) ứng của tụ tập cĩ thứ tự động (X,) cĩ thể được rút gọn gàng lại trở thành một biểu vật giản dị và đơn giản hơn nhưng vẫn hàm chứa chấp tương đối đầy đủ những thơng tin tưởng của trật tự  bên trên tập hợp X, bằng phương pháp là tớ chỉ vẽ cung nối kể từ đỉnh x cho tới đỉnh x' (x' khác x) Khi tớ cĩ xx', và khơng tồn bên trên nó không giống x và x' sao mang lại xy và y  x'. Biểu vật ở dạng rút gọn gàng nầy được gọi làbiểu vật Hasse của tập hợp cĩ trật tự (X,). Theo sự trình diễn phía trên tớ cĩ thể xây đắp một thuật tốn nhằm lần biểu vật Hasse của một tụ tập (hữu hạn) cĩ trật tự.

Ví dụ:

1. Xét trật tự thơng thông thường bên trên tụ tập X =1,2,3,4.

Đồ thị tương đối đầy đủ của (X, ) cĩ dạng nhập hình (a) sau đây. Hình (b) là dạng rút gọn gàng của vật thị, tức là biểu vật Hasse của thứ tự động  bên trên X.

2. Vẽ biểu vật Hasse trình diễn trật tự “chia hết”, được ký hiệu là , bên trên tập luyện hợp1,2,3,4,6,8,12.

Bắt đầu kể từ vật thị lý thuyết của trật tự nầy, tớ vô hiệu các vịng bên trên những đỉnh. Sau đĩ thõa vô hiệu những cạnh cĩ thể được suy ra bởi đặc thù truyền của trật tự : (1,4), (1,6), (1,8), (1,12), (2,8), (2,12) và (3,12). Cuối nằm trong tớ được biểu vật Hasse bao gồm các cạnh (1,2), (1,3), (2,4), (2,6), (3,6), (4,8), (4,12), và (6,12) :

3. Vẽ biểu vật Hasse mang lại trật tự trên tập luyện hợp

P

Cũng thực hiện tương tự động như nhập ví dụ trước tớ vô hiệu những cạnh sau trên đây kể từ vật thị trình diễn mang lại loại tự: (,a,b), (,a,c), (,b,c), (,a,b,c), (a,a,b,c), (b,a,b,c), và (c,a,b,c). Từ đĩ thõa tớ cĩ biểu vật Hasse được vẽ như sau :

Ghi chú :

Chúng tớ cịn cĩ một cách tiếp nhằm nêu lên định nghĩa biểu đồ Hasse cho 1 cấu hình trật tự (X,) bằng phương pháp thể hiện một khái niệm trội trực tiếp: Cho x  X, một thành phần nó  X được gọi là một trội thẳng của x nếu như và chỉ nếu như tớ cĩ 2 ĐK tại đây :

(1) xy (y là 1 trong những chận bên trên của x),

(2) Với từng z, nếu như xz và zy thì z = x hoặc z = nó.

Biểu vật Hasse mang lại cấu hình trật tự (X,) là 1 trong những vật thị lăm le hướng cĩ tụ tập đỉnh là X và tụ tập những cạnh là 1 trong những phần củagồm các cạnh (a,b) sao mang lại b là 1 trong những trội thẳng của a.

3.3 Tập thích hợp hữu hạn cĩ trật tự.

Trong mục nầy tất cả chúng ta tiếp tục trình diễn một số trong những thành quả liên quan đến những tụ tập hữu hạn cĩ trật tự (hay những cấu hình trật tự hữu hạn). Biểu vật Hasse là 1 trong những cơng cụ hiệu quả được sử dụng trong công việc khảo sát những trật tự bên trên những tụ tập hữu hạn.

Định lý 1.Cho (X,) là 1 trong những cấu hình trật tự hữu hạn. Ta cĩ : 1. Trong X cĩ tối thiểu một thành phần tối đái.

2. Nếu X cĩ một thành phần tối đái có một không hai thì thành phần đĩ thõa chính là thành phần nhỏ nhất của X.

Chứng minh:

Cho (X,) là 1 trong những cấu hình trật tự hữu hạn (nghĩa là X hữu hạn vàlà một trật tự bên trên X). Chọn một thành phần a0 X. Nếu a0 khơng cần là 1 trong những thành phần tối đái thì theo đuổi khái niệm của phần tử tối đái tớ cĩ một thành phần a1sao mang lại a1a0và a1a0.

Nếu a1 khơng cần là 1 trong những thành phần tối đái thì tớ lại cĩ một phần tử a2sao mang lại a2a1và a2a1. Cứ kế tiếp quy trình nầy để mang lại nếu như ankhơng tối đái thì tiếp tục cĩ một thành phần an+1sao cho an+1anvà an+1an. Do X chỉ cĩ một số trong những hữu hạn thành phần, nên quá trình bên trên cần ngừng so với một thành phần tối đái an. Như vậy nhập X cĩ tối thiểu một thành phần tối đái.

Giả sử X cĩ một thành phần tối đái có một không hai là m. Cho x là một phần tử tùy ý nằm trong X. Theo lập luận bên trên, tồn bên trên 1 phần tử tối đái ansao mang lại an x. Vì thành phần tối đái là có một không hai nên an = m. Suy đi ra m  x. Điều nầy minh chứng m là thành phần nhỏ nhất của X.

Theo dõi chứng tỏ của lăm le lý bên trên tớ rút đi ra một thuật tốn nhằm tìm một thành phần tối đái của một cấu hình hữu hạn.

Thuật tốn 1. Tìm thành phần tối đái nhập một cấu hình loại tự hữu hạn.

Nhập : X là 1 trong những tụ tập hữu hạn (khác rỗng), là một trật tự bên trên X.

Xuất : m là 1 trong những thành phần tối đái nhập X. Thuật tốn : 1. Chọn một thành phần mX 2. for xX do if xm and xm then mx (gán thành phần x mang lại phát triển thành m), và trở lại bước 1.

Nhận xét :

1. Qua chứng tỏ bên trên tớ thấy rằng với từng thành phần x X luơn tồn bên trên một thành phần tối đái m sao mang lại m  x (ở trên đây là một thứ tự động bên trên X).

2. Định lý bên trên tiếp tục khơng cịn trúng nếu như vứt đi ĐK hữu hạn của tụ tập X. Việc lần đi ra một ví dụ mang lại đánh giá nầy được dành mang lại phần bài xích tập luyện.

Ví du: Tìm thành phần tối đái của tụ tập cĩ loại tự (2,4,1,5,12,20,).

Aùp dụng thuật tốn bên trên tất cả chúng ta tiếp tục tìm kiếm được thành phần tối tiểu của cấu hình trật tự đang được mang lại là một trong.

Tương tự động như bên trên, so với những thành phần tối đại tớ cũng cĩ lăm le lý sau đây:

Định lý 2.

(1) Mọi tụ tập hữ hạn cĩ trật tự (X,) đều cĩ một thành phần tối đại. Hơn nữa, với từng x  X luơn tồn bên trên một thành phần tối đại M sao mang lại xM.

(2) Nếu X cĩ một thành phần tối đại có một không hai thì thành phần đĩ thõa chính là thành phần lớn số 1 của X.

Việc chứng tỏ lăm le lý bên trên và xây đựng thuật tốn nhằm lần phần tử tối đại được dành riêng cho phần bài xích tập luyện.

3.4 Sắp xếp topo (topological sorting)

Sắp xếp topo là 1 trong những yếu tố cần thiết trong công việc tham khảo các cấu trúc trật tự hữu hạn và cách thức bố trí topo thông thường được sử

dụng nhằm giải nhiều bài xích tốn thực tiễn. Chúng tớ demo coi bài xích tốn đặt ra như sau:

Giả sử cĩ một chủ đề bao gồm đôi mươi cơng việc không giống nhau. Một số cơng việc chỉ cĩ thể được triển khai sau thời điểm một số trong những cơng việc không giống được thực hiện hồn vớ. Chúng tớ cần triển khai những cơng việc theo đuổi trật tự nào? Để mơ hình mang lại yếu tố, tất cả chúng ta đặt điều X là tụ tập đôi mươi cơng việc của đề tài; bên trên X tớ xét một trật tự (hay mối quan hệ loại tự) sao mang lại a b nếu và chỉ nếu như a và b là 2 cơng việc nhập đĩ thõa cơng việc b chỉ cĩ thể được chính thức Khi cơng việc a và được hồn trở thành. Muốn cĩ một kế hoạch triển khai những cơng việc mang lại chủ đề tất cả chúng ta cần lần đi ra một thứ tự mang lại toàn bộ đôi mươi cơng việc “tương thích” với trật tự  nêu bên trên.

Trước không còn tất cả chúng ta nêu đi ra khái niệm định nghĩa “tương thích” như sau:

Định nghĩa:Cho (X,) là 1 trong những tụ tập cĩ trật tự. Một trật tự tồn phần trên X được gọi là tương mến với loại tự nếu như và chỉ nếu

ab  ab, với từng a,bX.

Việc xây đắp trật tự tồn phần tương mến với cùng 1 trật tự cho trước được gọi làsắp xếp topo(topological sorting).

Xem thêm: các đề thi vào lớp 10 môn toán

Thuật tốn bố trí topo cho 1 tụ tập hữu hạn cĩ trật tự dựa vào thành quả nêu trong những lăm le lý bên trên. Để khái niệm một trật tự tồn phần bên trên (X, ), trước không còn tớ lựa chọn ra một thành phần tối đái a1 của X; phần tử nầy tồn bên trên vì thế lăm le lý 1. Kế đĩ thõa, để ý rằng Nếu tụ tập X - a1   thì (X -a1,) cũng là 1 trong những tụ tập hữu hạn (khác rỗng) cĩ

thứ tự động. Ta lại lựa chọn ra thành phần tối đái a2 nhập X -  a1, rồi loại a2 khỏi việc kiểm tra ở bước tiếp theo sau nhằm lựa chọn thành phần tối đái nhập X - a1, a2 nếu như tụ tập X - a1, a2 không giống trống rỗng. Tiếp tục quy trình nầy bằng cơ hội lựa chọn thành phần tối đái ak+1trong X -a1, a2, ... , akkhi tập hợp cịn thành phần.

Vì X là 1 trong những tụ tập hữu hạn nên quy trình lựa chọn bên trên cần ngừng. Cuối cùng tớ đang được chuẩn bị những thành phần của tụ tập X trở thành một mặt hàng a1, a2, ... , an thỏa ĐK : với từng i, j sao mang lại i < j tớ cĩ ai  aj hoặc ai và aj