Bài giảng Toán rời rạc - Phần VII: Đồ thị - Nguyễn Viết Đông

Nội dung text: Bài giảng Toán rời rạc - Phần VII: Đồ thị - Nguyễn Viết Đông

1. Những khái niệm và tính chất cơ bản Đồ thị Biên soạn TS. Nguyễn Viết Đơng 1 2 Những khái niệm và tính chất cơ bản Những khái niệm và tính chất cơ bản e1 O e2 AB e3 V= {v1, v2, v3, v4} V= {O, A, B, AB} E = {e1, e2, e3, e4, e5, e6, e7} e e 4 7 E ={e1,e2, e3, e4, e5, e = v v , e =v v , 1 1 2 2 1 2 e5 e6 e6, e7, e8, e9} e3 =v1v4, e4 =v2v3, v1 e = v v , e = v v , e A B 5 2 3 6 2 4 e 3 1 e2 e7 = v3v4 e8 e9 e6 v2 v4 e e 5 • 4 e 3 4 v 7 3 • 1
2. Những khái niệm và tính chất cơ bản Định nghĩa đồ thị b c Định nghĩa1.Đồ thị vơ hướng G = (V, E) gồm: a d e i) V là tập hợp khác rỗng mà các phần tử của nĩ gọi h là đỉnh(vertex) của G. k ii) E là đa tập hợp gồm các cặp khơng sắp thứ tự g của hai đỉnh. Mỗi phần tử của E được gọi là một cạnh(edge) của G. Ký hiệu uv. 5 6 Những khái niệm và tính chất cơ bản Chú ý • Ta nĩi cạnh uv nối u với v, cạnh uv kề với u,v. • Nếu uv E thì ta nĩi đỉnh u kề đỉnh v. • Hai cạnh nối cùng một cặp đỉnh gọi là hai cạnh song song. • Cạnh uu cĩ hai đầu mút trùng nhau gọi là một khuyên. 7 8 2
3. Những khái niệm và tính chất cơ bản b c a d e h • Định nghĩa 2. Đồ thị vơ hướng khơng cĩ cạnh k g song song và khơng cĩ khuyên gọi là đơn đồ a b thị vơ hướng. b • Định nghĩa 3. Đồ thị vơ hướng cho phép cĩ a c cạnh song song nhưng khơng cĩ khuyên gọi là d đa đồ thị vơ hướng. • Định nghĩa 4. Đồ thị vơ hướng cho phép cĩ d c cạnh song song và cĩ khuyên gọi là giả đồ thị 9 10 Những khái niệmvà tính chấtcơ bản Multigraph -A Non-Simple Graph Simple Graph There can be multiple telephone lines between two computers in the network. Definition . A simple graph G = (V, E) consists of V, a Detroit nonempty set of vertices, and E, a set of unordered pairs New York of distinct elements of V called edges. San Francisco Detroit Chicago New York Denver Washington San Francisco Los Angeles Chicago Denver Washington In a multigraph G = (V, E) two or more edges may Los Angeles connect the same pair of vertices. 11 12 3
4. Multiple Edges Pseudograph- A Non-Simple Graph There can be telephone lines in the network from a computer to itself (for diagnostic use). Detroit Detroit New York New York San Francisco San Francisco Chicago Denver Washington Chicago Denver Los Angeles Washington Los Angeles Two edges are called multiple or parallel edges In a pseudograph G = (V, E) two or more edges may if they connect the same two distinct vertices. connect the same pair of vertices, and in addition, an edge may connect a vertex to itself. 13 14 Undirected Graphs Loops Detroit New York San Francisco Chicago pseudographs Denver multigraphs Washington simple graphs Los Angeles An edge is called a loop if it connects a vertex to itself. 16 15 4
5. Những khái niệm và tính chất cơ bản Định nghĩa 5 b b Đa đồ thị cĩ hướng G =(V,E) gồm: a a i) V là tập hợp khác rỗng mà các phần tử của nĩ gọi là đỉnh của G. ii)E là đa tập hợp gồm các cặp cĩ sắp thứ tự của hai d đỉnh. Mỗi phần tử của E được gọi là một c d c cung(cạnh)của G. Ký hiệu uv. Ta nĩi cung uv đi từ u đến v, cung uv kề với u,v 17 18 Những khái niệm và tính chất cơ bản Chú ý • Nếu uv là một cung thì ta nĩi: – Đỉnh u và v kề nhau. – Đỉnh u gọi là đỉnh đầu(gốc), đỉnh v là đỉnh cuối (ngọn) của cung uv.Đỉnh v là đỉnh sau của đỉnh u. • Hai cung cĩ cùng gốc và ngọn gọi là cung song song. • Cung cĩ điểm gốc và ngọn trùng nhau gọi là khuyên. 19 20 5
6. A Directed Graph  In a directed graph G = (V, E ) the edges are ordered pairs of (not necessarily distinct) vertices. Định nghĩa 6: Đa đồ thị cĩ hướng khơng chứa Detroit các cạnh song song gọi là đồ thị cĩ hướng New York Chicago San Francisco Denver Washington Los Angeles Some telephone lines in the network may operate in only one direction . 21 22 A Directed Graph A Directed Multigraph The telephone lines in the network that operate  In a directed multigraph G = (V, E ) the edges are ordered pairs of (not necessarily distinct) vertices, in two directions are represented and in addition there may be multiple edges. by pairs of edges in opposite directions. Detroit New York Detroit Chicago New York San Francisco Chicago San Francisco Denver Washington Denver Washington Los Angeles There may be several one-way lines in the Los Angeles same direction from one computer 23 to another in the network. 24 6
7. Types of Graphs Những khái niệm và tính chất cơ bản Biểu diễn ma trận của đồ thị: TYPE EDGES MULTIPLE EDGES LOOPS ALLOWED? ALLOWED? Simple graph Undirected NO NO Ta sử dụng ma trận kề. Multigraph Undirected YES NO Cho G = (V,E) với V={1,2, ,n}. Ma trận kề của G là ma trận A = (a ) xác định như sau: Pseudograph Undirected YES YES ij n Directed graph Directed NO YES aij = số cạnh(số cung) đi từ đỉnh i đến đỉnh j Directed multigraph Directed YES YES 25 26 Tìm ma trận kề Tìm ma trận kề a b c d a a b c d e f a 0 1 1 0 a b b b 1 0 1 1 a 0 2 1 0 0 0 c  b 2 0 1 0 1 1 c c d e 1 1 0 1 c 1 1 0 0 0 1 d d 0 1 1 0 f d 000000 e 0 1 0 0 1 0 f 0 1 1 0 0 0 27 28 7
8. Những khái niệm và tính chất cơ bản Bậc đỉnh a: deg(a) = 2 Bậc đỉnh b: deg(b) = 5 Bậc của đỉnh a b • Cho đồ thị vơ hướng G = (V,E). Bậc của đỉnh c v, ký hiệu deg(v), là số cạnh kề với v , trong đĩ một khuyên tại một đỉnh được đếm hai lần d cho bậc của đỉnh ấy. Bậc đỉnh c: deg(c) = 3 Bậc đỉnh d: deg(d) = 2 29 30 Những khái niệm và tính chất cơ bản Cho đồ thị cĩ hướng G = (V, E), v V a b 1) deg-(v):= số cung cĩ đỉnh cuối là v, gọi là bậc c d vào của v. e 2) deg +(v):= số cung cĩ đỉnh đầu là v, gọi là bậc ra f của v 3) deg(v):= deg- (v) + deg+(v)  Đỉnh bậc 0 gọi là đỉnh cơ lập. Đỉnh bậc 1 gọi là Bậc của các đỉnh? đỉnh treo 32 31 8
9. Bậc đỉnh a: deg-(a)= 1 ; deg+(a)=1 Bậc đỉnh b: deg-(b)= 1 ; deg+(b)=3 a b c d e f Bậc đỉnh c: deg-(c)= 1 ; deg+(c)=2 Bậc đỉnh d: deg-(d)= 0 ; deg+(d)=0 Bậc đỉnh e: deg-(e)= 1 ; deg+(e)=0 Bậc đỉnh f: deg-(f)= 2 ; deg+(f)=0 33 34 Những khái niệm và tính chất cơ bản Những khái niệm và tính chất cơ bản Định lí Đẳng cấu Cho đồ thị G = (V,E), m là số cạnh (cung) Định nghĩa 1) 2mv deg( )  Cho hai đơn đồ thị G = (V,E) và G’= (V’,E’). vV 2) Nếu G cĩ hướng thì: Ta nĩi rằng G đẳng cấu G’, ký hiệu G  G’, nếu tồn m deg ( v ) deg ( v ) tại song ánh f :V→ V’sao cho: v V v V uv là cạnh của G f(u)f(v) là cạnh của G’ 3) Số đỉnh bậc lẻ của đồ thị là số chẵn 35 36 9
10. Những khái niệm và tính chất cơ bản Graph Isomorphism Chú ý Nếu G và G’ là các đơn đồ thị vơ hướng đẳng cấu qua ánh xạ f thì chúng cĩ:  Cùng số đỉnh  Cùng số cạnh  Cùng số đỉnh với bậc cho sẵn(vd: số đỉnh bậc 2 của G và G’ bằng nhau)  deg v = deg f(v) 37 38 Note. Isomporphic simple graphs must have the same invariants: Isomorphism Example The number of vertices The number of edges The degrees of the vertices No vertex of deg 1 2 b b deg(e) = 1 b a 1 c a 3 a d c c 6 e 4 5 f d e d e Non-isomorphic graphs 39 40 10
11. Non-Isomorphic Example Are These Isomorphic? * Same # of vertices a 2 a * Same # of b 1 b edges 4 * Different 5 d d # of verts of e 3 e degree 2! c c (1 vs 3) 41 42 Những khái niệm và tính chất cơ bản NHỮNG KHÁI NIỆM VÀ TÍNH CHẤT CƠ BẢN Đồ thị con Subgraphs Cho hai đồ thị G = (V,E) và G’ = (V’,E’) (cùng vơ hướng hoặc cùng cĩ hướng). . G’ được gọi là đồ thị con của G, ký hiệu G’ G nếu V’ V và E’  E G H . Nếu V’= V và E’  E thì G’ được gọi là đồ thị con khung của G. 43 44 11
12. Đường đi, chu trình, đồ thị liên thơng: Đường đi, chu trình, đồ thị liên thơng Cho G = (V,E) là đồ thị vơ hướng u,v V b) Đường đi khơng cĩ cạnh nào xuất hiện quá a) Đường đi ( dây chuyền) cĩ chiều dài k nối hai một lần gọi là đường đi đơn đỉnh u,v là dãy đỉnh và cạnh liên tiếp nhau c) Đường đi khơng cĩ đỉnh nào xuất hiện quá một lần gọi là đường đi sơ cấp v0e1v1e2 vk-1ekvk sao cho: d) Đường đi được gọi là chu trình nếu nĩ bắt đầu v 0=u ,v k = v, e i=v i-1v i , i=1,2, ,k và kết thúc tại cùng một đỉnh 45 46 Đường đi, chu trình, đồ thị liên thơng Chu trình sơ Định nghĩa. Cho G = (V,E). Trên V ta định nghĩa cấp nào khơng? quan hệ tương đương như sau: u~v u = v hay cĩ một đường đi từ u đến v (a, e1,b,e2,c,e3,d,e4,b )là đường đi từ đỉnh a tới đỉnh b cĩ a) Nếu u~v thì ta nĩi hai đỉnh u và v liên thơng với chiều dài là 4. Tuy nhiên, trong trường hợp này, đồ thị của nhau chúng ta là đơn đồ thị, do vậy cĩ thể gọi đường đi này bằng 1 cách ngắn gọn như sau: (a,b,c,d,b) b) Mỗi lớp tương đương được gọi là một thành phần liên thơng của G Chu trình sơ cấp: (b,c,d,b) c) Nếu G chỉ cĩ một thành phần liên thơng thì G (b,f,e,b) gọi là liên thơng 48 47 12
13. Đường đi, chu trình, đồ thị liên thơng Định nghĩa. Cho G = (V,E) là đồ thị vơ hướng liên thơng a) Đỉnh v được gọi là đỉnh khớp nếu G – v khơng liên thơng (G – v là đồ thị con của G cĩ được bằng cách xố v và các cạnh kề với v) b) Cạnh e được gọi là cầu nếu G- e khơng liên thơng( G-e là đồ thị con của G cĩ được bằng cách xố cạnh e). 50 49 Đường đi, chu trình, đồ thị liên thơng Định nghĩa. Cho G = (V,E) vơ hướng liên thơng, khơng phải Kn, n>2. a) Số liên thơng cạnh của G, ký hiệu e(G) là số cạnh ít nhất mà khi xố đi G khơng cịn liên thơng nữa. b) Số liên thơng đỉnh của G, ký hiệu v(G) là số đỉnh ít nhất mà khi xố đi G khơng cịn liên thơng nữa. 52 51 13
14. Đường đi, chu trình, đồ thị liên thơng Định nghĩa. Cho G =(V,E) là đồ thị cĩ hướng u,v V a) Đường đi ( dây chuyền) cĩ chiều dài k nối hai đỉnh u,v là dãy đỉnh và cung liên tiếp nhau v0e1v1e2 .vk-1ek vksao cho: v0 = u, vk = v ei = vi-1vi , i = 1,2,, ,k. 54 53 Đường đi, chu trình, đồ thị liên thơng b) Đường đi khơng cĩ cung nào xuất hiện quá một lần gọi là đường đi đơn. c) Đường đi khơng cĩ đỉnh nào xuất hiện quá Đường đi cĩ độ dài 4 từ đỉnh 1 tới đỉnh một lần gọi là đường đi sơ cấp. 2 là : (1,2,3,4,2) d) Đường đi được gọi là mạch(chu trình) nếu nĩ bắt đầu và kết thúc tại cùng một đỉnh. 55 56 14
15. Đường đi, chu trình, đồ thị liên thơng Định nghĩa. Cho đồ thị cĩ hướng G = (V,E). Trên V ta định nghĩa quan hệ tương đương như sau: u~v u = v hay cĩ một đường đi từ u đến v và đường đi từ v đến u . a) Nếu u~v thì ta nĩi hai đỉnh u và v liên thơng mạnh với nhau . b) Mỗi lớp tương đương được gọi là một thành phần liên thơng mạnh của G . c) Nếu G chỉ cĩ một thành phần liên thơng mạnh thì G gọi là liên thơng mạnh . 57 58 Một số đồ thị đặc biệt Một số đồ thị vơ hướng đặc biệt 4. Đồ thị lưỡng phân đủ: là đồ thị đơn, lưỡng 1. Đồ thị đủ cấp n: Kn là đơn đồ thị cấp n mà giữa hai đỉnh bất kỳ đều cĩ một cạnh. phân, mỗi đỉnh trong V1 đều kề với mọi đỉnh trong V2. 2. Đồ thị k-đều : là đồ thị mà mọi đỉnh đều cĩ bậc bằng nhau và bằng k. 5. Đồ thị bù 3. Đồ thị lưỡng phân: Cho Kn = (V,E), G (V,E1) ≤ Kn , GVEE ,\1 G = (V,E), V = V1 V2, , V1 V2 =. Mọi cạnh của G đều nối một đỉnh trong V1 với một đỉnh G gọi là đồ thị bù của G. Đồ thị G đươc gọi là trong V2 tự bù nếu G đẳng cấu với đồ thị bù của nĩ 59 60 15
16. Một số đồ thị đặc biệt Một số đồ thị đặc biệt C4 C K4 5 K5 Cycle Cn Complete graph Kn 61 62 Một số đồ thị đặc biệt K K 1 K2 K3 4 K 5 K6 n nn( 1) W4 W Note that Kn has  i edges. 5 i 1 2 Wheele Wn 63 64 16
17. C 3 C4 C 5 C6 C W3 C7 8 W4 W 5 W6 W W7 8 How many edges are there in Wn? How many edges are there in Cn? 65 66 Q0 Q1 Q2 Q4 Q3 Number of vertices: 2n. Number of edges:Exercise to try! 67 68 17
18. Đề thi Đề thi 1)2000. ĐHBK 2)2001,ĐHBK Cho đồ thị vơ hướng , đơn G cĩ 7 đỉnh trong đĩ Cho đồ thị vơ hướng G liên thơng mà mỗi cĩ một đỉnh bậc 6. Hỏi G cĩ liên thơng khơng? đỉnh đều cĩ bậc bằng 20. Chứng minh rằng nếu xố đi một cạnh bất kỳ thì đồ thị thu Giải. Đỉnh bậc 6 nối với 6 đỉnh cịn lại. Do đĩ được vẫn cịn liên thơng hai đỉnh bất kỳ đều cĩ một đường đi qua đỉnh bậc 6 69 70 Đề thi Đề thi Giải . 3)2002,ĐHKHTN. Giả sử ta xĩa cạnh uv. Ta chỉ cần chứng minh vẫn cĩ đường đi từ u đến v. Đồ thị G gồm n đỉnh, 41 cạnh, mọi đỉnh đều cĩ Phản chứng. Giả sử khơng cĩ đường đi từ u bậc p. Nếu p lẻ và p> 1 thì đồ thị G cĩ liên thơng đến v. Khi đĩ thành phần liên thơng G’ chứa u mà khơng chứa v. Trong G’, u cĩ bậc 19, mọi khơng? đỉnh khác đều cĩ bậc 20. Tổng các bậc trong G’ là số lẻ .Vơ lý. 71 72 18
19. Đề thi Đề thi 4)2005, ĐHKHTN. Giải . Từ cơng thức bậc của đỉnh ta cĩ np=2.41. Vì p lẻ nên p là ước của 41. Mà 41 là số nguyên tố nên p = 41. Vậy n = 2 Vẽ đơn đồ thị vơ hướng gồm 6 đỉnh với bậc Do đĩ G cĩ 2 đỉnh mà cả 2 đỉnh đều cĩ bậc 41. Nếu G khơng 2,2,3,3,3,5 liên thơng thì G phải tách thành 2 thành phần liên thơng, mà mỗi thành phần liên thơng đều cĩ bậc 41 (lẻ). Vơ lý. 73 74 Đề thi Đề thi Giải . Nhận xét . Đỉnh bậc 5 nối với 5 đỉnh cịn lại. Do đĩ ta chỉ phải quan tâm đến 5 đỉnh cịn lại. Ta xét đơn đồ thị với 5 đỉnh và các bậc là 1,1,2,2,2. TH1. Hai đỉnh bậc 1 nối với nhau, 3 đỉnh bậc 2 nối với nhau tạo thành chu trình 75 76 19
20. Đề thi Đề thi Suy ra đồ thị cần tìm là TH2. Hai đỉnh bậc 1 khơng nối với nhau. Khi đĩ hai đỉnh bậc 1 phải nối với hai đỉnh bậc 2 khác nhau và đỉnh bậc hai cịn lại phải nối với hai đỉnh bậc hai ấy 77 78 Đề thi Đề thi • Suy ra đồ thị cần tìm là: 5)2006 , ĐHKHTN. Vẽ đồ thị đơn vơ hướng gồm 6 đỉnh với bậc 2,2,3,3,3,3 79 80 20
21. Đề thi Đề thi Giải. Ta được TH1. 2 đỉnh bậc 2 nối với nhau. Nếu chúng nối đến cùng một đỉnh bậc 3 thì đỉnh bậc 3 này chỉ nối đến một trong 3 đỉnh cịn lại:khơng thể đuợc. Như vậy hai đỉnh bậc hai nối đến hai đỉnh bậc 3 khác nhau. Bỏ 2 đỉnh bậc hai ta sẽ được một đơn đồ thị vơ hướng gồm 4 đỉnh với bậc 2, 2, 3, 3. Để ý rằng trong đồ thị này mỗi đỉnh bậc 2 đều nối với 2 đỉnh bậc 3 và do đĩ 2 đỉnh bậc 3 cũng nối với nhau. 81 82 Đề thi Đề thi TH2. 2 đỉnh bậc 2 khơng nối với nhau nhưng và ta được đồ thị nối đến cùng một đỉnh bậc 3. Khi ấy nếu bỏ đi hai cạnh này ta được một đồ thị 6 đỉnh với bậc 1, 1, 1, 3, 3, 3. Nếu 2 đỉnh bậc 1 nối với nhau hoặc nối đến cùng một đỉnh bậc 3 thì bỏ đi 2 đỉnh này cịn lại một đồ thị đỉnh với bậc 1, 3, 3, 3 hoặc 1, 1, 3, 3: khơng thể được. Như vậy mỗi đỉnh bậc 1 nối đến đỉnh bậc 3 khác nhau. Bỏ đi đỉnh bậc 1 sẽ cịn lại một chu trình 2, 2, 2 83 84 21
22. Đề thi Đề thi • TH3. 2 đỉnh bậc 2 khơng nối với nhau 6) Đề thi 07 và mỗi đỉnh nối đến 2 đỉnh bậc 3 khác Tìm tất cả các đơn đồ thị vơ hướng (sai nhau. Khi ấy nếu bỏ đi hai đỉnh này sẽ khác một đẳng cấu) gồm 6 đỉnh với bậc : cịn lại một chu trình 2, 2, 2, 2 và ta được: 2, 2, 2, 3, 3, 4 85 86 Đề thi Đề thi Giải 2,5 đ (vẽ mỗi đồ thị được 0,5đ. Lý luận đầy đủ đây là 4 lời giải duy nhất: 0,5đ) • Trường hợp 1: đỉnh bậc 4 nối đến 2 đỉnh bậc 3 và 2 đỉnh bậc 2. Bỏ đỉnh bậc 4 và 4 cạnh tương ứng ta sẽ được 1 đồ thị đơn vô hướng gồm 5 đỉnh với bậc 1, 1, 2, 2, 2. • Trường hợp 1a: mỗi đỉnh bậc 1 đều nối với 1 đỉnh bậc 2 (phải khác nhau). Do đó đỉnh bậc 2 còn lại sẽ nối đến 2 đỉnh bậc 2 trên. Chúng tạo thành một dây chuyền 1,2,2,2,1. Ta được 2 đồ thị không đẵng cấu nhau 87 88 22
23. Đề thi Đề thi • Trường hợp 2: đỉnh bậc 4 nối đến 3 đỉnh bậc 2 và 1 đỉnh bậc 3. Khi ấy nếu bỏ đi đỉnh bậc 4 và các cạnh tương ứng ta sẽ được 1 đồ thị đơn vô hướng gồm 5 đỉnh với bậc 1, 1, 1, 2, 3. Khi ấy đỉnh bậc 3 chỉ có thể nối đến 2 đỉnh bậc 1 và đỉnh bậc 2. Đỉnh bậc 1 còn lại sẽ nối đến đỉnh bậc 2, và ta được 89 90 Đề thi Đề thi • Trường hợp 1b: 2 đỉnh bậc 1 nối nhau. Như ĐHKHTN08 .Cho đồ thị G đơn, vơ hướng ,10 vậy 3 đỉnh bậc 2 tạo thành một dây chuyền. đỉnh và cĩ nhiều hơn 36 cạnh.Hỏi G cĩ liên Ta được đồ thị thơng khơng ?Tại sao? Giải(tĩm tắt). G là đồ thị liên thơng Phản chứng. Giả sử G khơng liên thơng .Gọi G1 là một thành phần liên thơng gồm k đỉnh 1 k 9.Gọi m là số cạnh của G thì m k2 -10k +45 . Mà max (k2 -10k +45) =36 (với 1 k 9) nên 91 m 36.Trái giả thiết. 92 23
24. Đề thi Đề thi • Cách khác. ĐHKHTN 2009. Nếu bỏ đi đỉnh bậc 1 và cạnh kề nĩ ta sẽ được đơn đồ thị vơ Xét đồ thị đơn vơ hướng G với 6 đỉnh , trong đĩ cĩ một đỉnh bậc hướng H gồm 5 đỉnh với bậc là 2, 3, 3, 3, 3. Rõ ràng nếu H liên 1 và 5 đỉnh bậc 3. Chứng minh rằng G liên thơng. thơng thì G cũng liên thơng. Giải. Trong đồ thị H đỉnh bậc 2 phải nối với 2 đỉnh bậc 3 khác nhau. Giả sử G khơng liên thơng. Gọi G1, G2, ,Gk là các thành phần Bỏ đỉnh bậc 2 này và bỏ hai cạnh kề với nĩ ta được đồ thị K gồm liên thơng của G (k 2). Vì G khơng cĩ đỉnh cơ lập nên mỗi 4 đỉnh với bậc 2, 2, 3, 3. Rõ ràng nếu K liên thơng thì H cũng liên thành phần liên thơng đều phải cĩ ít nhất hai đỉnh. Như vậy mỗi thơng và do đĩ G cũng liên thơng. thành phần liên thơng đều phải cĩ ít nhất một đỉnh bậc 3. Suy ra Trong đồ thị K hai đỉnh bậc 3 phải nối với nhau. Bỏ cạnh nối hai mỗi thành phần liên thơng phải cĩ ít nhất 4 đỉnh. Vậy G phải cĩ ít đỉnh bậc 3 này ta được đồ thị gồm 4 đỉnh bậc 2, đồ thị này là một nhất 4k 8 đỉnh . Trái giả thiết. chu trình , nĩ liên thơng . Do đĩ G liên thơng. 93 94 Bài tốn đường đi ngắn nhất Bài tốn đường đi ngắn nhất Đồ thị cĩ trọng số Ma trận khoảng cách(trọng số) 1. Đồ thị G = (V,E) gọi là đồ thị cĩ trọng số (hay chiều dài, trọng lượng) nếu mỗi cạnh(cung) e được gán với Cho G = (V, E), V = {v1,v2, ,vn} là đơn đồ thị cĩ trọng một số thực w(e).Ta gọi w(e) là trọng lượng của e. số. Ma trận khoảng cách của G là ma trận D= (dij) xác 2. Độ dài của đường đi từ u đến v bằng tổng độ dài các định như sau: cạnh mà đường đi qua 0 khi i j 3. Khoảng cách giữa 2 đỉnh u,v là độ dài ngắn nhất của d w() v v khi v v E các đường đi từ u đến v. ij i j i j khi vij v E 95 96 24
25. Bài tốn đường đi ngắn nhất 0 5 31 40 0 27 73 26 0 8 49 25 38 Thuật tốn Dijkstra D 0 16 70 0 9 Bài tốn. 23 0 12 10 0 Cho G = (V, E) đơn, liên thơng, cĩ trọng số dương (w(uv) > 0 với mọi u khác v). Tìm đường đi ngắn nhất từ u0 đến v và tính khoảng cách d(u 0,v). 98 97 Bài tốn đường đi ngắn nhất Bài tốn đường đi ngắn nhất Phương pháp 3. Trong V\{u ,u } tìm đỉnh cĩ khoảng cách đến Xác định tuần tự các đỉnh cĩ khoảng cách đến u0 0 1 u nhỏ nhất(đỉnh này phải là một trong các từ nhỏ đến lớn. 0 đỉnh kề với u hoặc u )giả sử đĩ là u 1. Trước tiên đỉnh cĩ khoảng cách nhỏ nhất đến u 0 1 2 0 4. Tiếp tục như trên cho đến bao giờ tìm được là u . 0 khoảng cách từ u đến mọi đỉnh . 2. Trong V\{u } tìm đỉnh cĩ khoảng cách đến u 0 0 0 Nếu G cĩ n đỉnh thì: nhỏ nhất (đỉnh này phải là một trong các đỉnh kề 0 = d(u ,u ) < d(u ,u ) d(u ,u ) d(u ,u ) với u0) giả sử đĩ là u1 0 0 0 1 0 2 0 n-1 99 100 25
26. Thuật tốn Dijkstra Bước1. i:=0, S:=V\{u0}, L(u0):=0, L(v):= với mọi v S và Bài tốn đường đi ngắn nhất đánh dấu đỉnh v bởi( ,-). Nếu n=1 thì xuất d(u0,u0)=0=L(u0) Bước2. Với mọi v S và kề với ui(nếu đồ thị cĩ hướng thì v Bài tập 1. Tìm đường đi ngắn nhất từ u0 đến các là đỉnh sau của ui), đặt L(v):= min{L(v),L(ui)+w(ui v)}.Xác đỉnh cịn lại định k = minL(v) ,v S. s r 7 Nếu k= L(vj) thì xuất d(u0,vj )= k và đánh dấu vj bởi (L(vj);ui). 1 4 3 ui+1:= vj S:=S\{ui+1} 3 x u 1 Bước3 i:=i+1 2 3 t Nếu i = n-1 thì kết thúc 1 4 Nếu khơng thì quay lại Bước 2 w y 3 z 5 101 102 s s r 7 r 7 1 1 4 3 4 3 3 x 3 x u 1 u 1 2 3 2 3 t t 1 4 1 4 w w y 3 z 5 y 3 z 5 u0 r s t x y z w u r s t x y z w 0 0* ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) 0* ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) - (4,u0) ( ,-) ( ,-) ( ,-) (1u0)* ( ,-) ( ,-) 103 104 26
27. s r 7 r 7 1 4 3 1 3 x u 4 3 1 x 2 t 3 3 1 4 u 1 w 2 3 y 3 z 5 t 1 4 u0 r s t x y z w w 0* ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) y 3 z 5 - (4,u0) ( ,-) ( ,-) ( ,-) (1u0)* ( ,-) ( ,-) - (3,y)* ( ,-) ( ,-) ( ,-) - (4,y) ( ,-) u0 r s t x y z w - - (10,r) (6,r) ( ,-) - (4,y)* ( ,-) 0* ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) - - (10,r) (6,r)* ( ,-) - - (9,z) (4,u ) (1u )* - 0 ( ,-) ( ,-) ( ,-) 0 ( ,-) ( ,-) - - (9,t) - (7,t)* - - (9,z) (3,y)* - ( ,-) ( ,-) ( ,-) - (4,y) ( ,-) - - (8,x)* - - - - (9,z) 105 106 - - - - - - - (9,z)* Bài tốn đường đi ngắn nhất Bài tốn đường đi ngắn nhất Cây đường đi s Bài tập 2(ĐHKHTN,2006). r 3 1 Câu 5. Cho đồ thị cĩ trọng số G = (V, E) , t 1 u x V = { v1, v2, v3, v4, v5, v6 , v7}xác định bởi ma 2 trận trọng số D. Dùng thuật tốn Dijkstra tìm 1 đường đi ngắn nhất từ v1 đến các đỉnh v2,v3,v 4, v5, v ,v y 3 z 5 6 7 w 107 108 27
28. Bài tốn đường đi ngắn nhất Bài tốn đường đi ngắn nhất 0 5 31 40 0 27 73 26 0 8 49 25 38 D 0 16 70 0 9 23 0 12 10 0 109 110 Bài tốn đường đi ngắn nhất Bài tốn đường đi ngắn nhất v1 v2 v3 v4 v5 v6 v7 0* ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) - (5,v1)* (31,v1) (40,v1) ( ,-) ( ,-) ( ,-) (31,v )* - - 1 (40,v1) (78,v2) ( ,-) ( ,-) (39,v )* - - - 3 (78,v2) (56,v3) (69,v3) - - - - (78,v2) (55,v4)* (69,v3) (67,v )* - - - - (78,v2) - 6 - - - - (77,v7) - - 111 112 28
29. Bài tốn đường đi ngắn nhất Bài tốn đường đi ngắn nhất a b c Bài tập3(ĐHKHTN2005). Cho một ví dụ chứng tỏ rằng thuật tốn 0 ( , ) ( , ) Dijkstrađể tìm đường đi ngắn nhất từ một đỉnh đến các đỉnh khác khơng áp dụng được cho đồ (5,aa ) (4, )* thị cĩ trọng lượng nếu cĩ cạnh cĩ trọng lượng âm (5,a )* b 5 -3 113 a 4 c 114 a b c d e f g z Bài tốn đường đi ngắn nhất 0 ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) 0 (4.a) (3.a) ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) BÀI 4(Đề2007) 0 (4.a) (3.a) (6.c) (9.c) ( ,-) ( ,-) ( ,-) Dùng thuật toán Dijsktra để tìm đường đi ngắn nhất từ đỉnh a đến đỉnh z và chiều dài của nó 0 (4.a) (3.a) (6.c) (9.c) ( ,-) ( ,-) ( ,-) trong đồ thị vô hướng có trọng lượng sau: 0 (4.a) (3.a) (6.c) (7.d) (11.d) ( ,-) ( ,-) 0 (4.a) (3.a) (6.c) (7.d) d e b 5 d 5 f (11. ) (12, ) ( ,-) 4 7 0 (4.a) (3.a) (6.c) (7.d) (11.d) (12,e ) (18,f ) 3 2 2 1 z 0 (4.a) (3.a) (6.c) (7.d) (11.d) (12,e ) (16,g ) a 3 4 0 (4.a) (3.a) (6.c) (7.d) (11.d) (12,e ) (16,g ) c 6 e 5 g 115 116 29
30. Bài tốn đường đi ngắn nhất Bài tốn đường đi ngắn nhất Thuật tốn Ford – Bellman Tìm đường đi ngắn nhất từ u0 đến các đỉnh hoặc chỉ ra đồ thị Bước 3. Nếu Lk(v) =Lk-1(v) với mọi v, tức Lk(v) cĩ mạch âm. ổn định thì dừng. Ngược lại đến bước 4. Bước 1. L (u ) =0 và L (v) = v u Đánh dấu đỉnh v 0 0 0 0. Bước 4. Nếu k = n thì dừng. G cĩ mạch âm. Nếu bằng ( ,-) ; k=1. k n-1 thì trở về bước 2 với k:=k+1 Bước 2. Lk(u0) = 0 và Lk(v) = min{Lk-1(u)+w(uv)/u là đỉnh trước của v} Nếu Lk(v) = Lk-1(y)+w(yv)thì đánh dấu đỉnh v bởi (Lk(v),y) 117 118 Bài tốn đường đi ngắn nhất Bài tốn đường đi ngắn nhất 4 2 3 2 • BT1. 7 1 6 1 2 2 4 -6 2 3 2 7 1 8 3 6 4 5 1 2 2 -6 2 8 3 k 1 2 3 4 5 6 4 5 2 0 0 ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) 119 120 30
31. 4 4 2 3 2 2 3 2 7 1 7 1 6 6 1 2 1 2 -6 2 2 -6 8 3 5 8 3 4 4 5 2 2 k 1 2 3 4 5 6 k 1 2 3 4 5 6 0 0 ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) 0 0 ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) 1 0 (7,1) ( ,-) (8,1) ( ,-) ( ,-) 1 0 (7,1) ( ,-) (8,1) ( ,-) ( ,-) 2 0 (7,1) (11,2) (8,1) (9,2) (8,2) 121 122 4 2 3 2 2 4 3 2 7 1 7 1 6 1 6 1 2 2 -6 2 2 -6 8 3 4 5 8 3 2 4 5 2 k 1 2 3 4 5 6 k 1 2 3 4 5 6 0 0 ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) 0 0 ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) 1 0 (7,1) ( ,-) (8,1) ( ,-) ( ,-) 1 0 (7,1) ( ,-) (8,1) ( ,-) ( ,-) 2 0 (7,1) (11,2) (8,1) (9,2) (8,2) 2 0 (7,1) (11,2) (8,1) (9,2) (8,2) 3 0 (7,1) (10,6) (2,6) (9,2) (8,2) 3 0 (7,1) (10,6) (2,6) (9,2) (8,2) 4 0 (4,4) (10,6) (2,6) (4,4) (8,2) 123 124 31
32. 4 2 4 3 2 3 2 7 2 7 1 1 1 6 1 6 2 2 2 2 -6 -6 8 4 5 3 8 4 5 3 2 2 k 1 2 3 4 5 6 k 1 2 3 4 5 6 0 0 ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) 0 0 ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) 1 0 (7,1) ( ,-) (8,1) ( ,-) ( ,-) 1 0 (7,1) ( ,-) (8,1) ( ,-) ( ,-) 2 0 (7,1) (11,2) (8,1) (9,2) (8,2) 2 0 (7,1) (11,2) (8,1) (9,2) (8,2) 3 0 (7,1) (10,6) (2,6) (9,2) (8,2) 3 0 (7,1) (10,6) (2,6) (9,2) (8,2) 4 0 (4,4) (10,6) (2,6) (4,4) (8,2) 4 0 (4,4) (10,6) (2,6) (4,4) (8,2) 5 0 (4,4) (8,2) (2,6) (4,4) (5,2) 5 0 (4,4) (8,2) (2,6) (4,4) (5,2) 6 0 (4,4) (7,6) (-1,6) (4,4) (5,2) 125 126 Bài tốn đường đi ngắn nhất Bài tốn đường đi ngắn nhất k = n = 6 . Lk(i) chưa ổn định nên đồ thị cĩ mạch k = n = 6 . Lk(i) chưa ổn định nên đồ thị cĩ mạch âm. Chẳng hạn: âm. Chẳng hạn: 4→2→6→4 cĩ độ dài -3 4→2→6→4 cĩ độ dài -3 127 128 32
33. Bài tốn đường đi ngắn nhất Bài tốn đường đi ngắn nhất • BT2. k 1 2 3 4 5 6 0 0 ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) 4 2 3 2 1 0 (7,1) ( ,-) (8,1) ( ,-) ( ,-) 7 1 6 2 0 (7,1) (11,2) (8,1) (9,2) (8,2) 1 2 2 -2 3 0 (7,1) (10,6) (6,6) (9,2) (8,2) 8 3 4 0 (7,1) (10,6) (6,6) (8,4) (8,2) 4 5 2 5 0 (7,1) (10,6) (6,6) (8,4) (8,2) 129 130 Bài tốn đường đi ngắn nhất Bài tốn đường đi ngắn nhất Thuật tốn Floyd. Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh 2 3 2 hoặc chỉ ra đồ thị cĩ mạch âm. Ngồi ma trận 7 1 6 1 khoảng cách D ta cịn dùng ma trận Q = (Qij), -2 trong đĩ 4 5 j khi ij E 2 Qij 0 khiij E 131 132 33
34. Bài tốn đường đi ngắn nhất Bài tốn đường đi ngắn nhất Bước 1. D0 = D, Q0 = Q, k = 1. • Bước 3. Nếu k = n thì dừng. Nếu k < n thì trở Bước 2. Với i = 1 đến n, với j =1 đến n. Đặt lại Bước 2 với k := k + 1 Dk 1(,)(,)(,)(,)(,) ik D k 1 kj ifD k 1 ij D k 1 ik D k 1 kj Dk (,) i j Dijk 1(,)(,)(,)(,) ifDijDikDkj k 1 k 1 k 1 Qikk 1(,)(,)(,)(,) ifDijDikDkj k 1 k 1 k 1 Qk (,) i j Qijk 1(,)(,)(,)(,) ifDijDikDkj k 1 k 1 k 1 133 134 Bài tốn đường đi ngắn nhất Bài tốn đường đi ngắn nhất • Cho đồ thị G cĩ ma trận khoảng cách là • Khi đĩ ma trận Q sẽ là 1 2 3 4 5 6 11 22 33 44 5 6 1 0 4 1 1 0 4 1 1 0 4 1 1 0 2 3 0 0 0 2 0 5 3 2 0 5 3 2 0 5 3 2 0 0 0 4 5 0 3 2 0 10 3 2 0 10 3 2 0 10 3 0 2 0 4 0 0 4 0 9 44 0 0 0 00 0 96 5 4 0 7 55 0 0 0 44 0 76 6 6 09 66 0 62 0 0 0 90 135 136 34
35. Bài tốn đường đi ngắn nhất Bài tốn đường đi ngắn nhất • Ta cĩ D1 = D, Q1 = Q và 1 2 3 4 5 6 1 2 3 4 5 6 1 0 4 1 9 7 1 0 24 31 2 2 0 2 0 5 3 2 0 0 0 45 53 0 3 2 0 710 5 3 0 2 0 210 2 0 D2 = 4 0 9 Q2 = 4 0 0 0 0 0 69 5 4 0 7 5 0 0 0 4 0 67 6 6 11 9 09 6 0 26 0 2 2 09 137 138 Bài tốn đường đi ngắn nhất Bài tốn đường đi ngắn nhất 1 2 3 4 5 6 1 2 3 4 5 6 1 0 34 1 8 6 1 0 34 31 3 3 2 0 5 3 2 0 0 0 45 53 0 D = Q = 3 3 2 0 710 5 3 3 0 2 0 210 2 0 4 0 9 4 0 0 0 0 0 69 5 4 0 7 5 0 0 0 4 0 67 6 6 11 9 09 6 0 26 0 2 2 09 139 140 35
36. Bài tốn đường đi ngắn nhất Bài tốn đường đi ngắn nhất 1 2 3 4 5 6 1 2 3 4 5 6 1 0 34 1 8 6 17 1 0 34 31 3 3 3 2 0 5 3 14 2 0 0 0 45 53 4 D = Q = 4 3 2 0 710 5 16 4 3 0 2 0 210 2 2 4 0 9 4 0 0 0 0 0 69 5 4 0 7 5 0 0 0 4 0 67 6 6 11 9 09 6 0 26 0 2 2 09 141 142 Bài tốn đường đi ngắn nhất Bài tốn đường đi ngắn nhất 1 2 3 4 5 6 1 2 3 4 5 6 1 0 34 1 8 6 13 1 0 34 31 3 3 3 2 0 5 3 10 2 0 0 0 45 53 5 D = 5 3 2 0 710 5 12 3 0 2 0 210 2 2 4 15 0 9 Q5 = 4 0 0 0 0 0 69 5 13 4 0 7 5 0 0 0 4 0 67 6 6 11 9 09 6 0 26 0 2 2 09 143 144 36
37. Bài tốn đường đi ngắn nhất Bài tốn đường đi ngắn nhất 1 2 3 4 5 6 1 2 3 4 5 6 1 0 34 1 8 6 13 1 0 34 31 3 3 3 2 0 5 3 10 2 0 0 0 45 53 5 D = 6 3 2 0 710 5 12 3 0 2 0 210 2 2 4 15 0 18 9 Q6 = 4 0 6 0 0 6 69 5 13 4 0 7 5 0 6 0 4 0 67 6 6 11 9 09 6 0 26 0 2 2 09 145 146 Bài tốn đường đi ngắn nhất Đường đi Euler - Đường đi Hamilton • Đường đi ngắn nhất từ đỉnh 1 đến đỉnh 6 là 1 3 2 5 6 vì Q6(1,6) =3,Q6(3,6) = 2,Q6(2,6) = 5,Q6(5, 6) = 6. • Đường đi ngắn nhất từ đỉnh 4 đến đỉnh 5 là 4 6 2 5 vì Euler Q6(4,5) =6,Q6(6,5) = 2,Q6(2,5) = 5. (1707-1783) 147 148 37
38. Đường đi Euler - Đường đi Hamilton Đường đi Euler - Đường đi Hamilton Problem. The town of Kưnigsberg was divided into four sections by the branch of the Pregel River Hamilton (1755-1804) These four sections are connected by seven bridges 149 150 Euler Paths Question. Can one cross seven bridges and return to the starting point without crossing any bridge twice? In the eighteenth century, Euler solved this problem 151 using Graph Theory 152 38
39. C Đường đi Euler - Đường đi Hamilton A Đường đi Euler D Định nghĩa. B i. Đường đi Euler là đường đi qua tất cả các Euler modeled this problem using the multigraph: cạnh mỗi cạnh (cung) đúng một lần.Chu trình Euler là chu trình đi qua tất cả các cạnh  four sections correspond to C của đồ thị mỗi cạnh đúng một lần. four vertices A, B, C, D. ii. Đồ thị được gọi là đồ thị Euler nếu nĩ cĩ chu  each bridge corresponds A D trình Euler to an edge 153 154 B Đường đi Euler - Đường đi Hamilton Đường đi Euler-Đường đi Hamilton Điều kiện cần và đủ. Thuật tốn Fleury để tìm chu trình Euler. i. Cho G = (V,E) là đồ thị vơ hướng liên thơng. G là đồ thị Euler Mọi đỉnh của G đều cĩ 1. Bắt đầu từ một đỉnh bất kỳ của G và tuân theo bậc chẵn. qui tắc sau: Mỗi khi đi qua một cạnh nào đĩ thì Nếu G cĩ hai đỉnh bậc lẻ cịn mọi đỉnh khác đều xố nĩ đi, sau đĩ xố đỉnh cơ lập nếu cĩ. cĩ bậc chẵn thì G cĩ đường đi Euler 2. Khơng bao giờ đi qua một cầu trừ phi khơng ii. Cho G là đồ thị cĩ hướng liên thơng. G là đồ thị Euler G cân bằng. cịn cách đi nào khác. 155 156 39
40. Đường đi Euler-Đường đi Hamilton Đường đi Euler - Đường đi Hamilton Đường đi Hamilton. a b c d Định nghĩa. Đường đi Hamilton là đường đi qua tất cả các đỉnh của đồ thị mỗi đỉnh đúng một lần. e h g f  Định nghĩa tương tự cho chu trình Hamilton (mạch Hamilton). abcfdcefghbga  Đồ thi gọi là đồ thị Hamilton nếu nĩ cĩ chu trình Hamilton 157 158 Đường đi Euler - Đường đi Hamilton Đường đi Euler - Đường đi Hamilton Điều kiện đủ (cho đồ thị đơn vơ hướng). Qui tắc để xây dựng một chu trình Hamilton H hoặc chỉ ra đồ thị vơ hướng khơng là Hamilton i. Định lý Ore(1960). Cho đồ thị G cĩ n đỉnh. Nếu deg(i)+deg(j)  n 3 với i và j là hai đỉnh Qui tắc 1.Tất cả các cạnh kề với đỉnh bậc 2 phải ở khơng kề nhau tuỳ ý thì G là Hamilton. trong H ii. Định lý Dirac (1952) Cho đồ thị G cĩ n Qui tắc 2. Khơng cĩ chu trình con(chu trình cĩ chiều đỉnh. Nếu deg(i)  n/2 với i tuỳ ý thì G là dài <n) nào được tạo thành trong quá trình xây dựng H Hamilton 159 160 40
41. Đường đi Euler - Đường đi Hamilton Đường đi Euler-Đường đi Hamilton Điều kiện đủ cho đồ thị cĩ hướng , đơn(khơng cĩ khuyên và khơng cĩ cạnh song song cùng Qui tắc 3. Khi chu trình Hamilton mà ta đang xây chiều) dựng đi qua đỉnh i thì xố tất cả các cạnh kề với i ĐK Meyniel. ij và ji  E deg(i)+deg(j) 2n-1 với i, j tùy ý. mà ta chưa dùng(vì khơng được dùng đến nữa). Điều này lại cĩ thể cho ta một số đỉnh bậc 2 và ta ĐLMeyniel(1973). Nếu G là đồ thị đơn, liên thơng mạnh lại dùng qui tăc1. và thoả ĐK Meyniel thì G là đồ thị Hamilton. Qui tắc 4. Khơng cĩ đỉnh cơ lập hay cạnh treo nào ĐL Camion(1959). Nếu G là đơn đồ thị đủ, liên thơng mạnh được tạo nên sau khi áp dụng qui tắc 3. thì G Hamilton 161 162 Đường đi Euler-Đường đi Hamilton Đường đi Euler-Đường đi Hamilton • Đề thi2004(ĐHKHTN) ĐLGhouila-Houri(1960) Nếu G là đơn đồ thị Đồ thi sau đây cĩ Hamilton khơng? liên thơng mạnh sao cho mọi đỉnh đều cĩ bậc 1 2 3 khơng nhỏ hơn n thì G Hamilton. 4 5 6 ĐL Woodall(1972). Cho G là đơn đồ thị thoả + - ij E deg (i)+deg (j) n, với mọi i,j 7 8 9 thì G Hamilton 163 164 41
42. Đường đi Euler-Đường đi Hamilton Đường đi Euler-Đường đi Hamilton • Giả sử G cĩ chu trình Hamilton H, theo qui • Giải: tăc1,tất cả các cạnh kề với đỉnh bậc 2 đều ở Ta thêm vào đồ thị G một đỉnh z và nối z với mỗi đỉnh trong H:12,14,23,36,47,78,69,89. Ta cĩ chu của G bởi một cạnh, ta thu được đồ thị G’ cĩ n+1 trình con là 1,2,3,6,9,8,7,4,1. đỉnh.Bậc của mọi đỉnh trong G’ đều lớn hơn bậc cũ của nĩ một đơn vị(trừz), cịn bậc của z bằng n. Vậy G khơng là đồ thị Hamilton. Do đĩ trong G’thì Đề thi 2005(ĐHKHTN).Cho G là đồ thị khơng deg’(i)+deg’(j)=deg(i)+1+deg(j) +1 n-1+1+1 = n+1, hướng, đơn, n 3(n là số đỉnh), khi i và j khác z . deg(i)+deg(j) n-1. Chứng minh rằng G cĩ deg’ (i) + deg ’(z) = deg (i) + 1 + n n+1 ,với i khác z đường đi Hamilton. Theo ĐL Ore thì G’ là đồ thị Hamilton,suy ra G cĩ đường đi Hamilton 165 166 42