ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
HOÀNG CHÍ THÀNH
CÁC MÔ HÌNH
TƯƠNG TRANH
Hà Nội
2
MỞ ĐẦU
Mô tả, thiết kế và điều khiển hệ thống là các vấn đề chính cần đặt ra khi
chúng ta xây dựng một hệ thống nào đó và sử dụng nó trong thực tiễn. Lý thuyết
mạng là lý thuyết tổ chức hệ thống được C.A. Petri khởi xướng vào đầu thập
niên sáu mươi của thế kỷ trước trong Luận án Tiến sĩ của ông. Từ đó đến nay
các nhà tin học trên thế giới đã nghiên cứu phát triển nhiều mô hình mạng khác
nhau và ứng dụng chúng vào nhiều lĩnh vực khoa học khác nhau. Ưu điểm chính
của lý thuyết mạng là khả năng nhận biết và biểu diễn sự tương tranh, an toàn,
xung đột, sống, tắc nghẽn , cung cấp kỹ thuật phân tích và thiết kế hệ thống và
cảnh báo sự hữu hạn của các tài nguyên của hệ thống.
Bên cạnh lý thuyết mạng nhiều mô hình biểu diễn tương tranh khác đã ra
đời. Một số mô hình dựa trên ngôn ngữ hình thức như: ngôn ngữ vết của A.
Mazurkiewicz, ngôn ngữ CSP của C.A.R. Hoare, ngôn ngữ CCS của R. Milner,
ngôn ngữ COSY của P. Lauer, ngôn ngữ nửa vết của H.C. Thành Công cụ đại
số cũng được sử dụng để biểu diễn tương tranh. Từ đó ra đời: đại số các quá
trình của V.E. Kotov và của J.A. Bergstra, cấu trúc biến cố của G. Winskel
Do khuôn khổ của chuyên đề, chúng tôi chỉ chọn lựa một số mô hình tiêu
biểu nhất để đưa vào các bài giảng với mục tiêu giúp người học nắm bắt được
các khái niệm mới, kỹ thuật cơ bản và ứng dụng chúng vào các vấn đề thực tiễn
như: hệ thống thông tin, cơ sở dữ liệu, thiết kế mạch lôgic, kiến trúc máy tính,
lập trình song song, công nghệ phần mềm, điều khiển hệ thống
Cuốn sách là nội dung chuyên đề dành cho học viên cao học và nghiên
cứu sinh chuyên ngành Tin học, Công nghệ Thông tin, Đảm bảo Toán học cho
Máy tính và Các hệ thống tính toán mà tác giả đã giảng dạy nhiều năm tại

tiết. Việc chế tạo từng chi tiết không phụ thuộc vào nhau. Việc lắp ráp thì thực
hiện tuần tự: trước tiên lắp ráp hai chi tiết đầu sau đó lắp thêm chi tiết thứ ba.
Hình 1.1. Quy trình tổ chức chế tạo và lắp ráp song song một thiết bị
4
Ta có thể đưa quá trình sản xuất thiết bị trên về một hệ thống tương tranh như
sau: chế tạo đồng thời hai chi tiết 1 và 2, việc lắp ráp hai chi tiết 1 và 2 đồng thời
với việc chế tạo chi tiết thứ ba, cuối cùng lắp ráp thêm chi tiết 3.
Như vậy, trong hệ thống sản xuất này việc chế tạo chi tiết 1 và việc chế
tạo chi tiết 2 là tương tranh với nhau. Chúng chỉ có thể được thực hiện đồng thời
nếu không tranh chấp các máy móc
Quá trình sản xuất một sản phẩm có thể biểu diễn ngắn gọn bằng sơ đồ sau:
1  2 ; 3  4 ; 5
Với việc tổ chức sản xuất như trên, ta thấy ngay các lợi ích sau đây:
1) Các chi tiết kỹ thuật được chế tạo trên các máy khác nhau, việc chế tạo
đồng thời có thể xoá bỏ thời gian chết của các máy.
2) Giảm thời gian chế tạo ra một sản phẩm.
Ví dụ 1.2: Tính giá trị của một biểu thức toán học
Giả sử ta cần phải tính giá trị của biểu thức sau đây:
A * B - (C + D) / (E - F)
Hình 1.2. Tổ chức tính toán song song một biểu thức
Sơ đồ tính toán giá trị biểu thức như trên giống như sơ đồ quá trình sản
xuất trong Ví dụ 1.1. Nếu máy tính có ít nhất hai bộ xử lý thì quá trình tính giá
trị biểu thức sẽ nhanh hơn nhiều.
Ví dụ 1.3: Chu trình xử lý
Xét chu trình tính toán được viết trên ngôn ngữ lập trình Pascal sau đây:
for i := 1 to 100 do
if A[i] > 0 then A[i] := A[i] + 1
else A[i] := 0 ;
5
100 lệnh if trên có thể được thực hiện đồng thời nếu máy tính có trên 100

