====== الگوریتم فلوری برای گراف‌های بی‌جهت ======


===== تعریف =====

طبق تعریف تور اویلری، گراف G بدون جهت با درجات زوج داده شده است. حال الگوریتم فلوری را برای یافتن تور اویلری در آن معرفی می‌کنیم.

===== الگوریتم =====

در گراف G داده شده، جهت پیدا کردن تور اویلری طبق الگوریتم فلوری به این صورت عمل می‌کنیم که؛

۱) اگر گراف رأس با درجه فرد نداشته باشد از رأسی دلخواه شروع می‌کنیم.

۲) اگر گراف دو رأس با درجه فرد داشته باشد از یکی از آن دو رأس شروع می‌کنیم.

۳) سایر گراف‌ها تور اویلری ندارند.


از رأس انتخاب شده شروع به گذر از یال‌ها می‌کنیم به نحوی که تا هر‌جا که ممکن باشد یالی را به عنوان یال بعدی انتخاب می‌کنیم که پس از عبور از آن گراف باقی‌مانده همبند بماند، در صورتی که چنین یالی وجود نداشته باشد یال باقی‌مانده متصل به رأس کنونی را انتخاب می‌کنیم.

با توجه به زوجیت درجات رئوس اثبات می‌شود که با غیر قابل گسترش شدن گذر، یال پیمایش نشده‌ای وجود نخواهد داشت. بنابراین گذر پیمایش شده تور اویلری مورد نظر خواهد بود. اگر گراف داده شده از نوع ۱ باشد تور پیمایش شده دور اویلری خواهد بود و در حالت ۲ تور پیمایش شده یک مسیر اویلریست.




===== پیچیدگی‌ الگوریتم =====

در پیمایش گذر مربوطه هر یال دقیقا یک بار مورد بررسی قرار می‌گیرد که در نتیجه پیچیدگی آن از $O(E)$ می‌باشد.
از طرفی در هر مرحله از پیمایش نیاز به یافتن یال‌های برشی داریم که با استفاده از الگوریتم تارجان به پیچیدگی $O(E^2)$ می‌رسیم.

===== پیاده‌سازی اولیه =====

<code c A.c>
#inlcude<iostream>
#include<vector>
#include<map>
using namespace std;

const int max_nodes = 100, max_edges;

vector<pair<int, int> > adj[max_nodes];

bool cut[max_edges], seen[max_edges];

void mark_cut_edges(){
	//set the cut of the cut edges true and others false
	//cut edges should be determined on the graph of edges which haven't been seen yet
}

void trail(int node){
	mark_cut_edges();
	bool could_exit = false;
	for(int i = 0; i < adj[node].length(); i++){
		int edge = adj[node][i];
		if(!seen[edge.secend] && cut[edge.second]){
			cout<<edge.second<<endl;//output the number of the edge
			seen[edge.second] = true;
			trail(edge.first);
			could_exit = true;
			break;
		}
	}
	if(!could_exit){//could not find any non-cut edge
		for(int i = 0; i < adj[node].length(); i++){
			int edge = adj[node][i];
			if(!seen[edge.secend]){
				cout<<edge.second<<endl;//output the number of the edge
				seen[edge.second] = true;
				trail(edge.first);
				could_exit = true;
				break;
			}
		}
	}
}

int main(){
	int n, m;
	cin>> n>> m;
	for(int i = 0; i < m; i++){
		int x, y;
		cin>> x>> y;
		x--; y--;
		adj[x].push_back(make_pair(y, i));
		adj[y].push_back(make_pair(x, i));
	}
	trail(0);
}
</code>

===== کابردها =====


**مثال**:
در گراف روبه‌رو تور اویلری بیابید.

{{ :آموزش:الگوریتم:felury2.png?200 |}}

<پاسخ>

فرض کنید مانند شکل از رأس F شروع کنیم و به ترتیب زیر یال‌ها را بپیماییم:


{{ :آموزش:الگوریتم:felury3.png?200 |}}


{{ :آموزش:الگوریتم:felury4.png?200 |}}


{{ :آموزش:الگوریتم:felury5.png?200 |}}

در این مرحله یال AB یال برشی است بنابراین نباید از آن عبور کنیم.


{{ :آموزش:الگوریتم:felury6.png?200 |}}


{{ :آموزش:الگوریتم:felury7.png?200 |}}

بدین‌ترتیب تنها با در نظر داشتن برشی بودن یال‌ها در هر مرحله تور اویلری را به دست آوردیم.


</پاسخ>


===== مسائل نمونه =====
[[http://codeforces.com/contest/508/problem/D|نمونه مسأله در کدفورسز]]

===== مراجع =====

  * [[https://en.wikipedia.org/wiki/Eulerian_path]]