플 로 레 알고리즘 오로라 (오 일 러) 통로 / 회로

1. 기본 개념:
(1) 오 라 도의 기본 개념:
오로라 통로 (오 라 적): 그림 속 의 각 변 을 통 해 한 번 만, 그리고 모든 정점 의 통 로 를 통과 합 니 다.
오 라 회 로 (오로라 폐 적): 그림 속 의 모든 변 을 통 해 한 번 만, 그리고 모든 정점 의 회 로 를 지나 갑 니 다.
오 라 토: 오 라 회 로 가 있 는 그림.오 라 토 는 한 정점 에서 출발 하여 각 변 을 한 번 에 다시 출발점 으로 돌아 갈 수 있 는 그림 이다. 즉, 모든 변 을 반복 하지 않 고 다시 출발점 으로 돌아 가 는 것 이다.
통로 와 회로: vie1e 2... envj 를 하나의 종 으로 한다. 도착 하 다 vj 이 고 길 이 는 n 의 통로 이 며 그 중에서 길 이 는 통로 의 중간 에 있 는 줄 수 를 말 합 니 다. 출발점 과 종점 이 같은 통 로 를 하나의 회로 라 고 합 니 다.
간단 한 그림: 평행 변 과 자체 회로 가 없 는 그림.
혼합 도: 방향 도 있 고 방향 도 없 는 그림 도 있다.
평범한 그림: 하나의 결점 만 있 는 그림
완전 도: n 개의 결점 이 있 고 모든 결점 이 서로 연 결 된 무 방향 간단 도 를 무 방향 완전 도 라 고 한다.n 개의 결점 이 있 고 모든 결점 사이 에 두 방향 이 반대 되 는 변 이 연결 되 어 있 는 방향 이 있 는 간단 한 그림 은 완전 도 이다.
(2) 오 라 토의 특징: 무방 향도
a) G 오 라 통로 의 충분 한 필요조건 은: G 연결, G 중 두 개의 기이 한 정점 만 있다.
b) G 는 오 라 회 로 (G 는 오 라 투) 가 있 고 G 는 모두 우 도 정점 이다.  지향 도
a) D 는 오로라 통로 가 있다. D 연결 은 두 개의 정점 을 제외 하고 나머지 정점 의 입 도 는 모두 출 도 와 같다. 이 두 개의 특수 한 정점 중 하 나 는 정점 의 입 도 는 출 도 보다 1 크 고 다른 정점 의 입 도 는 출 도 보다 1 작다.
b) D 는 오 라 회 로 (D 는 오 라 투) 가 있 습 니 다. D 는 연결 되 고 D 의 모든 정점 의 입 도 는 출 도 와 같 습 니 다.하 나 는 오로라 그림 이 고 이 그림 의 모든 정점 도수 가 0 일 때 만 있다.
2
플 로 레
) 알고리즘 사상 - 오로라 회로 해결
    Fleury 알고리즘:   v0 * 8712 ° V (G), 명령 P0 = v0;
Pi = v0e1v1e 2 를 설정 합 니 다. ei vi 는 이미 실행 되 었 습 니 다. 아래 방법 에 따라 ei + 1 을 선택 하 십시오.
(a) ei + 1 은 vi 와 관련 이 있다.
(b) 다른 쪽 이 없 는 한 줄 을 다 닐 수 있 습 니 다. 그렇지 않 으 면 ei + 1 은 Gi = G - {e1, e2 가 아 닙 니 다. …, ei} 의 다리 (다리 란 삭제 후 연결 그림 이 연결 되 지 않 는 가장자리);
(c) 더 이상 진행 할 수 없 을 때 알고리즘 이 정지 합 니 다.
알고리즘 이 정지 되 었 을 때 얻 은 간단 한 회로 Wm = v0e1v1e 2... emvm (vm = v0) 은 G 중의 한 오 라 회 로 이 고 복잡 도 는 O (e * e) 임 을 증명 할 수 있다.
3
오로라 알고리즘 C
언어 설명