1.3 Sơ lược về các mô hình biểu diễn tương tranh
1) Mô hình đầu tiên để biểu diễn hệ tương tranh được đề xuất bởi C.A.
Petri (Đức) vào năm 1962 trong Luận án Tiến sĩ của ông. Đó là mạng Petri.
Nếu otomat hữu hạn chỉ mô tả được các hệ thống tuần tự thì mạng Petri,
một công cụ toán học được phát triển trên cơ sở của otomat hữu hạn, mô tả được
các hệ thống không tuần tự mà trong đó có các hệ thống tương tranh.
Hiện nay mạng Petri vẫn được nghiên cứu phát triển mạnh mẽ cả về lý
thuyết lẫn ứng dụng [5,7,10,11]. Đã có hơn mười loại mạng khác nhau và được
áp dụng vào rất nhiều lĩnh vực.
2. Ngôn ngữ vết (trace language) do A. Mazurkiewicz (Ba Lan) đưa ra
vào năm 1977. Đây là một ngôn ngữ được phát triển từ ngôn ngữ hình thức để
mô tả hành vi của các hệ tương tranh [1].
3. CSP (Communicating Sequential Processes) là một ngôn ngữ để biểu
diễn các hệ tương tranh [3] do C.A.R. Hoare (Anh) đưa ra vào năm 1978.
4. CCS (Calculus of Communicating Systems) được R. Milner (Anh) xây
dựng vào năm 1980 như một công cụ toán học rõ ràng và tổng quát về tương
tranh và được thể hiện như một ngôn ngữ lập trình [4].
Ngoài những mô hình kể trên, các hệ tương tranh còn được mô tả bằng
các mô hình sau đây:
- Đại số các quá trình (Algebra of Processes) của J.A. Bergstra (Hà Lan)
7
- COSY (COncurent SYstem) do P. Lauer (Canada) đề xuất
- Cấu trúc biến cố (Event Structure) của G. Winskel (Đức),
và nhiều mô hình khác.
Một số nhóm nghiên cứu các hệ tương tranh trên thế giới:
Hệ tương tranh được nhiều nhà khoa học trên thế giới nghiên cứu và phát
triển tại các trường đại học và các viện nghiên cứu.
- Tại Đại học Bonn (Đức), nơi ra đời của mạng Petri, có một nhóm các
nhà khoa học có tên tuổi như: C.A. Petri, E. Best, W. Reisig, W.
Brauer, U. Goltz… phát triển nhiều mô hình khác nhau của mạng

Hội thảo khoa học hàng năm toàn thế giới về tương tranh (CONCUR)
được tổ chức tại nhiều trung tâm nghiên cứu trên khắp các châu lục đã thu hút sự
chú ý của nhiều người về Lý thuyết Tương tranh. Nhiều kết quả nghiên cứu lý
thuyết và ứng dụng của hệ tương tranh đã được trình bày tại hội thảo này.
9
Chương 2
MẠNG PETRI
2.1 Ví dụ về mạng Petri
Chúng ta nghiên cứu việc tổ chức cho mượn sách và nhận trả lại sách ở
một thư viện.
Hình 2.1. Cấu trúc đơn giản của một thư viện
Đây là cấu trúc đơn giản của một thư viện. Bạn đọc có thể truy nhập vào thư
viện thông qua ba bàn: bàn yêu cầu, bàn nhận sách và bàn trả sách. Trong thư
viện tất cả các sách đều được để trên giá và mỗi cuốn sách có một thẻ mục.
a) Bạn đọc yêu cầu: Nếu cuốn sách có trong thư viện thì thủ thư lấy sách,
thẻ mục của cuốn sách đó được cập nhật và bạn đọc nhận sách tại bàn
nhận sách.
b) Bạn đọc trả sách: Thẻ mục của sách được cập nhật và sách được đặt trở
lại giá.
Làm mịn sơ đồ thư viện trên bằng cách thêm vào hai bộ phận làm việc là:
“cho mượn sách” và “nhận lại sách” và hai thành phần thụ động là “kho sách”
và “hộp thẻ mục sách đã mượn”. Khi đó ta có sơ đồ mới chi tiết hơn của một
thư viện như dưới đây:
Hình 2.2. Sơ đồ tổ chức đầy đủ của một thư viện
10
Đây là một ví dụ về mạng Petri.
2.2 Các khái niệm cơ sở
2.2.1 Mạng Petri
Định nghĩa 2.1:
Bộ ba N = (S, T; F) được gọi là một mạng Petri nếu:


