Thứ Hai, 12 Tháng 10, 2015 - Bài Tập Chuyên Nghành

Trang chủ » đường đi Euler Và Chu Trình Euler được Ra đời Từ Bài Toán Nào » Thứ Hai, 12 Tháng 10, 2015 - Bài Tập Chuyên Nghành

Có thể bạn quan tâm

Tổng số khách Online :
  • Home
  • Phim Bộ
  • Phim Lẻ
  • Đề Cử
  • Phim TVB
  • Phim 18+
  • WWE
  • Phim Hài Hước
  • Quốc Gia
    • Việt Nam
    • Hồng Kông
    • Trung Quốc
    • Âu - Mỹ
    • Thái Lan
    • Nhật Bản
  • Bóng Đá Online
Chúc bạn có những giờ phút thư giản thoải mái :sexy:

Bạn Đang Xem ›

Tự tắt sau 15s!Click vào để tắt ngay! Bấm để cập nhật phim mới !
  • » Nhấn thích hoặc +1 nếu phim hay bạn nhé!
  • »Có đang xem phim này.
  • » Các bạn xem phim nên ấn nút tạm dừng khoảng 30s - 1 phút rồi tiếp tục xem phim để không bị giật.
  • » Nếu bạn không xem được phim vui lòng nhấn Ctrl + F5 vài lần. Hoặc chuyển sang Server khác để xem.
  • » Xem phim nhanh hơn với trình duyệt Firefox và Google Chrome , Cờ Rôm +
  • Bình luận
  • Nội dung phim