void DFS(Graph &G,SqStack &S,int x,int t)
{
       k=0;//    ,                     
       Push(S,x); //             
       for(i=t;i0)  
         {
          k=1;
          G[i][x]=0; G[x][i]=0; //     ,    
          DFS(G,S,i,0);//         ,       x   i, 
                        //        i    
          break;
         }//if,for
       if(k==0)       //  k=0,              
       {
              Pop(S);
              GetTop(S,m);
              G[x][m]=1;G[m][x]=1;//            
              a=x+1;//      ,                
              if(StackLength(S)!=e)//    ,         
              {
                     Pop(S); //       
                     DFS(G,S,m,a);//
              }//if
              else   //    ,        
                     Push(S,x);
       }//if
}//DFS
 
void Euler(Graph &G,int x)
{
//G         ,         ,  1    ,0    ,      ,x    
InitStack(S);//               
DFS(G,S,x,0);//        ,0       
//  
 while(!StackEmpty(S))
 {
  GetTop(S,m);
  printf("->v%d",m);
  Pop(S);
 }//while
}//Euler

다음 알고리즘 을 위 한 그림 동적 과정:
4. 오로라 알고리즘 의 C 실현

#include "SqStack.h" //       
#include "Queue.h"//       
 
typedef int Graph[200][200];
int v,e;
 
void DFS(Graph &G,SqStack &S,int x,int t)
{
       int k=0,i,m,a;
       Push(S,x);
       for(i=t;i0)
              {
                     k=1;
                     G[i][x]=0; //    
                     G[x][i]=0;
                     DFS(G,S,i,0);
                     break;
              }//if,for
       if(k==0)
       {
              Pop(S);
              GetTop(S,m);
              G[x][m]=1;//        
              G[m][x]=1;
              a=x+1;//         
              if(StackLength(S)!=e)
              {
                     Pop(S);
                     DFS(G,S,m,a);
              }//if
              else
                     Push(S,x);
       }//if
}//DFS
 
int BFSTest(Graph G)
{
       int a[200],x,i,k=0;
       LinkQueue Q;
       InitQueue(Q);
       EnQueue(Q,0);
       for(i=0;i0)
                            if(a[i]!=1)
                            {
                                   a[i]=1;
                                   EnQueue(Q,i);
                            }//if
       }//while
       for(i=0;iv%d",m);
              Pop(S);
       }//while
}
 
void InputM1(Graph &G)
{
 
int h,z;
printf("Please input       
");
scanf("%d",&v);
scanf("%d",&e);
for(int i=0;i

   5，   6
     1 2
          1 3
          2 5
          4 2
          3 2
          4 5

5. 작은 상식: 오로라 알고리즘 의 시작 과 한 획 의 문제
7 교 문제: 18 세기 유명한 고전 수학 문제 중의 하나.고 니스 버그 의 한 공원 에는 일곱 개의 다리 가 프 레 그 강 중 두 개의 섬 과 섬 을 강기슭 과 연결 시 켰 다 (그림 참조).-- 이 네 개의 육지 중 어느 하나 에서 출발 할 수 있 는 지, 마침 다 리 를 한 번 건 너 다시 출발점 으로 돌아 갈 수 있 을 까?오 라 는 1736 년 에 이 문 제 를 연구 하고 해결 했다. 그 는 문 제 를 다음 과 같은 오른쪽 그림 의 '한 획 의 그림' 문제 로 귀결 시 켜 상술 한 방법 이 불가능 하 다 는 것 을 증명 했다.
한 획:
『 9352 』 우 점 으로 구 성 된 연통 도 는 반드시 한 획 으로 그 릴 수 있다.그림 을 그 릴 때 어떤 짝 점 을 기점 으로 할 수 있 고 마지막 에 반드시 이 점 을 종점 으로 이 그림 을 다 그 릴 수 있다.
『 93535 』 두 개의 기이 한 점 만 있 는 연통 도 (나머지 는 모두 우 점) 는 반드시 한 획 으로 그 릴 수 있다.그림 을 그 릴 때 는 반드시 하나의 기이 한 점 을 기점 으로 하고, 다른 기이 한 점 의 종점 을 그 려 야 한다.
『 9354 』 다른 상황 의 그림 은 한 획 으로 그 릴 수 없다.(기 점 수 를 2 로 나 누 면 이 그림 은 몇 획 으로 그 려 야 하 는 지 계산 할 수 있다.)