Chú ý rằng, với cặp phần tử x, y  N ta có:
x 

y  y  x

ii) Cặp (s, t)  S  T được gọi là một nút (self-loop) nếu (s, t)  F và (t, s)  F.
Mạng N được gọi là tinh khiết (pure) nếu quan hệ lưu đồ F không chứa
một nút nào.
iii) Phần tử x  N được gọi là cô lập nếu

x  x

= .
iv) Mạng N được gọi là đơn giản (simple) nếu và chỉ nếu các phần tử khác nhau
không có chung tập vào và tập ra, nghĩa là:
x, y  N : (

x =

y )  ( x

= y

)  x = y.
11
Ví dụ 2.2: Xét mạng Petri được cho dưới dạng đồ thị dưới đây.
Hình 2.3. Biểu diễn đồ thị của một mạng Petri
Mạng ở ví dụ trên là đơn giản, không tinh khiết và không có phần tử cô lập.
2.2.2 Các mạng Petri đẳng cấu

nào đó thoả mãn, số còn lại thì không.
Tập các điều kiện được thoả mãn trong một hình trạng được gọi là một
trường hợp (case). Biến cố e có thể xuất hiện trong trường hợp c nếu và chỉ nếu
các điều kiện vào của e thoả mãn trong c còn các điều kiện ra thì không. Khi biến
cố e xuất hiện, các điều kiện vào của e không thoả mãn nữa còn các điều kiện ra
của e bắt đầu thoả mãn.
Vì các S-phần tử và T-phần tử được thể hiện như các điều kiện và các biến
cố nên ta ký hiệu mạng Petri là (B, E; F) thay cho (S, T; F).
Định nghĩa 3.1: Giả sử N = (B, E; F) là một mạng Petri.
1) Tập con c  B được gọi là một trường hợp hay một trạng thái.
2) Giả sử e  E và c  B. Ta nói rằng e là kích hoạt được trong c (hay e là c-
kích hoạt) nếu và chỉ nếu

e  c và e

 c = .
3) Giả sử e  E , c  B và e là kích hoạt được trong c. Khi đó, c' = (c \

e) 
e

được gọi là trường hợp kế tiếp của c (c’ là kết quả của sự xuất hiện của
biến cố e trong trường hợp c).
Và ta viết: c [ e > c'.
Một biến cố của hệ mạng có thể xảy ra nếu trong hệ có trạng thái làm thoả
mãn các điều kiện trước (tập vào) của biến cố đó và khi ấy các điều kiện sau (tập
ra) của biến cố này chưa thoả mãn. Khi biến cố xảy ra, các điều kiện trước không
thoả mãn nữa và các điều kiện sau được thoả mãn. Trạng thái kế tiếp nhận được
sau khi biến cố trên xảy ra phải thuộc không gian các trạng thái để có thể kích
hoạt các biến cố khác. Không gian các trạng thái của hệ thống là môi trường để

=

e
1
 e

2
= e

1


e
2
= e

1
 e

2
= .
2) Giả sử c và c' là các trường hợp của mạng N và tập con các biến cố G là
tách được. G được gọi là một bước từ c tới c' nếu và chỉ nếu mỗi biến cố e
trong G là c-kích hoạt và c' = (c \

G)  G

.
Khi đó, ta cũng ký hiệu là: c [ G > c'.
Bước G đã dẫn từ trường hợp c tới trường hợp c'. Hiển nhiên, nếu G chỉ

= (c 

G)  (c \ G

)
= c 

G vì c \ G

= c
=

G vì

G  c.
c' \ c = ((c \

G)  G

) \ c
= ((c \

G) \ c)  (G

\ c)
=   (G

\ c)
= G


