Định nghĩa cơ bản

Trước hết, hãy làm rõ một số khái niệm cơ bản: Đường đi: Một dãy các đỉnh sao cho các đỉnh kề nhau có cạnh nối trong đồ thị Đường đi đơn: Một đường đi không đi qua cạnh nào hai lần Chu trình: Một đường đi đơn mà điểm bắt đầu và kết thúc giống nhau

Đường đi Euler: Một đường đi đơn đi qua tất cả các cạnh của đồ thị đúng một lần Chu trình Euler: Một chu trình đi qua tất cả các cạnh của đồ thị đúng một lần Đồ thị Euler: Một đồ thị có chu trình Euler Đồ thị bán Euler: Một đồ thị có đường đi Euler

Điều kiện để tồn tại chu trình/đường đi Euler

Đối với đồ thị có hướng:

Tồn tại chu trình Euler khi và chỉ khi tất cả các đỉnh có bậc vào bằng bậc ra, và đồ thị liên thông

Chứng minh: Điều này rõ ràng là điều kiện cần, chỉ cần chứng minh điều kiện đủ. Xem xét chọn một đỉnh bất kỳ, lấy nó làm điểm bắt đầu thực hiện thuật toán dfs cho đến khi quay lại chính nó. Vì bậc vào bằng bậc ra, quá trình này luôn có thể thực hiện được. Phần còn lại của đồ thị được chia thành các thành phần liên thông, vẫn thỏa mãn điều kiện bậc vào bằng bậc ra. Vì không liên thông chắc chắn là do xóa các cạnh đã tìm, nên nếu mỗi thành phần liên thông có chu trình Euler, ghép chúng với vòng tìm được sẽ tạo thành một chu trình Euler mới. Lặp lại quá trình này, cuối cùng sẽ còn đúng một chu trình, nên điều kiện là đủ.

Tồn tại đường đi Euler khi và chỉ khi chính xác hai đỉnh không thỏa mãn bậc vào bằng bậc ra, hiệu giữa bậc ra và bậc vào lần lượt là +1 và -1, và đồ thị liên thông

Chứng minh: Nếu tồn tại đường đi Euler, thêm một cạnh từ điểm cuối đến điểm đầu, tạo thành chu trình Euler. Xóa cạnh này đi sẽ thỏa mãn điều kiện trên, chứng minh tính cần thiết. Nếu thỏa mãn điều kiện trên, thêm một cạnh từ điểm cuối đến điểm đầu sẽ tạo thành chu trình Euler, xóa cạnh này đi sẽ tồn tại đường đi Euler, chứng minh tính đủ.

Đối với đồ thị vô hướng: Kết quả tương tự, liên quan đến tính chẵn/lẻ của bậc đỉnh.

Đối với đồ thị hỗn hợp: Có một bài ví dụ dưới đây.

Giải pháp tìm chu trình Euler

Một cách tiếp cận tự nhiên là mô phỏng điều kiện xác định, mỗi lần tìm một chu trình và giải quyết đệ quy, nhưng cách này khá phức tạp. Hãy xem xét một phương pháp đơn giản hơn.

Chúng ta thường xây dựng đồ thị một cách tường minh, nhưng liệu có thể làm khác không? Xem xét việc sau khi tìm xong một chu trình, ta không thêm ngay chu trình này vào, mà thêm các chu trình của các thành phần liên thông trước, sau đó mới thêm chu trình này. Thứ tự này có lợi ích gì? Ta thấy thứ tự thêm chu trình phù hợp với thứ tự dfs, nên mỗi lần quay lui (backtrack) ta có thể thêm vào ngay lập tức, và chỉ cần một lần dfs là giải quyết xong.

Các bài toán ví dụ

Bài toán mẫu

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=1e5+5,M=2e5+5;
int n,m,in[N],stk[M],top,hd[N];
vector<int>e[N];
void dfs(int x){
  int cnt=0;
  for(int &i=hd[x];i<e[x].size();) dfs(e[x][i++]),++cnt;
  stk[++top]=x;assert(cnt<=2);
  return ;
}
int main(){
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  cin>>n>>m;
  for(int i=1;i<=m;i++){
    int u,v;cin>>u>>v;
    e[u].pb(v),++in[v];
  }
  int fg=1,rt=0;
  for(int i=1;i<=n;i++){
    sort(e[i].begin(),e[i].end());
    if(abs(int(e[i].size())-in[i])>1){ fg=0; }
    else if(e[i].size()>in[i]){
      if(rt){ fg=0; }
      else rt=i;
    }
  }
  if(!fg){ cout<<"Khong the tao duong di Euler"<<'\n'; return 0; }
  dfs(rt?rt:1);
  if(top!=m+1){ cout<<"Khong the tao duong di Euler"<<'\n'; }
  else{
    reverse(stk+1,stk+top+1);
    for(int i=1;i<=top;i++) cout<<stk[i]<<" ";
  }
  return 0;
}

