Tài liệu Luận văn một số thuật toán tìm đường đi dài nhất trên đồ thị

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 Thạch Thị Quỳnh Anh MỘT SỐ THUẬT TOÁN TÌM ĐƯỜNG ĐI DÀI NHẤT TRÊN ĐỒ THỊ LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Toán Ứng dụng HÀ NỘI, 2018 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 THẠCH THỊ QUỲNH ANH MỘT SỐ THUẬT TOÁN TÌM ĐƯỜNG ĐI DÀI NHẤT TRÊN ĐỒ THỊ LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Toán Ứng dụng Mã số: 8 46 01 12 Người hướng dẫn khoa học: TS. TRẦN VĨNH ĐỨC HÀ NỘI, 2018 1 LỜI CẢM ƠN Lời đầu tiên của luận văn tôi xin bày tỏ lòng biết ơn chân thành và sâu sắc nhất tới thầy giáo hướng dẫn TS. Trần Vĩnh Đức, người thầy đã định hướng chọn đề tài và tận tình hướng dẫn, giúp đỡ tôi trong suốt quá trình làm và hoàn thiện luận văn này. Tôi cũng xin bày tỏ lòng biết ơn chân thành tới Phòng Sau đại học, các thầy cô giáo giảng dạy chuyên ngành Toán Ứng dụng, Trường Đại học Sư phạm Hà Nội 2 đã giúp đỡ tôi trong suốt quá trình học tập tại trường. Nhân dịp này tôi cũng xin gửi lời cảm ơn đến gia đình, bạn bè luôn cổ vũ, động viên, giúp đỡ tôi trong suốt quá trình học tập và hoàn thiện luận văn này. Hà Nội, ngày 16 tháng 10 năm 2018 Tác giả luận văn THẠCH THỊ QUỲNH ANH 2 LỜI CAM ĐOAN Tôi xin cam đoan, dưới sự hướng dẫn của thầy giáo TS. Trần Vĩnh Đức, luận văn chuyên ngành Toán Ứng dụng với đề tài: "Một số thuật toán tìm đường đi dài nhất trên đồ thị" được hoàn thành bởi sự nhận thức và tìm hiểu của bản thân tác giả. Trong quá trình nghiên cứu và thực hiện luận văn, tác giả đã kế thừa những kết quả của các nhà khoa học với sự trân trọng và biết ơn. Hà Nội, ngày 16 tháng 10 năm 2018 Tác giả luận văn THẠCH THỊ QUỲNH ANH 3 Mục lục LỜI CẢM ƠN 1 LỜI CAM ĐOAN 2 MỞ ĐẦU 5 Chương 1. Kiến thức chuẩn bị 7 1.1 Một số khái niệm cần thiết trên đồ thị . . . . . . . . . . 7 1.2 Độ phức tạp thuật toán . . . . . . . . . . . . . . . . . . 11 1.3 Bài toán đường đi dài nhất trên đồ thị . . . . . . . . . . 14 Chương 2. Một số kết quả thu được về việc xấp xỉ bài toán đường đi dài nhất trên đồ thị 16 2.1 Đặt vấn đề . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2 Thuật toán tìm đường đi dài trên đồ thị . . . . . . . . . 18 2.3 Đồ thị bền với đường đi ngắn . . . . . . . . . . . . . . . 20 2.4 Tìm đường đi dài nhất trong những đồ thị ngẫu nhiên thưa thớt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.5 Kết luận về độ khó . . . . . . . . . . . . . . . . . . . . . 28 2.5.1 Kết quả về độ khó của đồ thị Hamilton . . . . . . 28 2.5.2 Tính chất hệ cải thiện và kết quả về độ khó của bài toán đường đi dài nhất . . . . . . . . . . . . . . . 29 4 Chương 3. Thuật toán thời gian đa thức cho bài toán đường đi dài nhất trên một số lớp đồ thị đặc biệt 38 3.1 Bài toán đường đi dài nhất trên đồ thị khoảng . . . . . . 38 3.1.1 Đồ thị khoảng . . . . . . . . . . . . . . . . . . . . 38 3.1.2 Tính có cấu trúc của đồ thị khoảng . . . . . . . . . 39 3.1.3 Đường đi dài nhất trên đồ thị khoảng . . . . . . . 42 3.2 Bài toán đường đi dài nhất trên đồ thị hoán vị . . . . . . 47 3.2.1 Đồ thị hoán vị . . . . . . . . . . . . . . . . . . . . 47 3.2.2 Bài toán đường đi dài nhất trên đồ thị hoán vị . . 48 KẾT LUẬN 51 TÀI LIỆU THAM KHẢO 52 5 MỞ ĐẦU 1. Lý do chọn đề tài Do sự phát triển với tốc độ nhanh của công nghệ thông tin, lý thuyết đồ thị đã trở thành một trong những lĩnh vực toán học quan trọng và cần thiết. Trên thực tế, lý thuyết đồ thị tỏ ra là một mô hình hữu hiệu cho mô hình hóa các bài toán tính toán và tối ưu tổ hợp. Bài toán đường đi dài nhất là một trong những bài toán cơ bản nhất của lí thuyết đồ thị. Nó có nhiều ứng dụng trong thực tế như trong lập kế hoạch, tự động hóa thiết kế điện tử, việc tìm kiếm các con đường quan trọng trong mạch IC hoặc hệ thống VLSI. Khác với bài toán đường đi ngắn nhất, là bài toán giải được trong thời gian đa thức, bài toán đường đi dài nhất là NP-khó vì nó chứa bài toán đường đi Hamilton như một trường hợp riêng, và do đó không thể giải được trong thời gian đa thức trừ phi P= NP. Để vượt qua khó khăn này, một số hướng nghiên cứu đã được đề xuất: 1. Dùng thuật toán xấp xỉ thời gian đa thức 2. Giải bài toán cho một vài lớp đồ thị cụ thể Với mong muốn tìm hiểu sâu hơn về bài toán đường đi dài nhất và các phương pháp giải nó, được sự hướng dẫn của TS Trần Vĩnh Đức, tôi chọn đề tài “ Một số thuật toán tìm đường đi dài nhất trên đồ thị“ . 2. Mục đích nghiên cứu a. Hướng giải xấp xỉ cho bài toán đường đi dài nhất. b.Thuật toán giải bài toán đường đi dài nhất trên một số lớp đồ thị đặc biệt. 6 3. Nhiệm vụ nghiên cứu Một số kết quả xấp xỉ thu được cho bài toán đường đi dài nhất trên đồ thị, và thuật toán giải bài toán đường đi dài nhất trên một số lớp đồ thị đặc biệt. 4. Đối tượng và phạm vi nghiên cứu - Đối tượng nghiên cứu: Bài toán đường đi dài nhất trên đồ thị. - Phạm vi nghiên cứu: + Giải xấp xỉ bài toán đường đi dài nhất. + Thuật toán thời gian đa thức để giải bài toán đường đi dài nhất trên đồ thị khoảng và đồ thị hoán vị. . 5. Phương pháp nghiên cứu Sử dụng các kết quả gần đây về việc giải xấp xỉ bài toán đường đi dài nhất. . Hà Nội, ngày 16 tháng 10 năm 2018 Tác giả luận văn THẠCH THỊ QUỲNH ANH 7 Chương 1 Kiến thức chuẩn bị Trong chương này chúng ta sẽ nhắc lại một số khái niệm và một số kết quả cần thiết để bổ trợ cho các chương sau. 1.1 Một số khái niệm cần thiết trên đồ thị Trước hết, chúng ta nhắc lại một số khái niệm cơ sở của lí thuyết đồ thị. Định nghĩa 1.1. Một đồ thị vô hướng G là một cặp có thứ tự G = (V, E), ở đây V là một tập còn E là một đa tập gồm các tập lực lượng 2 trên V. Các phần tử của V được gọi là các đỉnh, còn các phần tử của E được gọi là các cạnh của đồ thị vô hướng G. Nếu e = {u, v} ∈ E thì các đỉnh u, v được gọi là các đầu mút của cạnh e hay các đỉnh liên thuộc với e. Khi đó, hai đỉnh u, v được gọi là kề nhau hay láng giềng của nhau. Ta cũng thường kí hiệu cạnh {u, v} ngắn gọn là uv . Định nghĩa 1.2. Cho v là một đỉnh của đồ thị G. Bậc của đỉnh v trong G, kí hiệu là degG (v), được định nghĩa bởi số các cạnh của G liên thuộc v , tức số tất cả các láng giềng của v trong G. 8 Hình 1.1: Đồ thị G Đồ thị có thể vẽ trên mặt phẳng với các đỉnh là các điểm và các cạnh nối là các đường thẳng hoặc đường cong nối các điểm này. Đây là một trong những ưu điểm của lý thuyết đồ thị. Nó cho phép mô tả các lập luận và chứng minh theo cách rất trực quan và sáng sủa. Ví dụ 1.1. Cho đồ thị G = (V, E) với V = {u1 , u2 , u3 , u4 , u5 } và E = {(u1 , u3 ), (u1 , u4 ), (u1 , u5 ), (u2 , u4 ), (u3 , u5 )} Đồ thị này được vẽ như hình 1.1. Trong đồ thị này, cạnh a có hai đỉnh liên thuộc là u1 và u3 . Đỉnh u1 có 3 láng giềng là u3 , u4 , u5 nên degG (u1 ) = 3. Định nghĩa 1.3. Đồ thị G0 = (V 0 , E 0 ) được gọi là đồ thị con của đồ thị G = (V, E) nếu V 0 ⊆ V và E 0 ⊆ E . Khi E 0 chứa tất cả các cạnh của G mà hai đỉnh liên thuộc với nó đều thuộc V 0 thì G0 được gọi là đồ thị con cảm sinh bởi G trên tập đỉnh V 0 , kí hiệu G0 = G[V 0 ]. Hình 1.2: Một đồ thị con của G 9 Ví dụ 1.2. Hình 1.2 cho một đồ thị con của đồ thị G trong ví dụ 1.1 Định nghĩa 1.4. Cho đồ thị G = (V, E). Một đường đi L trong G là một dãy các đỉnh khác nhau sao cho hai đỉnh kế tiếp nhau của L đều kề nhau trong G. Đường đi có đỉnh đầu trùng với đỉnh cuối được gọi là chu trình. Ví dụ 1.3. Xét đồ thị G trong hình 1.1. Dãy u3 u1 u4 u5 là một đường đi trong G. Dãy u1 u3 u5 u1 là một chu trình trong G. Định nghĩa 1.5. Đồ thị vô hướng G = (V, E) được gọi là liên thông nếu luôn tìm được đường đi giữa hai đỉnh bất kì của nó. Trong trường hợp ngược lại, đồ thị được gọi là không liên thông. (a) Đồ thị không liên thông (b) Đồ thị liên thông Hình 1.3: Đồ thị không liên thông và đồ thị liên thông Ví dụ 1.4. Một đồ thị không liên thông và một đồ thị liên thông được cho trong hình 1.3. Định nghĩa 1.6. Đường đi qua tất cả các đỉnh của đồ thị được gọi là đường đi Hamilton. Chu trình đi qua tất cả các đỉnh của đồ thị gọi là chu trình Hamilton. Đồ thị có chứa chu trình Hamilton được gọi là đồ thị Hamilton. 10 Ví dụ 1.5. Xét đồ thị G được cho trong hình 1.1, dãy u2 u4 u1 u3 u5 là đường đi Hamilton. Đồ thị này không có chu trình Hamilton. Định nghĩa 1.7. Một đồ thị liên thông không có chu trình được gọi là cây. Cây (có gốc) là cây trong đó có một đỉnh được chọn là gốc và mỗi cạnh được định hướng trùng với hướng đi của đường đi duy nhất từ gốc tới mỗi đỉnh. Trong một cây có gốc, nếu có một cạnh đi từ đỉnh x đến đỉnh y thì đỉnh x được gọi là cha của đỉnh y, y là con của x. Hai đỉnh cùng cha được gọi là anh em, đỉnh không có con được gọi là lá, nói cách khác, lá chính là đỉnh có bậc 1. Số cạnh trên đường đi từ gốc tới mỗi đỉnh được gọi là mức của đỉnh ấy. Cây có gốc mỗi đỉnh có không quá hai con được gọi là cây nhị phân. Cây nhị phân mà mỗi đỉnh trong có đúng hai con được gọi là cây nhị phân đầy đủ. Hình 1.4: Một cây với 9 đỉnh và 8 cạnh Ví dụ 1.6. Một cây được cho trong hình 1.4. Trong đó u1 là gốc, u4 , u5 , u6 , u7 , u8 , u9 là lá. Lá u4 có 2 cạnh đi từ gốc đến nó nên u4 có mức là 2. 11 1.2 Độ phức tạp thuật toán Trong mục này chúng ta sẽ nhắc lại khái niệm thuật toán, các đặc trưng của nó và độ phức tạp tính toán. Định nghĩa 1.8. Một thuật toán là một bản liệt kê các chỉ dẫn, các quy tắc cần thực hiện theo từng bước xác định nhằm giải quyết một bài toán đã cho trong một khoảng thời gian hữu hạn. Ví dụ 1.7. Mô tả thuật toán tìm số nguyên lớn nhất trong một dãy hữu hạn các số nguyên. 1. Đặt giá trị cực đại tạm thời bằng số nguyên đầu tiên trong dãy. 2. So sánh số nguyên tiếp theo với giá trị cực đại tạm thời, nếu lớn hơn giá trị cực đại thì đặt giá trị cực đại tạm thời bằng số nguyên đó. 3. Lặp lại bước 2 nếu còn số nguyên trong dãy. 4. Giá trị cực đại tạm thời ở thời điểm này chính là số nguyên lớn nhất trong dãy. Như vậy khi mô tả (hay xây dựng) một thuật toán ta cần lưu ý đến các yếu tố sau: 1. Dữ liệu đầu vào :Một thuật toán phải mô tả rõ các giá trị đầu vào từ một tập hợp các dữ liệu xác định. 2. Dữ liệu đầu ra: Từ một tập các giá trị đầu vào thuật toán sẽ tạo ra các giá trị đầu ra. Một thuật toán có các tính chất sau: 1. Tính xác định: Các bước của thuật toán phải được xác định một cách chính xác, các chỉ dẫn phải rõ ràng, có thể thực hiện được. 2. Tính hữu hạn: Thuật toán phải kết thúc sau một số hữu hạn bước. 3. Tính đúng đắn: Thuật toán phải cho kết quả đúng theo yêu cầu của bài toán đặt ra. 4. Tính tổng quát: Thuật toán phải được áp dụng cho mọi bài toán 12 cùng loại, với mọi dữ liệu đầu vào như đã được mô tả. Để đánh giá hiệu quả của một thuật toán, có thể xét số các phép tính phải thực hiện khi thực hiện thuật toán này. Thông thường số các phép tính được thực hiện phụ thuộc vào cỡ của bài toán, tức là độ lớn của đầu vào. Tuy nhiên trong những ứng dụng thực tiễn, chúng ta không cần biết chính xác hàm này mà chỉ cần biết một ước lượng đủ tốt của chúng. Sau đây chúng ta sẽ đưa ra một số khái niệm liên quan đến việc đánh giá độ phức tạp của thuật toán. Cho hai hàm số f và g , f, g : R → R Định nghĩa 1.9. Ta nói rằng f (x) = o(g(x)) khi x dần tới dương vô (x) ) = 0. cùng nếu như limx→+∞ ( fg(x) Ví dụ 1.8. x2 = o(x5 ) Định nghĩa 1.10. Ta nói rằng f (x) là O-lớn của g(x) khi x dần tới dương vô cùng nếu như tồn tại hai hằng số C > 0 và N > 0 sao cho với mọi x > N thì |f (x)| ≤ C.|g(x)|. Kí hiệu f (x) = O(g(x)). Ví dụ 1.9. Xét hàm số f (x) = x2 + 2x + 3, rõ ràng f (x) = O(x2 ) vì với mọi x > 1 ta có f (x) ≤ x2 + 2x2 + 3x2 = 6x2 . Chú ý rằng các số C và N nếu tồn tại thì không phải là duy nhất. Định nghĩa 1.11. Ta nói rằng f (x) là O-lớn của g(x) khi x dần tới dương vô cùng nếu như tồn tại hai hằng số C > 0 và N > 0 sao cho với mọi x > N thì |f (x)| ≤ C.|g(x)|. Kí hiệu f (x) = O(g(x)). Định nghĩa 1.12. Ta nói rằng f (x) = Ω(g(x)) nếu như tồn tại hằng số C > 0 và dãy x1 , x2 , x3 , ... sao cho với mọi i thì |f (xi )| > C.|g(xi )|. Ví dụ 1.10. x = Ω(logn) 13 Định nghĩa 1.13. Ta nói rằng f (x) tăng theo hàm mũ nếu tồn tại c > 1 và d sao cho f (x) = Ω(cx ) và f (x) = O(dx ). Ví dụ 1.11. f (x) = e2x , f (n) = n! Một số độ phức tạp thường gặp đối với một thuật toán gồm có: 1. Độ phức tạp hằng số O(1) 2. Độ phức tạp tuyến tính O(n) 3. Độ phức tạp đa thức O(P (n)) 4. Độ phức tạp logarit O(logn) 5. Độ phức tạp hàm mũ O(2n ) 6. Độ phức tạp giai thừa O(n!) Định nghĩa 1.14. DTIME là các lớp độ phức tạp bao gồm các bài toán quyết định giải được trong một giới hạn thời gian nhất định. Nếu các dữ liệu vào có kích thước n giải được trong thời gian f (n) thì bài toán nằm trong lớp độ phức tạp DT IM E(f (n)). Tiếp theo ta sẽ đưa ra khái niệm về độ phức tạp P , N P : Định nghĩa 1.15. Một bài toán quyết định được gọi là thuộc lớp P nếu tồn tại một thuật toán giải bài toán trong thời gian O(nc ) với một hằng số c không phụ thuộc kích thước đầu vào n. Định nghĩa 1.16. Một bài toán quyết định được gọi là thuộc lớp N P nếu lời giải có thể kiểm chứng được trong thời gian đa thức. Về mặt trực quan, một bài toán dễ giải thì cũng dễ kiểm tra lời giải. Do đó P ⊆ N P . Định nghĩa 1.17. Một bài toán quyết định A được gọi là N P -đầy đủ nếu như A là một bài toán trong N P và nếu có một một thuật toán thời gian đa thức cho những bài toán này, thì mọi bài toán NP đều giải được trong thời gian đa thức . 14 Định nghĩa 1.18. Một bài toán A được gọi là NP-khó nếu nó "ít nhất là khó ngang bất kì bài toán nào trong NP". Ví dụ 1.12. Có nhiều bài toán NP-khó ví dụ như bài toán người bán hàng , bài toán xếp ba lô ... 1.3 Bài toán đường đi dài nhất trên đồ thị Trong mục này ta sẽ nhắc lại khái niệm về bài toán đường đi dài nhất trên đồ thị. Định nghĩa 1.19 (Bài toán đường đi dài nhất). Cho một đồ thị G = (V, E). Hãy tìm trong G một đường đi dài nhất, tức một dãy nhiều nhất các đỉnh khác nhau sao cho hai đỉnh kế tiếp nhau đều kề nhau trong G. Hình 1.5: Một đồ thị với đường đi dài nhất đi qua tất cả các đỉnh Bài toán đường đi dài nhất trên đồ thị là bài toán cơ bản của lý thuyết đồ thị. Khác với bài toán đường đi ngắn nhất, là bài toán giải được trong thời gian đa thức, bài toán đường đi dài nhất là bài toán NP-khó do nó chứa bài toán đường đi Hamilton như một trường hợp 15 riêng. Bởi vậy đối với bài toán này, việc tìm kiếm một lời giải xấp xỉ trong thời gian đa thức là một giải pháp cần thiết và có ý nghĩa nhất định về mặt lý thuyết cũng như ứng dụng thực tiễn. 16 Chương 2 Một số kết quả thu được về việc xấp xỉ bài toán đường đi dài nhất trên đồ thị 2.1 Đặt vấn đề Trong phần này, ta sẽ chỉ ra một vài thuật toán xấp xỉ thời gian đa thức cho đường đi dài nhất. Kết quả được lấy từ tài liệu tham khảo [2] . Một thuật toán tham lam được đưa ra và nó cho thấy có thể phát hiện được những đường đi dài trong một đồ thị dày đặc. Ở điểm này, đây chính là thuật toán tốt nhất được biết đến trong một đồ thị bất kì. Đối với trường hợp nhóm lớn và các số bán cung, độ khó của bài toán đã đưa đến những nghiên cứu về dữ liệu đặc biệt, nơi mà các điều kiện thuận lợi nhất được đảm bảo để đạt được một giá trị nào đó. Từ đó chúng ta xây dựng lên thuật toán để tìm ra đường đi dài nhất trong đồ thị Hamilton. 17 Hamilton yếu Ta xét nhiều điều kiện cần để đường đi Hamilton được hình thành qua một thuật toán tuyến tính số tự nhiên. Những đồ thị thỏa mãn điệu kiện này được gọi là đồ thị Hamilton yếu. Ta không định nghĩa chính xác mà thay vào đó sẽ đưa ra ba thuộc tính của đồ thị Hamilton yếu được gọi là "các thuộc tính 1-2-3". Cho đồ thị G(V, E) và một tập U ⊆ V , ta kí hiệu tập đỉnh đồ thị con cảm sinh của G là G[U ]. Định nghĩa 2.1 (1-Tính bền). đồ thị G = (V, E) được gọi là 1-bền nếu với bất kì tập U ⊂ V , đồ thị con cảm sinh G[V − U ] có nhiều nhất |U | thành phần liên thông. Nói cách khác, bằng cách bỏ đi k đỉnh của đồ thị thì nó không thể tách ra thành nhiều hơn k thành phần liên thông. Định nghĩa 2.2 (2-Thừa số). Một đồ thị G = (V, E) sẽ có 2-thừa số nếu tồn tại tập E 0 ⊂ E , sao cho mỗi đỉnh trong đồ thị G0 = (V, E 0 ) đều có bậc 2. Định nghĩa 2.3 (3-Chu trình). Một đồ thị G = (V, E) sẽ có 3-chu trình nếu với mỗi bộ ba đỉnh u, v, w ∈ V đều tồn tại một chu trình trong đồ thị G bao gồm u, v, w. Định lý 2.1. Đồ thị Hamilton yếu bất kì là 1- bền, có 2-thừa số và là 3-chu trình. 18 Dễ thấy rằng mỗi đồ thị Hamilton dạng G thỏa mãn cả ba tính chất trên. Bỏ đi k đỉnh của một chu trình sẽ tạo ra k đường đi. Do đó một đồ thị Hamilton có thể tách ra thành nhiều nhất k thành phần liên thông bằng cách bỏ đi k đỉnh kéo theo tính 1-bền .Một chu trình Hamilton là 2-thừa số của đồ thị G. Cuối cùng, thuộc tính 3-chu trình có được từ thực tế rằng mỗi tập ba đỉnh đều nằm trên chu trình Hamilton. Định lý 2.2. Mỗi đồ thị Hamilton đều là Hamilton yếu. 2.2 Thuật toán tìm đường đi dài trên đồ thị Bây giờ ta sẽ chỉ ra thuật toán để tìm được đường đi dài trên các đồ thị 1-bền. Nếu không xét đến các trường hợp đặc biệt thì với bất cứ đồ G = (V, E) nào, chúng ta giả thiết rằng |V | = n và |E| = m . Ta đo độ dài của một đường đi dựa trên số lượng đỉnh trong nó. Trước tiên ta sẽ mô tả một thuật toán đơn giản để tìm ra đường đi dài trên đồ thị dày đặc. Sau đó, ta sẽ chỉ ra cách tìm một đường đi có độ dài Θ(logn) trên một đồ thị 1-bền bất kì. Định lý 2.3. Bất kì một đồ thị nào có m cạnh và n đỉnh sẽ chứa một đường đi có độ dài d = m n. Chứng minh. Trước tiên ta xét một đồ thị với bậc d nhỏ nhất. Rõ ràng, bất kì một đường đi dài nhất nào trên đồ thị này đều có độ dài tối thiểu là d. Vì vậy, một thuật toán tham lam sẽ tìm được một đường đi có độ dài có độ dài d. Bây giờ, ta xét một đồ thị với m cạnh, n đỉnh và cho d = m n. Lặp lại việc chọn đỉnh có bậc nhỏ hơn d và bỏ đi đỉnh này cùng tất cả các cạnh liên thuộc với nó. Quá trình này sẽ dừng khi phần đồ thị còn lại có bậc nhỏ nhất là d. Tất nhiên phần đồ thị còn lại không thể là trống