Không chỉ {e
1
,e
2
} mà {e
2
,e
3
} cũng tạo nên một bước.
Khi thay thế các trường hợp, bước tiếp theo bước sinh ra các quá trình.
Nếu bước hữu hạn thì nó có thể được thể hiện bởi sự xuất hiện của các biến cố
của nó theo thứ tự tuỳ ý. Do vậy, các biến cố trong một bước hữu hạn có thể thực
hiện đồng thời với nhau.
Bổ đề 3.2: Giả sử N = (B, E; F) là một mạng Petri, c
1
, c
2
là các trường hợp của
mạng N và G là một bước hữu hạn dẫn c tới c'. Giả sử G = {e
1
, e
2
, … , e
k
} và
< e
1
, e
2
, … , e


e
j
= e

i
 e

j
= e

i


e
j
=

e
i
 e

j
= .
Khi đó nếu c [ e
i
> c' thì

e
j

Hình 3.2. Tình trạng xung đột
Trong mạng trên với trường hợp được chỉ ra (các điều kiện tô màu) nếu e
1
xuất hiện trước e
2
thì không có xung đột giữa e
1
và e
3
, còn nếu e
2
xuất hiện trước
e
1
thì xảy ra xung đột. Do không có thứ tự xác định trước giữa e
1
và e
2
nên tình
trạng này được gọi là mập mờ.
3.2 Hệ mạng điều kiện - biến cố
Một mạng Petri bao gồm các điều kiện và các biến cố chưa đủ để mô tả hệ
thống. Vì vậy ngoài mạng ta phải thêm vào các trường hợp mà ta muốn xét.
Tập các trường hợp C này phải thoả các tính chất sau đây:
1. Nếu tập G  E là một bước được kích hoạt bởi trường hợp c  C thì G
dẫn tới một trường hợp khác cũng thuộc C. Như vậy, các bước không
được dẫn ra ngoài C.
2. Ngược lại, nếu trường hợp c  C là kết quả của bước G  E thì tình
huống mà ta đi từ đó cũng phải là một trường hợp thuộc C. Hay nói một
cách khác, nếu ta quay trở lại tìm trường hợp trước thì ta chỉ cần tìm

 r

-1
)
*
, trong đó quan hệ r


P(B)  P(B) được định nghĩa như sau:
(c
1
, c
2
)  r

 G  E : c