Chuỗi từ

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int N=1e3+5;
int n,in[27],hd[27],top;
string s[N],stk[N];
vector<pair<string,int> >e[27];
void dfs(int x){ 
  for(int &i=hd[x];i<e[x].size();){
    auto d=e[x][i++];
    dfs(d.se);stk[++top]=d.fi;
    //Lưu ý việc thêm cạnh phải đặt bên trong, vì một tầng có thể có nhiều cạnh ra, có lẽ tối đa là hai
    //Một là tìm vòng lặp tìm thấy, còn lại là các thành phần liên thông đệ quy tìm vòng lặp
    //Cân nhắc tại sao quay lui dfs có thể thêm ngay
    //Đối với cái đầu tiên, chắc chắn là các điểm sau trong vòng lặp đã hoàn thành, quay lui tại điểm hiện tại hoặc quay về điểm trước đó thêm vào, điều này là đúng
    //Đối với cái thứ hai, chắc chắn là cạnh đầu tiên bắt đầu từ x để tìm chu trình Euler trong thành phần liên thông, khi quay lui thì các cạnh khác đã thêm hết, nên là đúng.
  } 
  return ;
}
int main(){
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>s[i];
    int chfi=s[i][0]-'a'+1,chlst=s[i][s[i].size()-1]-'a'+1;
    e[chfi].pb(mp(s[i],chlst)),++in[chlst]; 
  }
  int fg=1,rt=0,mn=0;
  for(int i=1;i<=26;i++){
    if(!e[i].empty() && !mn) mn=i;
    sort(e[i].begin(),e[i].end());
    if(abs((int)e[i].size()-in[i])>1){ fg=0; }
    else{
      if(e[i].size()>in[i]){
        if(rt) fg=0;
        else rt=i;
      }
    }
  }
  if(!fg){ cout<<"Khong the tao chuoi tu"<<'\n'; return 0; }
  dfs(rt?rt:mn);
  if(top!=n){ cout<<"Khong the tao chuoi tu"<<'\n'; return 0; }
  reverse(stk+1,stk+top+1);
  for(int i=1;i<=top;i++){
    cout<<stk[i];
    if(i!=top) cout<<".";
  } 
  return 0;
}

SMI-Rác thải

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
const int N=1e5+5,M=1e6+5;
int n,m,hd[N],stk[M],cnt,vis[M*2],in[N];
vector<pair<int,int>>e[N];
vector<vector<int>>ans;
void dfs(int x){
  for(int &i=hd[x];i<e[x].size();){
    auto p=e[x][i++];
    if(vis[p.second]) continue;
    vis[p.second]=1;
    dfs(p.first);
  } 
  if(in[x]){
    vector<int>vec;
    vec.pb(x);
    while(stk[cnt]!=x) in[stk[cnt]]=0,vec.pb(stk[cnt--]);
    vec.pb(x);ans.pb(vec);
  }
  else stk[++cnt]=x,in[x]=1;
  return ;
}
int main(){
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  cin>>n>>m;
  for(int i=1;i<=m;i++){
    int u,v,s,t;cin>>u>>v>>s>>t;
    if(u==v || s==t) continue;
    e[u].pb(mp(v,i)),e[v].pb(mp(u,i));
  }
  int fg=1;
  for(int i=1;i<=n;i++){
    if(e[i].size()&1){ fg=0; }
  }
  if(!fg){ cout<<"Khong the giai quyet"<<'\n'; return 0; }
  for(int i=1;i<=n;i++){ 
    if(hd[i]!=e[i].size()){ cnt=0,dfs(i); }
  }
  cout<<ans.size()<<'\n';
  for(auto x:ans){
    cout<<x.size()-1<<" ";
    for(auto y:x) cout<<y<<" ";
    cout<<'\n';
  }
  return 0;
}

Các bài trên đều phân tích về trường hợp tồn tại chu trình Euler. Trong bài 1 và 2, cũng có thể tồn tại đường đi Euler, nhưng thực ra cách thức khôi phục các điểm hoặc cạnh trên đường đi đều giống nhau, vì có thể giả sử rằng cạnh đầu tiên là từ điểm cuối đến điểm đầu, biến thành chu trình Euler, chỉ là không xét đến ảnh hưởng của cạnh này trong kết quả cuối cùng.

Bài toán nâng cao:

LIS-The Postman: Cần bổ sung MOS-Cầu: Cần bổ sung Johnny and Megan's Necklace: Cần bổ sung Flip and Reverse: Cần bổ sung