Download miễn phí Điều hành dự án bằng phương pháp Pert - Pcm và ứng dụng giải bài toán lập lịch thi công công trình
Trong sự phát triển vượt bậc của xã hội hiện nay, việc xây dựng các dự án lớn đã có rất nhiều chuyên gia có nhiều kinh nghiệm trợ giúp họ hoàn thành dự án này, đồng thời họ cũng đã có đủ những kinh nghiệm để hoàn thành các dự án đó.
Tuy nhiên để hoàn thành những dự án lớn đó thì với sự phát triển của công nghệ thông tin hiện nay đã phần nào đã góp phần vào công cuộc phát triển và xây dựng nền kinh tế của nước nhà.
Trong thời gian làm đề tài này. Với một công nghệ tối ưu đã nghiên cứu và phát triển trong xây dựng và điều hành những dự án lớn (Nhất là những dự án đòi hỏi sự chính xác, đòi hỏi phải tiết kiệm nhân lực, tiết kiệm thời gian nhưng phải hoàn thành trong một thời gian sớm nhất), nhưng đã phần nào đáp ứng được được các nhu cầu cần thiết ở trên.
Để tải tài liệu này, vui lòng Trả lời bài viết, Mods sẽ gửi Link download cho bạn ngay qua hòm tin nhắn.
Ketnooi -
You must be registered for see links
Ai cần tài liệu gì mà không tìm thấy ở Ketnooi, đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
đồ thị là 3n.
Hệ quả: Trong đồ thị vô hướng, số đỉnh bậc lẻ (nghĩa là có bậc là số lẻ) là một số chẵn.
Chứng minh: Thực vậy gọi O và U tương ứng là tập đỉnh bậc lẻ và tập
đỉnh bậc chẵn của đồ thị. Ta có:
Do deg(v) là chẵn với v là đỉnh trong U nên tổng thứ hai trong vế phải ở trên là số chẵn. Từ đó suy ra tổng thứ nhất (chính là tổng bậc của các đỉnh bậc lẻ) cũng phải là số chẵn, do tất cả các số hạng của nó là số lẻ, nên tổng này phải gồm một số chẵn các số hạng. Vì vậy, số đỉnh bậc lẻ phải là số chẵn. Ta xét các thuật ngữ tương tự cho đồ thị có hướng.
Định nghiã 3: Nếu e = (u, v) là cung của đồ thị có hướng G thì ta nối hai đỉnh u và v là kề nhau, và nói cung (u,v) nối đỉnh u với đỉnh v hay cũng nói cung này là đi ra khỏi đỉnh u và đi vào đỉnh v. Đỉnh u(v) sẽ được gọi là đỉnh đầu (cuối) của cung (u, v).
Tương tự như khái niệm bậc, đối với đồ thị có hướng ta có khái niệm bán bậc ra (vào) của một đỉnh.
Định nghĩa 4: Ta gọi bán bậc ra (bán bậc vào) của các đỉnh v trong đồ thị có hướng là số cung của đồ thị đi ra khỏi nó (đi vào nó) và ký hiệu là deg+(v) (deg(v)).
Định lý 2: Giả sử G = (V,E) là đồ thị có hướng. Khi đó
Rất nhiều tính chất của đồ thị có hướng không phụ thuộc vào hướng trên các cung của nó. Vì vậy, trong nhiều trường hợp sẽ thuận tiện hơn nếu ta bỏ qua hướng trên các cung của đồ thị. Đồ thị vô hướng thu được bằng cách bỏ qua hướng trên các cung được gọi là đồ thị vô hướng tương ứng với dồ thị có hướng đã cho.
1.3. Đường đi, chu trình, đồ thị liên thông.
Định nghĩa 1: Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên dương, trên đồ thị vô hướng G =(V,E) là dãy x0, x1, … ,xn-1,xn trong đó u =x0, v=xn , (xi, xi+1) Ỵ E, i= 0, 1, 2… , n-1. Đường đi nói trên còn có thể biểu diễn dưới dạng dãy các cạnh: (x0, x1), (x1, x2), …, (xn-1, xn).
Đỉnh u gọi là đỉnh đầu còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có đỉnh đầøu trùng với đỉnh cuối (tức là u= v) được gọi là chu trình. Đường đi hay chu trình được gọi là đơn nếu như không có cạnh nào bị lặp lại.
Định nghĩa 2: Đường đi độ dài n từ đỉnh u đến đỉnh v trong đó n là số nguyên dương, trên đồ thị vô hướng G =(V, A) là dãy x0, x1, … ,xn-1,xn trong đó u =x0, v=xn , (xi, xi+1) ỴA, i= 0, 1, 2… , n-1. Đường đi nói trên còn có thể biểu diễn dưới dạng dãy các cung: (x0, x1), (x1, x2), …, (xn-1, xn).
Đỉnh u gọi là đỉnh đầu còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có đỉnh đầøu trùng với đỉnh cuối (tức là u= v) được gọi là chu trình. Đường đi hay chu trình được gọi là đơn nếu như không có cung nào bị lặp lại.
Định nghĩa 3: Đồ 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ó.
Như vậy hai máy tính bấy kỳ trong mạng có thể trao đổi thông tin được với nhau khi và chỉ khi đồ thị tương ứng vơi mạng này là đồ thị liên thông.
Định nghĩa 4: Ta gọi đồ thị con của đồ thị G= (V,E) là đồ thị H = (W,F) trong đó W Í V và FÍE.
Trong trường hợp đồ thị là liên thông, nó sẽ rã ra thành một số đồ thị con liên thông đôi một không có đỉnh chung. Những đồ thị con liên thông như vậy ta sẽ gọi là các thành phần liên thông của đồ thị.
Định nghĩa 5: Đỉnh v được gọi là đỉnh rẽ nhánh nếu việc loại bỏ v cùng với các cạnh liên thuộc với nó khỏi đồ thị làm tăng số thành phần liên thông của đồ thị. Cạnh e được gọi là cầu nếu việc loại bỏ nó khỏi đồ thị làm tăng số thành phần liên thông của đồ thị.
Định nghĩa 6: Đồ thị có hướng G= (V,A) được gọi là liên thông mạnh nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó.
Định nghĩa 7: Đồ thị có hướng G =(V,A) được gọi là liên thông yếu nếu đồ thị vô hướng tương ứng với nó là đồ thị vô hướng liên thông.
Rõ ràng nếu đồ thị là liên thông mạnh thì nó cũng là liên thông yếu, nhưng điều ngược lại là không luôn đúng.
Định lý1: Đồ thị vô hướng liên thông là định hướng được khi và chỉ khi mỗi cạnh của nó nằm trên ít nhất một chu trình.
Chứng minh: Điều kiện cần, giả sử (u, v) là một cạnh của đồ thị. Sự tồn tại đường đi có hướng từ u đến v và ngược lại suy ra (u, v) phải nằm trên ít nhất một chu trình.
Điều kiện đủ, thủ tục sau đây cho phép định hướng các cạnh của đồ thi để thu được đồ thị có hướng liên thông mạnh. Giả sử C là chu trình nào đó trong đồ thị. Định hướng các cạnh trên chu trình này theo một hướng đi vòng theo nó. Nếu tất cả các cạnh của đồ thị đã được định hướng thì kết thúc thủ tục. Ngược lại chọn e là cạnh chưa định hướng có chung đỉnh với ít nhất một trong số các cạnh đã định hướng. Theo giả thiết tìm đựơc chu trình C’ chứa cạnh e định nghĩa các cạnh chưa định hướng của C’ theo một hướng dọc theo chu trình này (không định hướng lại các cạnh đã có hướng). Thủ tục trên sẽ lặp lại cho đến khi tất cả các cạnh của đồ thị được định hướng. Khi đó ta thu được đồ thị có hướng liên thông mạnh.
II. Biểu diễn đồ thị trên máy tính.
Để lưu trữ đồ thị và thực hiện các thuật toán khác nhau với đồ thị trên máy tính cần tìm những cấu trúc dữ liệu thích hợp để mô tả đồ thị. Việc chọn cấu trúc dữ liệu nào để biểu diễn đồ thị có tác động rất lớn đến hiệu quả của thuật toán. Vì vậy, việc chọn lựa cấu trúc dữ liệu để biểu diễn đồ thị phụ thuộc vào từng tình huống cụ thể (bài toán và thuật toán cụ thể ). Ở phần này ta sẽ xét một số phương pháp cơ bản để biểu diễn đồ thị trên máy tính, đồng thời cũng phân tích một cách ngắn gọn những ưu điểm cũng như những nhược điểm của chúng.
2.1. Ma trận kề, Ma trận trọng số.
Xét đơn đồ thị vô hướng G = (V,E), với tầp đỉnh V= {1, 2, …,n} tập cạnh E = {e1, e2,…, em}. Ta gọi ma trận kề của đồ thị G là (0, 1) ma trận A = {aij: i,j = 1, 2,… ,n}với các phần tử được xác định theo quy tắc sau đây:
aij =0 nếu (i,j) Ï E và aij =1 nếu (i,j)Ỵ E, i,j =1, 2,…,n
Thí dụ1: Ma trận kề củae đồ thị vô hướng cho trong hình 1 là:
0 1 1 0 0 0
1 0 1 0 1 0
1 1 0 1 0 0
0 0 1 0 1 1
0 1 0 1 0 1
0 0 0 1 1 0
1 2 3 4 5 6
1
2
3
4
5
6
3 4 2 5
1 6 1 4
2 5 3 6
G G1
Hình 1: Đồ thị vô hướng G và Đồ thị có hướng G1
Các tính chất của ma trận kề:
1. Rõ ràng ma trận kề của đồ thị vô hướng là ma trận đối xứng, tức là a[i, j]= a[j, i], i, j = 1, 2,…,n. Ngược lại, mỗi (0, 1) – ma trận đối xứng cấp n sẽ tương ứng chính xác đến cách đánh số đỉnh (còn nói là: chính xác đến đẳng cấu), với một đơn đồ thị vô hướng n đỉnh.
2. Tổng các phần tử trên dòng i (cột j) của ma trận kề chính bằng bậc của đỉnh i (đỉnh j).
3. Nếu ký hiệu aijp, i,j = 1, 2,…, n. Là các phần tử của ma trận Ap = A.A….A. p là thừa số, khi đó aijp, i,j = 1, 2,…, n. cho ta số đường đi khác nhau từ đỉnh i đến đỉnh j qua p –1 đỉnh trung gian.
Ma trận kề của đồ thị có hướng được định nghĩa một cách hoàn toàn tương tự.
Thí dụ 2: Đồ thị có hướng G1 cho trong hình 1 có ma trận kề là ma tr...
Hệ quả: Trong đồ thị vô hướng, số đỉnh bậc lẻ (nghĩa là có bậc là số lẻ) là một số chẵn.
Chứng minh: Thực vậy gọi O và U tương ứng là tập đỉnh bậc lẻ và tập
đỉnh bậc chẵn của đồ thị. Ta có:
Do deg(v) là chẵn với v là đỉnh trong U nên tổng thứ hai trong vế phải ở trên là số chẵn. Từ đó suy ra tổng thứ nhất (chính là tổng bậc của các đỉnh bậc lẻ) cũng phải là số chẵn, do tất cả các số hạng của nó là số lẻ, nên tổng này phải gồm một số chẵn các số hạng. Vì vậy, số đỉnh bậc lẻ phải là số chẵn. Ta xét các thuật ngữ tương tự cho đồ thị có hướng.
Định nghiã 3: Nếu e = (u, v) là cung của đồ thị có hướng G thì ta nối hai đỉnh u và v là kề nhau, và nói cung (u,v) nối đỉnh u với đỉnh v hay cũng nói cung này là đi ra khỏi đỉnh u và đi vào đỉnh v. Đỉnh u(v) sẽ được gọi là đỉnh đầu (cuối) của cung (u, v).
Tương tự như khái niệm bậc, đối với đồ thị có hướng ta có khái niệm bán bậc ra (vào) của một đỉnh.
Định nghĩa 4: Ta gọi bán bậc ra (bán bậc vào) của các đỉnh v trong đồ thị có hướng là số cung của đồ thị đi ra khỏi nó (đi vào nó) và ký hiệu là deg+(v) (deg(v)).
Định lý 2: Giả sử G = (V,E) là đồ thị có hướng. Khi đó
Rất nhiều tính chất của đồ thị có hướng không phụ thuộc vào hướng trên các cung của nó. Vì vậy, trong nhiều trường hợp sẽ thuận tiện hơn nếu ta bỏ qua hướng trên các cung của đồ thị. Đồ thị vô hướng thu được bằng cách bỏ qua hướng trên các cung được gọi là đồ thị vô hướng tương ứng với dồ thị có hướng đã cho.
1.3. Đường đi, chu trình, đồ thị liên thông.
Định nghĩa 1: Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên dương, trên đồ thị vô hướng G =(V,E) là dãy x0, x1, … ,xn-1,xn trong đó u =x0, v=xn , (xi, xi+1) Ỵ E, i= 0, 1, 2… , n-1. Đường đi nói trên còn có thể biểu diễn dưới dạng dãy các cạnh: (x0, x1), (x1, x2), …, (xn-1, xn).
Đỉnh u gọi là đỉnh đầu còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có đỉnh đầøu trùng với đỉnh cuối (tức là u= v) được gọi là chu trình. Đường đi hay chu trình được gọi là đơn nếu như không có cạnh nào bị lặp lại.
Định nghĩa 2: Đường đi độ dài n từ đỉnh u đến đỉnh v trong đó n là số nguyên dương, trên đồ thị vô hướng G =(V, A) là dãy x0, x1, … ,xn-1,xn trong đó u =x0, v=xn , (xi, xi+1) ỴA, i= 0, 1, 2… , n-1. Đường đi nói trên còn có thể biểu diễn dưới dạng dãy các cung: (x0, x1), (x1, x2), …, (xn-1, xn).
Đỉnh u gọi là đỉnh đầu còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có đỉnh đầøu trùng với đỉnh cuối (tức là u= v) được gọi là chu trình. Đường đi hay chu trình được gọi là đơn nếu như không có cung nào bị lặp lại.
Định nghĩa 3: Đồ 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ó.
Như vậy hai máy tính bấy kỳ trong mạng có thể trao đổi thông tin được với nhau khi và chỉ khi đồ thị tương ứng vơi mạng này là đồ thị liên thông.
Định nghĩa 4: Ta gọi đồ thị con của đồ thị G= (V,E) là đồ thị H = (W,F) trong đó W Í V và FÍE.
Trong trường hợp đồ thị là liên thông, nó sẽ rã ra thành một số đồ thị con liên thông đôi một không có đỉnh chung. Những đồ thị con liên thông như vậy ta sẽ gọi là các thành phần liên thông của đồ thị.
Định nghĩa 5: Đỉnh v được gọi là đỉnh rẽ nhánh nếu việc loại bỏ v cùng với các cạnh liên thuộc với nó khỏi đồ thị làm tăng số thành phần liên thông của đồ thị. Cạnh e được gọi là cầu nếu việc loại bỏ nó khỏi đồ thị làm tăng số thành phần liên thông của đồ thị.
Định nghĩa 6: Đồ thị có hướng G= (V,A) được gọi là liên thông mạnh nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó.
Định nghĩa 7: Đồ thị có hướng G =(V,A) được gọi là liên thông yếu nếu đồ thị vô hướng tương ứng với nó là đồ thị vô hướng liên thông.
Rõ ràng nếu đồ thị là liên thông mạnh thì nó cũng là liên thông yếu, nhưng điều ngược lại là không luôn đúng.
Định lý1: Đồ thị vô hướng liên thông là định hướng được khi và chỉ khi mỗi cạnh của nó nằm trên ít nhất một chu trình.
Chứng minh: Điều kiện cần, giả sử (u, v) là một cạnh của đồ thị. Sự tồn tại đường đi có hướng từ u đến v và ngược lại suy ra (u, v) phải nằm trên ít nhất một chu trình.
Điều kiện đủ, thủ tục sau đây cho phép định hướng các cạnh của đồ thi để thu được đồ thị có hướng liên thông mạnh. Giả sử C là chu trình nào đó trong đồ thị. Định hướng các cạnh trên chu trình này theo một hướng đi vòng theo nó. Nếu tất cả các cạnh của đồ thị đã được định hướng thì kết thúc thủ tục. Ngược lại chọn e là cạnh chưa định hướng có chung đỉnh với ít nhất một trong số các cạnh đã định hướng. Theo giả thiết tìm đựơc chu trình C’ chứa cạnh e định nghĩa các cạnh chưa định hướng của C’ theo một hướng dọc theo chu trình này (không định hướng lại các cạnh đã có hướng). Thủ tục trên sẽ lặp lại cho đến khi tất cả các cạnh của đồ thị được định hướng. Khi đó ta thu được đồ thị có hướng liên thông mạnh.
II. Biểu diễn đồ thị trên máy tính.
Để lưu trữ đồ thị và thực hiện các thuật toán khác nhau với đồ thị trên máy tính cần tìm những cấu trúc dữ liệu thích hợp để mô tả đồ thị. Việc chọn cấu trúc dữ liệu nào để biểu diễn đồ thị có tác động rất lớn đến hiệu quả của thuật toán. Vì vậy, việc chọn lựa cấu trúc dữ liệu để biểu diễn đồ thị phụ thuộc vào từng tình huống cụ thể (bài toán và thuật toán cụ thể ). Ở phần này ta sẽ xét một số phương pháp cơ bản để biểu diễn đồ thị trên máy tính, đồng thời cũng phân tích một cách ngắn gọn những ưu điểm cũng như những nhược điểm của chúng.
2.1. Ma trận kề, Ma trận trọng số.
Xét đơn đồ thị vô hướng G = (V,E), với tầp đỉnh V= {1, 2, …,n} tập cạnh E = {e1, e2,…, em}. Ta gọi ma trận kề của đồ thị G là (0, 1) ma trận A = {aij: i,j = 1, 2,… ,n}với các phần tử được xác định theo quy tắc sau đây:
aij =0 nếu (i,j) Ï E và aij =1 nếu (i,j)Ỵ E, i,j =1, 2,…,n
Thí dụ1: Ma trận kề củae đồ thị vô hướng cho trong hình 1 là:
0 1 1 0 0 0
1 0 1 0 1 0
1 1 0 1 0 0
0 0 1 0 1 1
0 1 0 1 0 1
0 0 0 1 1 0
1 2 3 4 5 6
1
2
3
4
5
6
3 4 2 5
1 6 1 4
2 5 3 6
G G1
Hình 1: Đồ thị vô hướng G và Đồ thị có hướng G1
Các tính chất của ma trận kề:
1. Rõ ràng ma trận kề của đồ thị vô hướng là ma trận đối xứng, tức là a[i, j]= a[j, i], i, j = 1, 2,…,n. Ngược lại, mỗi (0, 1) – ma trận đối xứng cấp n sẽ tương ứng chính xác đến cách đánh số đỉnh (còn nói là: chính xác đến đẳng cấu), với một đơn đồ thị vô hướng n đỉnh.
2. Tổng các phần tử trên dòng i (cột j) của ma trận kề chính bằng bậc của đỉnh i (đỉnh j).
3. Nếu ký hiệu aijp, i,j = 1, 2,…, n. Là các phần tử của ma trận Ap = A.A….A. p là thừa số, khi đó aijp, i,j = 1, 2,…, n. cho ta số đường đi khác nhau từ đỉnh i đến đỉnh j qua p –1 đỉnh trung gian.
Ma trận kề của đồ thị có hướng được định nghĩa một cách hoàn toàn tương tự.
Thí dụ 2: Đồ thị có hướng G1 cho trong hình 1 có ma trận kề là ma tr...