1
[ G > c
2
.
C được gọi là không gian các trường hợp của hệ .
3) e  E , c  C để e kích hoạt được trong c.
Ví dụ 3.6: Cho mạng Petri:
Hình 3.3. Cấu trúc tĩnh của một hệ mạng điều kiện - biến cố
Lấy c
0
= {b
1
}. Khi đó không gian C = {{b
1

và theo định nghiã thì phải
có c, c'  C mà c [ e > c' và vì b  c  c'.
4) Biến cố trong chu trình hẹp không bao giờ được kích hoạt.
Ví dụ 3.7: Bài toán sắp đặt lại các tập hợp.
Cho hai tập không rỗng, hữu hạn, rời nhau A và B. Sắp đặt lại các phần tử
trong tập A  B thành hai tập A' và B' sao cho |A'| = |A|, |B'| = |B| và max (A) <
min (B).
Chương trình tương tranh giải bài toán trên được biểu diễn bởi hệ mạng
điều kiện - biến cố sau đây:
Hình 3.4. Chương trình tương tranh cho bài toán sắp đặt lại các tập hợp
Định lý 3.4: Giả sử  là một hệ mạng điều kiện - biến cố.
Giả sử quan hệ
r
 P(B)  P(B) được định nghĩa như sau:
(c
1
, c
2
) 
r
 e  E : c
1
[ e > c
2
.
Nếu tập các biến cố E hữu hạn thì R

= (
r


r
-1
)
*
. Từ đây suy ra: R


R
.
18
Giả sử  = (B, E; F, c
0
) là một hệ mạng điều kiện - biến cố. Các trường
hợp trong không gian các trường hợp kích hoạt liên tiếp các biến cố cho ta một
dãy hành động xảy ra trên hệ. Chẳng hạn,
c
1
[e
1
> c
2
[e
2
> c
3
[e
3
> c
4
c

1
e
2
e
n
được gọi là từ sinh bởi hệ mạng . Ngôn ngữ sinh bởi
hệ mạng điều kiện - biến cố , ký hiệu bởi L(), là tập tất cả các từ sinh bởi hệ
mạng này.
L() = { = e
1
e
2
e
n
|  c
1
, c
2
, c
n+1
 C

,  e
1
, e
2
, e
n
 E


3.3 Hệ chu trình và hệ sống
Những yêu cầu đặt ra cho không gian các trường hợp C của hệ mạng điều
kiện - biến cố  sẽ rõ ràng hơn bằng cách thể hiện được rằng C là tập tất cả các
trường hợp kế tiếp của một trường hợp ban đầu nào đó. Nếu mọi trường hợp của
 đều được tái sản xuất thì mỗi một không gian các trường hợp như thế sẽ trùng
với tập C.
Định nghĩa 3.8:
Hệ mạng điều kiện - biến cố  được gọi là chu trình nếu và chỉ nếu:
c
1
, c
2
 C : (c
1
, c
2
)  r

*
.
Định lý 3.5: Giả sử  là một hệ mạng điều kiện - biến cố chu trình và c là một
trường hợp nào đó trong không gian C. Thế thì: C = {c'  (c, c')  r

*
} .
Chứng minh:
Vì hệ  là chu trình nên r

-1
 r

Định nghĩa 3.11: Giả sử  và ' là hai hệ mạng điều kiện - biến cố.
1) Giả sử có hai song ánh  : C

 C
’
và  : E

 E
’
.
- Hai hệ  và ' được gọi là (,)-tương đương nếu và chỉ nếu:
c
1
, c
2
 C

, G  E

: c
1
[ G > c
2
 (c
1
) [ (G) > (c
2
).
- Hai hệ  và ' được gọi là tương đương nếu và chỉ nếu chúng là (,)-
tương đương đối với cặp song ánh (,) nào đó và ta ký hiệu:   '.

– xuân hoặc hạ
s
2
– xuân hoặc thu
s
3
– hạ hoặc thu.
Tập các trường hợp C' : {s
1
, s
2
} = xuân , {s
1
, s
3
} = hạ ,
{s
2
, s
3
} = thu ,  = đông.
Định lý 3.9: Giả sử  và ' là hai hệ mạng điều kiện - biến cố tương đương.
1. Hệ  là chu trình  hệ ' là chu trình.
2. Hệ  là sống  hệ ' là sống.
Hệ mạng điều kiện - biến cố tuần tự với các trường hợp bao gồm chỉ một
điều kiện tương ứng với các otomat hữu hạn. Với hai hệ như thế sự tương đương
trùng với sự đẳng cấu.
Bổ đề 3.10: Giả sử  và ' là hai hệ mạng điều kiện - biến cố mà: c  C



Giả sử (b, e)  F

. Thế thì biến cố e là {b} -kích hoạt. Vậy (e) là ({b})
-kích hoạt và ('(b), '(e))  F
’
.
Chứng minh một cách tương tự thì từ (e, b)  F

suy ra ('(e), '(b))  F
'
.
Điều ngược lại là hiển nhiên.
3.5 Hệ mạng điều kiện - biến cố an toàn
Trong phần 3.1 chúng ta đã chỉ ra rằng biến cố sẽ không được kích hoạt
trong tình trạng không an toàn. Tình trạng như thế có thể loại trừ được nhờ một
phép biến đổi tương đương trên các hệ mạng điều kiện - biến cố. Để làm việc
này, ta thêm cho mỗi điều kiện b một điều kiện bù

b
của nó sao cho trong mỗi
trường hợp của hệ thì hoặc b hoặc

b
được thoả mãn.
Định nghĩa 3.13: Giả sử  là hệ mạng điều kiện - biến cố và b, b' là các điều
kiện trong B

.
1. Điều kiện b' được gọi là bù của điều kiện b khi và chỉ khi


: hoặc b  c hoặc
b
 c.
Nếu hệ  là đầy đủ thì:
4) e  E

: |

e| = |e

|.
5) c  C

: |c| =
2
1
|B

|.
Chứng minh:
1) Suy từ tính đơn giản của hệ .
2) Suy từ định nghĩa của điều kiện bù.
22
3) Điều này đúng vì trong trường hợp ngược lại thì các biến cố liên quan không
thể được kích hoạt trong bất kỳ một trường hợp nào và mâu thuẫn với định nghĩa
của hệ mạng điều kiện - biến cố.
4) Suy từ định nghĩa của điều kiện bù.
5) Suy từ 3).
Ví dụ 3.14: Cách xây dựng điều kiện bù.
Hỉnh 3.7. Điều kiện b và bù của nó