LỜI MỞ ĐẦULeonhard Euler là 1 nhà toán học và nhà vật lí học Thụy Sỹ, sinh ngày 15-4-1707 tại thành phố Basel. Từ nhỏ ông đã tỏ ra có tài năng ttrong môn toán học nhưng cha ông muốn ông học giáo lí và trở thành mộtmục sư. Năm 1720, Euler bắt đầu học tại Đại học Basel và trong thời kì này cha ông cũng cho phép ông học toán . Ông đã có những công trình xuất sắc về toán học và đặc biệt là thành công của thuật toán Euler.Bắt đầu từ bài báo của Euler công bố năm 1736 liên quan đến lời giải bài toán nổitiếng về các cây cầu ở Konigsberg. Tại thành phố Konigsberg nước Đức có sôngPregel bao quanh 2 đảo lớn. Hai đảo này được nối với các vùng đất thành phốbởi 7 cây cầu. Cư dân thành phố đặt ra bài toán: có thể xuất phát tại một điểm vàđi qua 7 cây cầu, mỗi cây cầu chỉ được đi qua đúng một lần, và trở về điểm xuấtphát được không? Và nhà toán học L.Euler đã trả lời trọn vẹn cho bài toán này. Người ta lấy tên cho bài toán trên là tên của nhà toán học Euler. Tuy nhiên, chotới nay mối quan tâm đến lý thuyết đồ thị không hề suy giảm. Lý do của sự quantâm ấy chính là sự vận dụng rộng rãi của đồ thị trong rất nhiều lĩnh vực khác . Nội dung của thuật toán euler được trình bày như sau. Một là giới thiệu về đồ thi euler mà trọng tâm là xoay quanh bài toán bảy cây cầu euler từ đó đưa ra được các khái niệm, định nghĩa về đồ thị euler và nửa euler. Nêu ra các ứng dụng tích cực của đồ thị euler. Hai là nêu ra các định lý euler với việc chứng minh phù hợp, dể hiểu, dễ nắm bắt,dễ tiếp nhận Ba là cài đặt thuật toán euler trên c/c++.Với việc xoay quanh các vấn đề chính.Nêu ý tưởng bài toán tìm chu trình euler bằng thuật toán fluery và cài đặt.Từ đó,đưa ra kết quả thu được ra màn hình Bốn là đánh giá ưu,nhược điểm của thuật toán nhất là trong đời sống thực tiễn.từ đó,thấy được những điểm nổi bật của thuật toán euler. Và cuối cùng,cùng với việc nêu là những nội dung chính,quan trọng liên quan tới thuật toán euler thì đưa ra những tài liệu tham khảo cần thiết làm quen đến thuật toán phù hợp với việc vận dụng Mục Lục I.Giới thiệu đồ thị euler 1.1:Bài toán bảy cây cầu 1.2Định nghĩa 1.3Ứng dụng II.Định lý euler 2.1Định lý 1 2.2Hệ quả 2.3Định lí 2và thuật toán flor 2.4 Các tính chất III. Cài đặt thuật toán euler trên c/c++ 3.1 Ý tưởng 3.2 Giải thích 3.3Cài đặt 3.4 Kết quả IV. Đánh giá thuật toán V. Tài liệu tham khảo I.Giới thiệu đồ thị euler 1.1:Bài toán bảy cây cầu Bài toán bảy cây cầu Eulercòn gọi làBảy cầu ở Konigsbergnảy sinh từ nơi chốn cụ thể. Thành phố Konigsberg, Đức (nay là Kaliningrad, Nga) nằm trên sôngPregel, bao gồm hai hòn đảo lớn nối với nhau và với đất liền bởi bảy cây cầu. Bài toán đặt ra là tim một tuyến đường mà đi qua mỗi cây cầu một lần và chỉ đúng một lần (bất kể điểm xuất phát hay điểm tới). Năm1736,Leonhard Eulerđã chứng minh rằng điều đó là không thể được. Người ta kể rằng, khoảng năm1750, vào các ngày Chủ nhật, những người dân giàu có và học thức của thành phố đã đi dạo quanh để tìm cách giải bài này, nhưng đây có lẽ chỉ là một truyền thuyết. Để chứng minh kết quả, Euler đã phát biểu bài toán bằng các thuật ngữ củalý thuyết đồ thị. Ông loại bỏ tất cả các chi tiết ngoại trừ các vùng đất và các cây cầu, sau đó thay thế mỗi vùng đất bằng một điểm, gọi làđỉnhhoặcnút, và thay mỗi cây cầu bằng một đoạn nối, gọi làcạnhhoặcliên kết. Cấu trúc toán học thu được được gọi là mộtđồ thị. Hình thù của đồ thị có thể bị bóp méo theo đủ kiểu nhưng không làm đồ thị bị thay đổi, miễn là các liên kết giữa các nút giữ nguyên. Việc một liên kết thẳng hay cong, một nút ở bên phải hay bên trái một nút khác là không quan trọng. Euler nhận ra rằng bài toán có thể được giải bằng cách sử dụngbậccủa các nút. Bậc của một nút là số cạnh nối với nó, trong đồ thị các cây cầu Konigsberg, ba nút có bậc bằng 3 và một nút có bậc 5. Euler đã chứng minh rằng một chu trình có dạng như mong muốn chỉ tồn tại khi và chỉ khi không có nút bậc lẻ. Một đường đi như vậy được gọi là mộtchu trình Euler. Do đồ thị các cây cầu Konigsberg có bốn nút bậc lẻ, nên nó không thể có chu trình Euler. 1.2 Định nghĩa Định nghĩa : Chu trình đơn trong G đi qua mỗi cạnh của nó một lần được gọi là chu trình euler.Đường di đơn trong G đi qua mỗi cạnh của nó một lần được gọi là đường đi euler.Đồ thị được gọi là đồ thị euler nếu nó có chu trình euler,và gọi là đồ thị nửa euler nếu nó có đường đi euler ·Dây chuyền Euler: dây chuyền đi qua tất cả các cạnh trongđồ thị,mỗi cạnh được đi qua đúng một lần. ·Chu trình Euler: dây chuyền Euler có đỉnh đầu trùng với đỉnh cuối. ·Đường đi Euler (Đồ thị có hướng): đường đi qua tất cả các cạnh củađồ thị , mỗi cạnh được đi qua đúng một lần. ·Mạch Euler (Đồ thị có hướng) : đường đi Euler có đỉnh đầu trùng với đỉnh cuối. ·Đồ thị Euler vô hướng:đồ thị vô hướngcó chứa một chu trình Euler. ·Đồ thị Euler có hướng:đồ thị có hướng có chứa một mạch Euler. Hình 3: Ví dụ về đồ thị Euler ·Đồ thị được gọi làđồ thị Eulernếu cóchu trình (mạch) Euler, và gọi làđồ thị nửa Eulernếu nó códây chuyền (đường đi) Euler. Ví dụ 1: Đồ thị G1 trong hình 1 là đồ thị Euler vì nó có chu trình Euler a, e, c, d, e, b, a. Đồ thị G3 không có chu trình Euler nhưng nó có đường đi Euler a, c, d, e, b, d, a, b, vì thế G3 là đồ thị cửa Euler. Đồ thị G2 không có chu trình cũng như đường đi Euler. Hình 1 : Đồ thị G 1 , G 2 , G 3 . ·Vídụ 2: (Hình 2) ·Đồ thị H2 là đồ thị Euler vì nó cómạch Eulera - b - c - d - e - a. ·Đồ thị H3 không cómạch Eulernhưng nó cóđường đi Euler c - a - b - c - d - b vì thế H3 là đồ thị nửa Euler. ·Đồ thị H1 không cómạch Eulercũng nhưđường đi Euler. Hình 2: Đồ thị Euler - Đồ thị nửa Euler (có hướng) 1.3 Ứng dụng ·Áp dụng thuật toán tìm đường đi và chu trình Euler trong một số bài toán điển hình và bài toán Thanh tra giao thông. ·Để giải các bài toán chuyển động II.Định lý euler 2.1 Định lí 1 ·Đồ thị vô hướng liên thông G là đồ thị Euler khi và chỉ khi mọi đỉnh của G đều có bậc chẵn. Chứng minh định lí Định lí 1: Để chứng minh định lí trước hết ta phải chứng minh bổ đề : Bổ đề: Nếu bậc của mỗi đỉnh của đồ thị G không nhỏ hơn 2 thì G chứa chu trình Chứng minh :nếu G có cạnh lặp thì khẳng định của bồ đề là hiển nhiên.vì vậy giả sử G là đơn đồ thị.Gọi v là một đỉnh nài đó của G.Ta sẽ xây dựng theo quy nạp đường đi v->v1->v2->…. trong đó v1là đỉnh kề với v, còn với i ≥ 1, chọn vi+1là đỉnh kề với vivà vi+1≠ vi-1(có thể chọn như vậy vìdeg(vi) ≥ 2), v0= v. Do tập đỉnh của (G) là hữu hạn, nên sau một số hữu hạn bước ta phải quay lại 1 đỉnh đã xuất hiện trước đó. Gọi k là số nguyên dương đầu tiên để vk= vi. Khi đó, đường đi vi, vi+1,...., vk-1, vklà mộtchu trình đơn cần tìm ·Điều kiện cần:Giả sử G là đồ thị Euler tức là tồn tại chu trình Euler P trong G. Khi đó cứ mỗi lần chu trình P đi qua một đỉnh nào đó của G bậc của đỉnh đó tăng lên 2. mặt khác mỗi cạnh của đồ thị xuất hiện trong P đúng một lần, suy ra mỗi đỉnh của đồ thị điều có bậc chẵn. ·Điều kiện đủ: quy nạp theo số cạnh của G. Do G liên thông và deg(v) là số chẵn nên bậc của mỗi đỉnh của nó không nhỏ hơn 2. Từ đó theo bổ đề G phải chứa chu trình C. Nếu C đi qua tất cả các cạnh của G thì nó chính là chu trình Euler. Giả sử C không đi qua tất cả các cạnh của G. Khi đó loại bỏ khỏi G tất cả các cạnh thuộc C ta thu được một đồ thị mới H vẫn có bậc là chẵn. Theo giả thiết qui nạp, trong mỗi thành phần liên thông của H điều tìm được chu trình Euler. Do G là liên thông nên trong mỗi thành phần của H có ít nhất một đỉnh chung với chu trình C. Vì vậy, ta có thể xây dựng chu trình Euler trong G như sau: bắt đầu từ một đỉnh nào đó của chu trình C, đi theo các cạnh của C chừng nào chưa gặp phải đỉnh không cô lập của H. Nếu gặp phải đỉnh như vậy ta sẽ đi theo chu trình Euler của thành phần liên thông của H chứa đỉnh đó. Sau đó lại tiếp tục đi theo cạnh của C cho đến khi gặp phải đỉnh không cô lập của H thì lại theo chu trình Euler của thành phần liên thông tương ứng Quá trình sẽ kết thúc khi ta trở về đỉnh xuất phát , tức là thu được chu trình đi qua mỗi cạnh của đồ thị đúng một lần. 2.2 Hệ quả ·Hệ quả:Đồ thị liên thông(G) là nửa Euler (mà không là Euler) khi và chỉ khi có đúng 2 đỉnhbậclẻ trong (G). ·Chứng minh:Nếu (G) làđồ thị nửa Eulerthì tồn tại mộtđường đi Eulertrong (G) từ đỉnh u đến đỉnh v. Gọi (G') là đồ thị thu được từ (G) bằng cách thêm vào cạnh (u,v). Khi đó (G') làđồ thị Eulernên mọi đỉnh trong (G') đều cóbậcchẵn (kể cả u và v). Vì vậy u và v là 2 đỉnh duy nhất trong (G) cóbậc lẻ. Đảo lại, nếu có đúng 2 đỉnhbậclẻ là u và v thì gọi (G') là đồ thị thu được từ (G) bằng cách thêm vào cạnh (u,v). Khi đó mọi đỉnh của (G') đều cóbậcchẵn hay (G') làđồ thị Euler. Bỏ cạnh (u,v) đã thêm vào ra khỏichu trình Eulertrong (G') ta có đượcđường đi Eulertừ u đến v trong (G) hay (G) làđồ thị nửa Euler. 2.3Định lí 2 và thuật toán Flor Xuất phát từ một đỉnh của G ta đi theo các cạnh của nó một cách tùy ý chỉ cần tuân thủ 2 quy tắc sau: 1.Xóa bỏ cạnh đã đi qua và đồng thời xóa cả những đỉnh cô lập tạo thành. 2.Ở mỗi bước ta chỉ đi qua cầu khi không còn cách lựa chọn nào khác Chứng minh tính đúng đắn của thuật toán : Trước tiên ta chỉ ra rằng thủ tục trên có thể thực hiện được ở mỗi bước.Giả sử ta đi đến một đỉnh v nào đó,khi đó nếu v#u thì đồ thị còn lại H là liên thông và chứa đúng hai đỉnh bậc lẻ là v và u.Theo hệ quả trong H có đường đi euler P từ v đến u.Do việc xóa bỏ cạnh đầu tiên của đường đi P không làm mất tính liên thông của H,từ đó suy ra thủ tục có thể thực hiện ở mỗi bước.Nếu v=u thì lập luận ở trên sẽ vẫn đúng chừng nào vẫn còn cạnh kề với u. Như vậy chỉ còn phải chỉ ra là thủ tục trên dẫn đường đi euler.Thực vậy trong G khổng thể còn cạnh chưa đi qua khi mà ta sử dụng cạnh cuối cùng kề với u Chứng minh tương tự như trong định lí 1 ta thu được kết quả sau đây cho đồ thị có hướng ·Định lí 2: Đồ thị có hướng liên thông mạnh là đồ thị euler khi và chỉ khi Deg*(v)=deg-(v) 2.4 Các tính chất ·Một đồ thị vô hướng là đồ thị Euler nếu nó liên thông và có thể phân tích thành các chu trình có các cạnh rời nhau. ·Nếu đồ thị vô hướngGlà Euler thìđồ thị đườngL(G) cũng là Euler. ·Đồ thị có hướng là Euler nếu nó liên thông và mọi đỉnh của nó cóbậc vàobằngbậc ra. ·Đồ thị có hướng là Euler nếu nó liên thông và có thể phân tích thành các chu trình có hướng với các cung rời nhau. III. Cài đặt thuật toán euler trên c/c++ 3.1 Ý tưởng Sử dụng thuật toán fluery để tìm chu trình euler trong đồ thị G. 3.2 Giải thích Cho G = (V, E) là một đồ thị Euler. Bước 1. Bắt đầu với i = 0 và định nghĩa T0 = v0. Bước 2. Đặt Ti= v0e1v1e2…eiviei là đường đi giữa v0 và vi tại bước thứ i, gọi Ei = {e1,e2,…,ei}, G’ là đồ thị con sau khi xóa các cạnh thuộc Ei trong G: G’= G – Ei. Chọn một cạnh e(i+1) nối vi với v(i+1) từ tập cạnh E – Ei. Lưu ý là nếu e(i+1) là một cạnh cầu trong đồ thị con G’, chỉ chọn nó khi và chỉ khi không còn lựa chọn nào khác. Cập nhật Ti+1 = Tie(i+1)v(i+1)= v0e1v1e2…eivie(i+1)v(i+1). Nếu không còn lựa chọn nào cho cạnh e(i+1) thì dừng. Bước 3. Gán i = i+1, quay lại bước 2. 3.3 Cài đặt ·Input: file văn bản input.txt ·Dòng 1: Chứa số đỉnh n của đồ thị ·Các dòng tiếp theo là ma trận kề của đồ thị ·Output: file văn bản output.txt ghi chu trình euler ·Ví dụ:
Input.txt
9 0 1 0 1 0 1 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0
Output.txt
1 2 4 1 6 7 3 4 5 8 9 4 7 1
#include <iostream> #include <fstream> #include <string> #include <vector> using namespace std; ifstream infile("input.txt"); ofstream outfile("output.txt"); bool euler(vector<vector<int>> edge); bool fleury(vector<vector<int>> edge, vector<int> del); vector<vector<int>>erase(vector<vector<int>> edge, vector<int> del); bool empty(vector<vector<int>> edge); int main(){ int n, i, j; infile>>n; vector<vector<int>> edge; int val; for(i=0; i<n; i++){ vector<int> row; for(j=0; j<n; j++) { infile>>val; row.push_back(val); } edge.push_back(row); } if(euler(edge)){ cout<<"Chu trinh Euler: "<<endl; vector<int> circuit; int current=0; circuit.push_back(current); cout<<current + 1<<" "; while(!empty(edge)){ for(i=0; i<n; i++){ int previous=current; if(edge[current][i]==1){ vector<int> del; del.push_back(current); del.push_back(i); if(fleury(edge, del)){ edge=erase(edge,del); current=i; circuit.push_back(current); cout<<current + 1<<" "; break; } } } } for(i=0; i<circuit.size(); i++){ outfile<<circuit[i] + 1<<" "; } cout<<endl<<"Chu trinh Euler da duoc ghi vao file output.txt."<<endl; }else{ cout<<"Khong tim duoc chu trinh Euler."<<endl; } system("PAUSE"); return 0; } bool euler(vector<vector<int>> edge){ for(int i=0; i<edge.size(); i++){ int deg=0; for(int j=0; j<edge[0].size(); j++){ deg+=edge[i][j]; } if(deg%2!=0){ return false; } } return true; } bool fleury(vector<vector<int>> edge, vector<int> del){ int n, i, j, k; if(del[0]==del[1]){ return false; } vector<vector<int>> edged=edge; edged[del[0]][del[1]]=0; edged[del[1]][del[0]]=0; n= edged[0].size(); //Kh?i t?o b?ng const int infinity=1000000; vector<bool> known; for(i=0; i<n; i++){ known.push_back(false); } vector<int> d; d.push_back(0); for(i=1; i<n; i++){ d.push_back(infinity); } vector<int> p; for(i=0; i<n; i++){ p.push_back(-1); } for(k=0; k<n; k++) { int min=0; while(known[min]==true){ min++; } for(i=0; i<n; i++){ if(known[i]==false && d[i]<d[min]){ min=i; } } known[min]=true; for(j=0; j<n; j++){ if(edged[min][j]!=0 && d[j]>edged[min][j] && known[j]==false){ d[j]=edged[min][j]; p[j]=min; } } } bool ok=true; for(i=1;i<n; i++){ if(p[i]==-1){ for (int j=0; j<n; j++){ if(edged[i][j]!=0){ ok=false; break; } } } } return ok; } vector<vector<int>> erase(vector< vector<int>> edge, vector<int> del){ vector< vector<int>> edged=edge; edged[del[0]][del[1]]=0; edged[del[1]][del[0]]=0; return edged; } bool empty(vector<vector<int>> edge){ for(int i=0; i<edge.size(); i++){ for(int j=0; j<edge[0].size(); j++){ if(edge[i][j]==1){ return false; } } return true; } } 3.3 Kết quả Xem thêm: ·Bài toán người đưa thư trung hoa ·Bài toán ghép tên IV.Đánh giá thuật toán ·Tính xác định: các bước rõ ràng, thực hiện được ra một kết quả. ·Tính hữu hạn: có số bước nhất định và điểm kết thúc ·Tính kết quả: dữ liệu phù hợp , thuật toán cho kết quả đúng yêu cầu ·Tính phổ dụng: áp dụng được cho nhiều bài toán khác có cùng cấu trúc, với các dữ liệu khác nhau ·Tính hiệu quả: đơn giản, dễ hiểu, tối ưu hóa bộ nhớ và thời gian thực hiện ·Tính hình thức: từng bước trong thuật toán luôn thực hiện đúng như kịch bản (chương trình ) mà không biết đến mục tiêu cuối cùng ( không tự suy đoán ) ·Tính đúng đắn: thuật toán cho kết quả đúng ·Giải thuật thực hiện nhanh V. Tài liệu tham khảo ·Chap_13_Graph Algorithms ·Fleury's Algorithm ·Đồ thị Euler_Giải thuật và lập trình. Tác giả: Lê Minh Hoàng ·The_Mathematics_of_Getting_Around

Còn nhiều phim hot bạn đã xem chưa?

Bài đăng Mới hơn Trang chủ Nhấn +1 để xem nhanh hơn : Thể Loại Phim
  • Phim Bộ
  • Phim Lẻ
  • Đề Cử
  • Phim TVB
  • Phim 18+
  • WWE
Quốc Gia
  • Top Xem Tuần
  • Tháng
  • Năm
  • (không có tiêu đề) Lượt xem: Đang cập nhật
  • Bài tập CSDL Lượt xem: Đang cập nhật
  • (không có tiêu đề) Lượt xem: Đang cập nhật
  • Bài tập CSDL Lượt xem: Đang cập nhật
  • (không có tiêu đề) Lượt xem: Đang cập nhật
  • (không có tiêu đề) Lượt xem: Đang cập nhật
  • (không có tiêu đề) Lượt xem: Đang cập nhật
  • Bài tập CSDL Lượt xem: Đang cập nhật
  • (không có tiêu đề) Lượt xem: Đang cập nhật
Đào Văn Trí. Được tạo bởi Blogger. Bài Tập Chuyên Nghành

blogger giải bài tập chuyên nghành nhóm 6 đại học tin k6 (Đại Học Thành Đô)

nhóm 6

Unknown Xem hồ sơ hoàn chỉnh của tôi

Blogge

Lưu trữ Blog

  • ▼  2015 (2)
    • ▼  tháng 10 (2)
      • Bài tập CSDL
      •                  LỜI MỞ ĐẦU    

Tin tức blogger

Tổng số lượt xem trang

Sparkline Vn141.com - Xem phim online miễn phí, chất lượng hình ảnh rõ nét, tốc độ tải phim nhanh, xem phim online không phải chờ đợi lâu, luôn cập nhật phim mới để để mang đến cho các bạn những bộ TVB phim 18+ , các thể loại phim tâm lý, tình cảm cực lôi cuốn và hấp dẫn nhất. Đặc biệt website rất thân thiện với người dùng và hạn chế tối đa các quảng cáo gây khó chịu khi Xem phim online . Chúc các bạn Xem phim online vui vẻ. - Sitemaps - Rss - Liên hệ quảng cáo Hỗ trợ

Liên hệ : Phía bên trên

Weblinks: Phim 18+, Phim TVB, Phim Bộ, Phim Lẻ, WWE Show, Phim Đề Cử, Phim Hài Hước, Phim Việt Nam, Phim Hồng Kông, Phim Thái Lan , Phim Âu Mỹ

Từ khóa » đường đi Euler Và Chu Trình Euler được Ra đời Từ Bài Toán Nào