; F

 F, (C

))
được gọi là đầy đủ của hệ .
Hiển nhiên, mỗi điều kiện b trước đây không có bù trong hệ  thì nay đã
có bù trong hệ


.
Định lý 3.12: Giả sử  là hệ mạng điều kiện - biến cố và trường hợp c  C

.
1.


=


2. b  B

, c  C

: b  (c) 
b
 (c).
3. c = (c)  B


 b  B  b  G

} và
G
–
= G

 {
b
b  B  b 

G }
b)

G =
–
G  B

, G

= G
–
 B

.
Bây giờ ta chỉ ra rằng việc làm đầy đủ một hệ mạng điều kiện - biến cố sẽ
cho ta một hệ mạng điều kiện - biến cố an toàn tương đương.
Định lý 3.15: Nếu hệ



1
\ c
2
=

G  c
2
\ c
1
= G

)  ((c
1
) \ (c
2
) =
–
G  (c
2
) \ (c
1
) = G
–
).
Chứng minh mệnh đề  :
Theo Định lý 3.12 và 3.14 ta có:
c
1
= (c
1

) \ ((c
2
)  B

) = ((c
1
) \ ((c
2
))  B

) =
–
G  B

=

G.
Tương tự ta có: c
2
\ c
1
= G

.
Chứng minh mệnh đề ngược lại  :
Giả sử tập B là tập các điều kiện không có bù của hệ  và:

B
1
= {

1
) \ (c
2
) = (c
1


B
1
) \ (c
2


B
2
)
= (c
1
\ (c
2


B
2
))  (

B
1
\ (c
2

= 
=

G  ({
b
b  B \ c
1
} \ {
b
b  B \ c
2
})
=

G  {
b
b  (B \ c
1
)  b  (B \ c
2
)}
=

G  {
b
b  B  b  c
1
 b  c
2
}

hợp c  C

:
1.

e  c  e

 B

\ c , nghĩa là e

 c = .
2. e

 c 

e  B

\ c , nghĩa là

e  c = .
Chú ý rằng, trong định nghĩa trên mệnh đề 2. không phải bao giờ cũng suy
được từ mệnh đề 1. Chẳng hạn, xét hệ đơn giản sau đây:
Hình 3.8. Một hệ mạng đơn giản
Định lý 3.16:
1) Mọi hệ mạng điều kiện - biến cố đầy đủ là an toàn.
2) Mỗi hệ mạng điều kiện - biến cố đều có một hệ mạng an toàn tương đương.
3) Nếu hệ  là an toàn thì: e  E

:

\ c). Do vậy:

e  c.
2) Hệ


chính là hệ đầy đủ, an toàn tương đương cần tìm.
3) Giả sử rằng e

= . Thế thì

e   vì e không cô lập. Khi đó, c  C

mà

e  c. Vì e

 B

\ c nên mâu thuẫn với giả thiết e

= .
Chứng minh tương tự cho trường hợp

e = .
Hiển nhiên, không phải mọi hệ mạng điều kiện - biến cố an toàn nào cũng
đầy đủ.
25
3.6 Đồ thị các trường hợp
Để có cái nhìn đầy đủ tất cả các bước của một hệ mạng điều kiện - biến

: (c, c')  r

*
 c, c'  C

, G
1
, G
2
, … G
n
  , c
0
, c
1
, … c
n
 C

:
c = c
0
[G
1
> c
1
[G
2
> c
2

Hệ mạng điều kiện - biến cố  là sống 
c  C

, e  E

, c', c"  C

: (c, c')  r

*
 c' [e > c" 
Tồn tại đường đi < c G
1
c
1
… c
n-1
G
n
c
n
> mà c
n-1
= c' , G
n
= {e} và c
n
= c".
Đó chính là điều phải chứng minh.
Ví dụ 3.18: