مسیر اویلری

[computer-student]

سلام مساله زیر جک می کنه یک مسیر اویلری هست یا نه، چطور می تونیم تمام مسیر های اویلری یک گراف رو چاپ کنیم؟


// A C++ program to check if a given graph is Eulerian or not
#include<iostream>
#include <list>
using namespace std;

// A class that represents an undirected graph
class Graph
{
int V; // No. of vertices
list<int> *adj; // A dynamic array of adjacency lists
public:
// Constructor and destructor
Graph(int V) {this->V = V; adj = new list<int>[V]; }
~Graph() { delete [] adj; } // To avoid memory leak

// function to add an edge to graph
void addEdge(int v, int w);

// Method to check if this graph is Eulerian or not
int isEulerian();

// Method to check if all non-zero degree vertices are connected
bool isConnected();

// Function to do DFS starting from v. Used in isConnected();
void DFSUtil(int v, bool visited[]);
};

void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
adj[w].push_back(v); // Note: the graph is undirected
}

void Graph::DFSUtil(int v, bool visited[])
{
// Mark the current node as visited and print it
visited[v] = true;

// Recur for all the vertices adjacent to this vertex
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i, visited);
}

// Method to check if all non-zero degree vertices are connected.
// It mainly does DFS traversal starting from
bool Graph::isConnected()
{
// Mark all the vertices as not visited
bool visited[V];
int i;
for (i = 0; i < V; i++)
visited[i] = false;

// Find a vertex with non-zero degree
for (i = 0; i < V; i++)
if (adj[i].size() != 0)
break;

// If there are no edges in the graph, return true
if (i == V)
return true;

// Start DFS traversal from a vertex with non-zero degree
DFSUtil(i, visited);

// Check if all non-zero degree vertices are visited
for (i = 0; i < V; i++)
if (visited[i] == false && adj[i].size() > 0)
return false;

return true;
}

/* The function returns one of the following values
0 --> If grpah is not Eulerian
1 --> If graph has an Euler path (Semi-Eulerian)
2 --> If graph has an Euler Circuit (Eulerian) */
int Graph::isEulerian()
{
// Check if all non-zero degree vertices are connected
if (isConnected() == false)
return 0;

// Count vertices with odd degree
int odd = 0;
for (int i = 0; i < V; i++)
if (adj[i].size() & 1)
odd++;

// If count is more than 2, then graph is not Eulerian
if (odd > 2)
return 0;

// If odd count is 2, then semi-eulerian.
// If odd count is 0, then eulerian
// Note that odd count can never be 1 for undirected graph
return (odd)? 1 : 2;
}

// Function to run test cases
void test(Graph &g)
{
int res = g.isEulerian();
if (res == 0)
cout << "Graph is not Eulerian\n";
else if (res == 1)
cout << "Graph has a Euler path\n";
else
cout << "Graph has a Euler cycle\n";
}

// Driver program to test above function
int main()
{
// Let us create and test graphs shown in above figures
Graph g1(5);
g1.addEdge(1, 0);
g1.addEdge(0, 2);
g1.addEdge(2, 1);
g1.addEdge(0, 3);
g1.addEdge(3, 4);
test(g1);

Graph g2(5);
g2.addEdge(1, 0);
g2.addEdge(0, 2);
g2.addEdge(2, 1);
g2.addEdge(0, 3);
g2.addEdge(3, 4);
g2.addEdge(4, 0);
test(g2);

Graph g3(5);
g3.addEdge(1, 0);
g3.addEdge(0, 2);
g3.addEdge(2, 1);
g3.addEdge(0, 3);
g3.addEdge(3, 4);
g3.addEdge(1, 3);
test(g3);

// Let us create a graph with 3 vertices
// connected in the form of cycle
Graph g4(3);
g4.addEdge(0, 1);
g4.addEdge(1, 2);
g4.addEdge(2, 0);
test(g4);

// Let us create a graph with all veritces
// with zero degree
Graph g5(3);
test(g5);

return 0;
}

[a.r.khoshghalb]

سلام
خیلی خوشحالم که بعد از مدت ها یکی یه سوال علمی پرسید!
انقدر سوالات مسخره دیده بودیم تو این چند وقت که دیگه ...

من اول برای اینکه ممکنه بعضی از دوستان ندونند دور یا مسیر اویلری چیه یه توضیح کوچیکی بدم!

توی یک گراف، به یک مسیر میگیم مسیر اویلری اگر از یک راس شروع بشه، از همه یال ها بگذره و به یک راس دیگه تموم شه.
توی یک گراف، به یک دور میگیم دور اویلری اگر از یک راس شروع شه و از همه یال ها بگذره و به راسی که ازش شروع کردیم هم تموم شه.

شرط اینکه یک گراف دور اویلری داره یا نه چیه!
یک گراف دور اویلری دارد اگر و تنها اگر همبند باشه و درجه همه راس ها زوج باشه!
اگر هم همبند باشه و درجه دقیقا 2 راس هم فرد باشه مسیر اویلری داره!
اثباتشون رو خواستی بگو بهت بگم.

حالا در جواب سوال شما که گفتی همه مسیر های اویلری، گراف اگر 2 تا راس فرد داشته باشه که خوب واضحه مسیر از یکیشون شروع میشه و به اون یکی تموم میشه اگر هم نداشته باشه کلا مسیر اویلری نداره! پس حداکثر یک مسیر اویلری داره گراف!
اما میتونه چند دور اویلری داشته باشه!

برای پیدا کردن یک مسیر (یا یک دور) اویلری توی یک گراف 3 تا الگوریتم معروف وجود داره (در واقع من 3 تا میشناسم!)

الگوریتم اول اسمش فلوری هست! به این صورته که شما توی گراف از یک راس شروع می کنی (اگر راس با درجه فرد داری از راس با درجه فرد!) و به یکی از یال های اون راس میری و یال رو حذف می کنی. باز میرسی به یک راس و توی اون دوباره یکی از یال هاش رو میری و حذفش می کنی. اما همیشه اولویت با یال غیر برشی هست یعنی اگر یال غیر برشی داشت اون رو بری اگر نه از یک یال برشی بری. (یال برشی یا همون cut-edge میدونی چیه؟ اگر نمیدونستی بگو بگم.)

الگوریتم دیگه اسمش رو نمیدونم! این الگوریتم برای گرافی که راس با درجه فرد داشته باشه کار نمی کنه (در حالت کلی کار نمیکنه اگر یکمی فک کنی میبینی میتونی یه طوری تف بزنی که کار کنه(راهنمایی اینکه دو تا راسی که درجه فرد دارن رو به هم وصل کنی تا اونا هم درجه زوج داشته باشن!) ).
به این صورت هست که از یکی از راس های گرافت شروع می کنی و یکی از یال هاش رو میری به راس بعدی که رسیدی باز یکی از یال هاش رو میری (در طول مسیر، هر یالی رو که دیدیم حذف میکنیم از گراف) و انقدر اینکار رو می کنی تا به راسی که ازش شروع کردی برسی! الان یک دور پیدا کردی. حالا میری از یک راس دیگه که هنوز یال داره شروع میکنی و همین کار رو می کنی. اگر هیچ راسی نبود که یال داشته باشه تمومه.
حالا یه سری دور داری. تنها کاری که باید بکنی اینه که اینارو سر هم کنی تا بشه یک دور اویلری.
اینکار رو میتونی هم با لینکد لیست هم با وکتور انجام بدی.
من خیلی کلی میگم، اینکه چه جوری کدشو بنویسی با خودت. فرض کن الان دورهامون شدن اینا :
1 2 3 4 3 2 1
2 6 5 2
4 5 4
3 3
دور اویلری جواب میشه 1 2 6 5 2 3 3 4 5 4 3 2 1
برای اینکه قشنگ متوجه بشه چه جوری در آوردیم دور رو یه بار دیگه رنگی نشون میدم.
این ها دور هامون هستند:
1 2 3 4 3 2 1
2 6 5 2
4 5 4
3 3
میخوایم جواب رو بدست بیاریم. شروع می کنیم رو دور اول حرکت می کنیم به هر عددی رسیدیم میبینیم دور اون عدد رو تو جواب گذاشتیم یا نه. اگه نذاشته بودیم اون رو اضافه می کنیم به جواب.
در واقع جواب میشه :
1 2 6 5 2 3 3 4 5 4 3 2 1

الگوریتم بعدی رو هم نمی دونم اسمش چیه ولی چون توی یوساکو دیدمش بهش میگیم الگوریتم یوساکو :لبخند:
اینطوریه که میای DFS میزنی ولی راس ها رو مارک نمی کنی! بعد هر وقت به یک راسی رسیدی که یال نداشت و باید میرفتی به راس قبلی، این راسی که دیگه یال نداره رو میریزی توی یک وکتور یا آرایه. بعد اون وکتور رو اگه بر عکس چاپ کنی میشه دور اویلری!

حالا برای اینکه بیای همه دور های اویلری رو پیدا کنی، باید راسی که ازش شروع می کنی رو عوض کنی و الگوریتم رو اجرا کنی. (مسیر اویلری هم که گفتم حداکثر یکی داریم)

هر کدوم از الگوریتم ها رو اگر خواستی بدونی زمان اجراش چه قدره (از چه اوردریه) یا اثبات هر کدوم رو خواستی (به جز آخری که بلد نیستم :لبخند:) بگو بهت بگم. در کل هر جای دیگه رو هم اگر متوجه نشدی یا چیزی گفتم که نمیدونستی چیه بپرس.

یکم میگردم چند تا سوالی که با مسیر یا دور اویلری حل شه هم در جواب همین پست میذارم برات...

ویرایش :

حالا در جواب سوال شما که گفتی همه مسیر های اویلری، گراف اگر 2 تا راس فرد داشته باشه که خوب واضحه مسیر از یکیشون شروع میشه و به اون یکی تموم میشه اگر هم نداشته باشه کلا مسیر اویلری نداره! پس حداکثر یک مسیر اویلری داره گراف!
این حرف من غلط بود، میتونه از یک راس شروع شه و یکی تموم شه اما مسیر های متفاوتی داشته باشه. عذر خواهی میکنم.
فکر نمی کنم الگوریتمی باشه که با زمان خوب همه مسیر های اویلری رو بده چون تعدادشون میتونه خیلیــــــی زیاد بشه.
به هر حال امیدوارم پست ام بهت در رسیدن به جواب سوالت کمکت کنه. :لبخندساده:

[a.r.khoshghalb]

سوال یوساکو که با مسیر (یا دور) اویلری حل میشه:


PROBLEM STATEMENT

Riding the Fences




Farmer John owns a large number of fences that must be repaired annually. He traverses the fences by riding a horse along each and every one of them (and nowhere else) and fixing the broken parts.


Farmer John is as lazy as the next farmer and hates to ride the same fence twice. Your program must read in a description of a network of fences and tell Farmer John a path to traverse each fence length exactly once, if possible. Farmer J can, if he wishes, start and finish at any fence intersection.


Every fence connects two fence intersections, which are numbered inclusively from 1 through 500 (though some farms have far fewer than 500 intersections). Any number of fences (>=1) can meet at a fence intersection. It is always possible to ride from any fence to any other fence (i.e., all fences are "connected").


Your program must output the path of intersections that, if interpreted as a base 500 number, would have the smallest magnitude.


There will always be at least one solution for each set of input data supplied to your program for testing.




PROGRAM NAME: fence





INPUT FORMAT





Line 1:
The number of fences, F (1 <= F <= 1024)


Line 2..F+1:
A pair of integers (1 <= i,j <= 500) that tell which pair of intersections this fence connects.







SAMPLE INPUT (file fence.in)




9


1 2
2 3
4 2
3 4
4 5
5 7

2 5
5 6
4 6


OUTPUT FORMAT




[*=left]The output consists of F+1 lines, each containing a single integer. Print the number of the starting intersection on the first line, the next intersection's number on the next line, and so on, until the final intersection on the last line. There might be many possible answers to any given input set, but only one is ordered correctly.




SAMPLE OUTPUT (file fence.out)


1
2
3
4
2
5
4
6
5
7

[مسعود اقدسی فام]

ممنون از توضیحاتتون a.r.khoshghalb (http://barnamenevis.org/member.php?277700-a-r-khoshghalb).
چیزی که من از این سوال برداشت کردم این بود که ایشون این کد رو از جایی گیر آوردن و الان می‌خوان بدونن چطور باید ازش کمک بگیرن که بتونن کل مسیرهای اویلری رو نمایش بدن.
دز جواب computer-student (http://barnamenevis.org/member.php?341497-computer-student):
این کد در مورد اویلری بودن یه مسیر با تعریف دوستمون (که از یه راس شروع بشه و به راس مجزای دیگه ختم بشه) نیست. بلکه فقط تعیین می‌کنه یه گراف دور اویلری داره یا نه. در مورد دور اویلری بودن یه مسیر خاص هم نیست. برای این کار (ضمن بررسی پیوسته بودن گراف) تعداد رئوس با درجه‌ی فرد رو به دست می‌یاره. اگه تعداد صفر باشه که یعنی دور اویلری داره و اگه دو تا باشه یعنی شبه اویلری (فقط شامل مسیر اویلری) هست و اگه بیشتر از دو تا باشه یعنی ربطی به دور اویلری نداره! امکان هم نداره فقط یه راس با درجه‌ی فرد داشته باشیم.
حتی اگه منظور شما از مسیر اویلری همون دور اویلری باشه، بازم این کد کمکی بهتون نمی‌کنه. چون صرفا وجود یا عدم وجود رو با استفاده از دو تا شرط بررسی می‌کنه و اصلا پیمایش مختلف برای پیدا کردن مسیر رو نداره.
اگه گراف کامل باشد به ازای n راس (n-1) فاکتوریل دور مختلف با شروع از یه راس ثابت می‌شه تشکیل داد که خب به ازای nهای بزرگ خیلی عدد بزرگی می‌شه. اگه با شروع از همه‌ی رئوس مد نظر باشه که n فاکتوریل می‌شه و بزرگتر از قبل.

[computer-student]

همه ی توضیحاتتون خیلی عالی بود
آقای a.r.khoshghalb (http://barnamenevis.org/member.php?277700-a-r-khoshghalb) می شه اون سه الگوریتم رو پیچیدگی های زمانیشو بیان کنید و برنامه هاشو بهم بدید( لطفا:خجالت:) و پیچیدگی های فضاییشو بررسی کنیم خیلی دوس دارم این بحث رو بیشتر باز کنیم
آقای اقدسی فام از شما هم ممنونم بله من مسیر های اویلری رو می خوام نه دور های اویلری

[redflight]

سلام
از دیدن این تاپیکک بی نهایت خوشحال شدمممممممم چون من الان روی مسیر های همیلتونی دارم کار می کنم بعدش باید برم سراغ مسیر های اویلری:لبخند:


اگر هم همبند باشه و درجه دقیقا 2 راس هم فرد باشه مسیر اویلری داره!

یعنی اگر گرافی سه راس فرد داشته باشه دیگه مسیر اویلری نداره؟؟


الگوریتم اول اسمش فلوری هست! به این صورته که شما توی گراف از یک راس شروع می کنی (اگر راس با درجه فرد داری از راس با درجه فرد!) و به یکی از یال های اون راس میری و یال رو حذف می کنی. باز میرسی به یک راس و توی اون دوباره یکی از یال هاش رو میری و حذفش می کنی. اما همیشه اولویت با یال غیر برشی هست یعنی اگر یال غیر برشی داشت اون رو بری اگر نه از یک یال برشی بری. (یال برشی یا همون cut-edge میدونی چیه؟ اگر نمیدونستی بگو بگم.)

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

[redflight]

الگوریتم دیگه اسمش رو نمیدونم! این الگوریتم برای گرافی که راس با درجه فرد داشته باشه کار نمی کنه (در حالت کلی کار نمیکنه اگر یکمی فک کنی میبینی میتونی یه طوری تف بزنی که کار کنه(راهنمایی اینکه دو تا راسی که درجه فرد دارن رو به هم وصل کنی تا اونا هم درجه زوج داشته باشن!) ).
به این صورت هست که از یکی از راس های گرافت شروع می کنی و یکی از یال هاش رو میری به راس بعدی که رسیدی باز یکی از یال هاش رو میری (در طول مسیر، هر یالی رو که دیدیم حذف میکنیم از گراف) و انقدر اینکار رو می کنی تا به راسی که ازش شروع کردی برسی! الان یک دور پیدا کردی. حالا میری از یک راس دیگه که هنوز یال داره شروع میکنی و همین کار رو می کنی. اگر هیچ راسی نبود که یال داشته باشه تمومه.
حالا یه سری دور داری. تنها کاری که باید بکنی اینه که اینارو سر هم کنی تا بشه یک دور اویلری.
اینکار رو میتونی هم با لینکد لیست هم با وکتور انجام بدی.
من خیلی کلی میگم، اینکه چه جوری کدشو بنویسی با خودت. فرض کن الان دورهامون شدن اینا :
1 2 3 4 3 2 1
2 6 5 2
4 5 4
3 3
دور اویلری جواب میشه 1 2 6 5 2 3 3 4 5 4 3 2 1
برای اینکه قشنگ متوجه بشه چه جوری در آوردیم دور رو یه بار دیگه رنگی نشون میدم.
این ها دور هامون هستند:
1 2 3 4 3 2 1
2 6 5 2
4 5 4
3 3
میخوایم جواب رو بدست بیاریم. شروع می کنیم رو دور اول حرکت می کنیم به هر عددی رسیدیم میبینیم دور اون عدد رو تو جواب گذاشتیم یا نه. اگه نذاشته بودیم اون رو اضافه می کنیم به جواب.
در واقع جواب میشه :
1 2 6 5 2 3 3 4 5 4 3 2 1


خب پس این الگوریتم برای پیدا کردن مسیر های اویلری به درد نمی خوره درسته؟ :متفکر:
می تونیم بگیم چون گراف راس فردی نداشته در نتیجه مسیر اویلری ای هم نداره؟

[مسعود اقدسی فام]

می تونیم بگیم چون گراف راس فردی نداشته در نتیجه مسیر اویلری ای هم نداره؟

وقتی می‌خوایم گراف رو بگردیم، هر ورودی به یه راس باید یه خروج داشته باشه. غیر از راس آخر که مقصد هست. راس شروع هم که یه خروج اضافی داره و اگه دوباره واردش بشیم حتما باید خارج بشیم. پس این دو تا راس حتما باید درجه‌شون فرد باشه و بقیه باید حتما درحه‌شون زوج باشه تا بشه بینشون یک یا چند مسیر اویلری مختلف رو درست کرد.
پس در کل:
دور اویلری: همه زوج
مسیر اویلری: همه غیر از مبدا و مقصد زوج و اون دو تا فرد
یعنی اگه یه گرافی غیر از دو تا (صفر یا چهار یا شش ...) درجه‌ی فرد داشته باشه حتما مسیر نداره. اگه غیر از صفر هم باشه که دور هم نداره. اینی هم که فقط دو و چهار و شش رو نوشتم واسه اینه که توی یه گراف بدون جهت تعداد رئوس با درجه‌ی فرد حتما زوج هستش و امکان نداره فقط یدونه یا سه تا و هر عدد فرد دیگه‌ای راس با درجه‌ی فرد داشته باشه. اثباتشم راحته.

[computer-student]

وقتی می‌خوایم گراف رو بگردیم، هر ورودی به یه راس باید یه خروج داشته باشه. غیر از راس آخر که مقصد هست. راس شروع هم که یه خروج اضافی داره و اگه دوباره واردش بشیم حتما باید خارج بشیم. پس این دو تا راس حتما باید درجه‌شون فرد باشه و بقیه باید حتما درحه‌شون زوج باشه تا بشه بینشون یک یا چند مسیر اویلری مختلف رو درست کرد.
پس در کل:
دور اویلری: همه زوج
مسیر اویلری: همه غیر از مبدا و مقصد زوج و اون دو تا فرد
یعنی اگه یه گرافی غیر از دو تا (صفر یا چهار یا شش ...) درجه‌ی فرد داشته باشه حتما مسیر نداره. اگه غیر از صفر هم باشه که دور هم نداره. اینی هم که فقط دو و چهار و شش رو نوشتم واسه اینه که توی یه گراف بدون جهت تعداد رئوس با درجه‌ی فرد حتما زوج هستش و امکان نداره فقط یدونه یا سه تا و هر عدد فرد دیگه‌ای راس با درجه‌ی فرد داشته باشه. اثباتشم راحته.

برنامه ی مسیر اویلری را دارین؟:ناراحت:

[a.r.khoshghalb]

همه ی توضیحاتتون خیلی عالی بود
آقای a.r.khoshghalb (http://barnamenevis.org/member.php?277700-a-r-khoshghalb) می شه اون سه الگوریتم رو پیچیدگی های زمانیشو بیان کنید و برنامه هاشو بهم بدید( لطفا:خجالت:) و پیچیدگی های فضاییشو بررسی کنیم خیلی دوس دارم این بحث رو بیشتر باز کنیم
آقای اقدسی فام از شما هم ممنونم بله من مسیر های اویلری رو می خوام نه دور های اویلری

راستش خیلی حالشو ندارم کدشو بزنم :لبخند:. این کدی هست که من قبلا برای همین سوال یوساکو که گذاشتم زدم و اکسپت شده و از همین الگوریتم فلوری استفاده کردم. اگر هر جایی از کد مفهوم نبود یا سوالی بود بپرس حتما جواب میدم.
کد فلوری (http://pastebin.ubuntu.com/8386929/)

زمان اجرای الگوریتم فلوری از اوردر تعداد یال ها به توان 2 هست --> (O(E2
به این صورت که هر یال رو دقیقا یک بار می پیماییم(!) و برای هر یال هم چک می کنیم که cut-edge هست یا نه. البته خیلی راه هایی ارائه شده که یه جوری کدشو بزنین که کمتر باشه اوردرش ولی تفاوت چندانی نداره.

اینم کدیه که همون موقع برای همین سوال یوساکو زدم و اکسپت شده. الگوریتم این یکی اون الگوریتم DFS ایی هست (اونی که تو یوساکو خونده بودم)
باز هم اگر هر جایی از کد مفهوم نبود یا سوالی بود بپرس حتما جواب میدم.

کد DFS ایی :لبخند: (http://pastebin.ubuntu.com/8386980/)

زمان اجرای این برنامه اگر اشتباه نکنم از اوردر تعداد راس ها ضربدر تعداد یالهاست (اگر اشتباه کردم تصحیح کنید). --> (O(EV

کد اون یکی که تریل (trail) پیدا می کنه بعد با هم مرج (merge) می کنه رو ندارم. متاسفانه اون کد برای سوال یوساکو جواب نمیده چون یوساکو دور یا مسیر اویلری ای رو می خواد که لکسیکوگرافیکالی(!) (Lexicographicaly) کمینه (minimunm) باشه. به زودی کدشو میزنم و همینجا میذارمش.



سلام
از دیدن این تاپیکک بی نهایت خوشحال شدمممممممم چون من الان روی مسیر های همیلتونی دارم کار می کنم بعدش باید برم سراغ مسیر های اویلری:لبخند:

یعنی اگر گرافی سه راس فرد داشته باشه دیگه مسیر اویلری نداره؟؟

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

اول در رابطه با سوالتون که گفتین اگر گرافی 3 راس فرد داشته باشه دیگه مسیر اویلری نداره؟؟ شما اگر گرافی کشیدید که 3 راس با درجه فرد داشت من اون گراف رو از شما میخرم :لبخند:. هیچ گرافی تعداد فردی راس با درجه فرد نداره. (چرا؟ راحته یکم فکر کنید خودتون به نتیجه میرسید، خوشحال میشم این چیزی که گفتم رو اثبات کنید و اینجا بذارید تا با هم در رابطه با اثباتش صحبت کنیم)
برنامشو گذاشتم، چرا اتفاقا پیچیدگی زمانیش خیلی زیاد هم نیست.
تعریفی که از یال برشی کردید درست بود ولی فک کنم الگوریتم رو متوجه نشدید! الگوریتم دقیقا بر عکس چیزیه که شما گفتید، اولویت توی این الگوریتم با یال های غیر برشی هست. اگر یال غیر برشی نبود اون وقت از یک یال برشی میریم.


خب پس این الگوریتم برای پیدا کردن مسیر های اویلری به درد نمی خوره درسته؟ :متفکر:
می تونیم بگیم چون گراف راس فردی نداشته در نتیجه مسیر اویلری ای هم نداره؟
چرا همونطور که گفتم میشه اون دو تا راس فرد رو با یک یال به هم وصل کرد بعد دور اویلری ای رو پیدا کنیم که اون یالی که اضافه کردیم آخرین یال پیمایش شده باشه بعد حذفش کنیم از دور و بشه یک مسیر اویلری.
بله اگر گراف راس فردی نداشته باشه میشه نتیجه گرفت که مسیر اویلری هم نداره؟ (چرا؟ سعی کنید اثبات کنید این قضیه رو).

در کل تو این 3 الگوریتم به نظر من اونی که یوساکو نوشته بود از همه بهتره چون شما می تونید دقیقا همین الگوریتم رو بزنید و مسیر و دور اویلری رو توی گراف جهت دار هم پیدا کنید اما اونی که مرج (merge) می کنیم برای جهت دار کار نمیکنه و این فلوری هم برای جهت دار کار نمیکنه (2 تا فلوری هست! یه فلوری دیگه داریم که برای جهت دار هاست، تقریبا مشابه همینه...)
و این 3 الگوریتم خیلیییی چیزهای زیادی داره که باید اثبات شن ولی ما اثبات نکردیم و فقط گفتیمشون! اگر کسی علاقه داشت بگه که با هم ببینیم چه چیزهایی باید اثبات بشن و سر اثبات هاشون با هم بحث کنیم.

ویرایش:
الان کد ها رو یک بار دیگه نگاه کردم دیدم شاید بعضی از دوستان خیلی واضح نباشه براشون که کد چی کار می کنه.
به زودی کد هر 3 رو یک بار دیگه میزنم و میذارم.

[computer-student]

ویرایش:
الان کد ها رو یک بار دیگه نگاه کردم دیدم شاید بعضی از دوستان خیلی واضح نباشه براشون که کد چی کار می کنه.
به زودی کد هر 3 رو یک بار دیگه میزنم و میذارم.
یعنی از این کدها استفاده نکنم؟
کدهایی که میذاریذ همه مسیرهای اویلری را نشون می ده؟
بهترین الگوریتم کدوم هست؟
می شه سریع بزارید؟ تا کی می زارید؟

[computer-student]

کدها رو متوجه نمی شم، ورودی چی هست؟ کدها رو می شه کامنت گذاری کنین؟

[a.r.khoshghalb]

چشم تا چند دقیقه دیگه کد ها رو مینویسم دوباره و میذارم.

[omid_kma]

الگوریتم بعدی رو هم نمی دونم اسمش چیه ولی چون توی یوساکو دیدمش بهش میگیم الگوریتم یوساکو :لبخند:
اینطوریه که میای DFS میزنی ولی راس ها رو مارک نمی کنی! بعد هر وقت به یک راسی رسیدی که یال نداشت و باید میرفتی به راس قبلی، این راسی که دیگه یال نداره رو میریزی توی یک وکتور یا آرایه. بعد اون وکتور رو اگه بر عکس چاپ کنی میشه دور اویلری!
مطمئن هستین چیزی که گفتید درسته ؟؟ و با این میشه مسیر اویلری پیدا کرد ؟
وقتی که راس ها رو مارک نمیزنی چطور می خواهی بفهمی دیگه یال نداریم ؟( فرض کنید گراف شکل یک مثلث هست این طوری بینهایت بار دور خودمون می چرخیم)
الگوریتمی که من دیدم بر مبنای DFS هست اسمش HierHolzer هست که زیاد شبیه توضیحاتی که دادید نیست

[redflight]

وقتی می‌خوایم گراف رو بگردیم، هر ورودی به یه راس باید یه خروج داشته باشه. غیر از راس آخر که مقصد هست. راس شروع هم که یه خروج اضافی داره و اگه دوباره واردش بشیم حتما باید خارج بشیم. پس این دو تا راس حتما باید درجه‌شون فرد باشه و بقیه باید حتما درحه‌شون زوج باشه تا بشه بینشون یک یا چند مسیر اویلری مختلف رو درست کرد.
پس در کل:
دور اویلری: همه زوج
مسیر اویلری: همه غیر از مبدا و مقصد زوج و اون دو تا فرد
یعنی اگه یه گرافی غیر از دو تا (صفر یا چهار یا شش ...) درجه‌ی فرد داشته باشه حتما مسیر نداره. اگه غیر از صفر هم باشه که دور هم نداره. اینی هم که فقط دو و چهار و شش رو نوشتم واسه اینه که توی یه گراف بدون جهت تعداد رئوس با درجه‌ی فرد حتما زوج هستش و امکان نداره فقط یدونه یا سه تا و هر عدد فرد دیگه‌ای راس با درجه‌ی فرد داشته باشه. اثباتشم راحته.
درسته ممنونم....


اول در رابطه با سوالتون که گفتین اگر گرافی 3 راس فرد داشته باشه دیگه مسیر اویلری نداره؟؟ شما اگر گرافی کشیدید که 3 راس با درجه فرد داشت من اون گراف رو از شما میخرم :لبخند:. هیچ گرافی تعداد فردی راس با درجه فرد نداره. (چرا؟ راحته یکم فکر کنید خودتون به نتیجه میرسید، خوشحال میشم این چیزی که گفتم رو اثبات کنید و اینجا بذارید تا با هم در رابطه با اثباتش صحبت کنیم)
این که بله :لبخند: من گراف های جهت دار رو در نظر گرفتم و یال های خروجی رو مساوی با درجه اون راس در نظر گرفتم....
الگوریتم های شما برای گراف های جهت دار هم جواب می ده؟

تعریفی که از یال برشی کردید درست بود ولی فک کنم الگوریتم رو متوجه نشدید! الگوریتم دقیقا بر عکس چیزیه که شما گفتید، اولویت توی این الگوریتم با یال های غیر برشی هست. اگر یال غیر برشی نبود اون وقت از یک یال برشی میریم.
درسته من اشتباه بیانش کردم درست می گین

[redflight]

شما الان سه تا الگوریتم گفتین که یکیش (O(E2 هست یکیش هم O(EV)هست و اون سومی هم نگفتین....
اما مگه complexity time برای مسیرهای اویلری O(V+E) نبوده؟؟؟؟

بهترین الگوریتم موجود برای مسیرهای اویلری چیه ؟ الگوریتم های parallel ای هم براش دارین؟

[a.r.khoshghalb]

درسته ممنونم....
الگوریتم های شما برای گراف های جهت دار هم جواب می ده؟

اول اینکه اینا الگوریتم های من نیستند :لبخند:
گفتم، توی ایناها اون DFS اییه فقط جواب میده واسه جهت دار. یه نوع فلوری هم هست که اونم جواب میده.

[a.r.khoshghalb]

مطمئن هستین چیزی که گفتید درسته ؟؟ و با این میشه مسیر اویلری پیدا کرد ؟
وقتی که راس ها رو مارک نمیزنی چطور می خواهی بفهمی دیگه یال نداریم ؟( فرض کنید گراف شکل یک مثلث هست این طوری بینهایت بار دور خودمون می چرخیم)
الگوریتمی که من دیدم بر مبنای DFS هست اسمش HierHolzer هست که زیاد شبیه توضیحاتی که دادید نیست

بله مطمئن هستم :لبخندساده:
عرض کردم راس ها رو مارک نمی کنیم. یال رو که مارک می کنیم.
برای منم خیلی درکش سخته که چرا کار می کنه و تا حالا حتی تلاش هم نکردم اثباتش کنم! اگر اثبات کردید برای ما هم بذارید استفاده کنیم!
در ضمن HierHolzer اون الگوریتم دومی هست که گفتم. که میریم تریل پیدا می کنیم بعد مرج میکنیم.

[a.r.khoshghalb]

کدها رو متوجه نمی شم، ورودی چی هست؟ کدها رو می شه کامنت گذاری کنین؟

کد فلوری رو دوباره نوشتم و گذاشتم.
یکم طولانی شد ولی تلاش کردم تا جای ممکن قابل فهم باشه! امیدوارم مشکلی نباشه!
در ضمن اگر تستی دادی به کد و غلط دراومد بهم بگو درست کنم! خیلی تست نکردم کد رو. روش درسته ولی شاید یه جایی تو کد باگ زده باشم.
کد فلوری (http://pastebin.ubuntu.com/8389502/)

کد اون 2 تای دیگرو هم به زودی میزارم.

[redflight]

اول اینکه اینا الگوریتم های من نیستند :لبخند:
گفتم، توی ایناها اون DFS اییه فقط جواب میده واسه جهت دار. یه نوع فلوری هم هست که اونم جواب میده.

computer-student نگفته گراف جهت دار یا غیر جهت دار، فکر کنم فقط برنامه یه مسیر اویلری می خواد، شما می شه روی این جهت دارهااااا تمرکز کنین؟؟:لبخند::لبخند::لبخند::� �بخند::لبخند:
اون نوع فلوری رو می شه بزارید؟ :لبخند:
شما برنامههاشو قراره دوباره بزارید؟

[redflight]

کد فلوری رو دوباره نوشتم و گذاشتم.
یکم طولانی شد ولی تلاش کردم تا جای ممکن قابل فهم باشه! امیدوارم مشکلی نباشه!
در ضمن اگر تستی دادی به کد و غلط دراومد بهم بگو درست کنم! خیلی تست نکردم کد رو. روش درسته ولی شاید یه جایی تو کد باگ زده باشم.
کد فلوری (http://pastebin.ubuntu.com/8389502/)

کد اون 2 تای دیگرو هم به زودی میزارم.

این جهت دار رو کار می کنه؟

[redflight]

تا چند دقیقه دیگه همین پستم رو ویرایش میکنم و کد الگوریتم یوساکو رو میذارم. اون هم رو جهت دار هم بی جهت کار می کنه.

پیچیدگی زمانی اش از اون DFS ای بهتره؟

یه سوال دیگه، پس چرا ما می گفتیم مسیر اویلری O(E+V) هست؟

[omid_kma]

بله مطمئن هستم :لبخندساده:
عرض کردم راس ها رو مارک نمی کنیم. یال رو که مارک می کنیم.
برای منم خیلی درکش سخته که چرا کار می کنه و تا حالا حتی تلاش هم نکردم اثباتش کنم! اگر اثبات کردید برای ما هم بذارید استفاده کنیم!
در ضمن HierHolzer اون الگوریتم دومی هست که گفتم. که میریم تریل پیدا می کنیم بعد مرج میکنیم.
آخه اصولا توی dfs راس رو مارک می کنن نه یال رو چون پیاده سازیش راحت تر میشه حالا به هرحال فرقی هم نداره این طوری هم جواب میده..

میشه لینک این الگوریتم که داخل یوساکو دیدین رو بدید ؟

[a.r.khoshghalb]

آخه اصولا توی dfs راس رو مارک می کنن نه یال رو چون پیاده سازیش راحت تر میشه حالا به هرحال فرقی هم نداره این طوری هم جواب میده..

میشه لینک این الگوریتم که داخل یوساکو دیدین رو بدید ؟

من به اون سکشن ای که توش مسیر اویلری هست نرسیدم. متنش رو یکی از دوستان که رسیده بود برام فرستاده بود که الانم ندارمش.
ولی سوالی که این الگوریتم رو براش توضیح داده بود همون سوالیه که توی پست دومم گذاشتم.

[computer-student]

بزودی همین پستم رو ویرایش میکنم و کد الگوریتم یوساکو رو میذارم. اون هم رو جهت دار هم بی جهت کار می کنه.

مرسی می شه دومی هم مثل فلوری دوباره بنویسی این که دوباره نوشتی خیلی بهتره ولی می شه با ماتریس مجاورت بنویسی؟

[a.r.khoshghalb]

computer-student نگفته گراف جهت دار یا غیر جهت دار، فکر کنم فقط برنامه یه مسیر اویلری می خواد، شما می شه روی این جهت دارهااااا تمرکز کنین؟؟http://barnamenevis.org/images/smilies/yahoo/109.gifhttp://barnamenevis.org/images/smilies/yahoo/109.gifhttp://barnamenevis.org/images/smilies/yahoo/109.gifhttp://barnamenevis.org/images/smilies/yahoo/109.gifhttp://barnamenevis.org/images/smilies/yahoo/109.gif
اون نوع فلوری رو می شه بزارید؟ http://barnamenevis.org/images/smilies/yahoo/109.gif
شما برنامههاشو قراره دوباره بزارید؟


مرسی می شه دومی هم مثل فلوری دوباره بنویسی این که دوباره نوشتی خیلی بهتره ولی می شه با ماتریس مجاورت بنویسی؟

این کدش:
کد DFS ای یوساکو (http://pastebin.ubuntu.com/8393645/)
این الگوریتم هم برای جهت دار هم بی جهت کار می کنه. اگر خواستی جهت دارش کنی یه کم باید کد رو توی قسمت ورودی و مارک کردن تغییر بدی.

نه این کار رو خودت انجام بده. اگر ورودی شما ماتریس مجاورت هست، توی تابع اینپوت ورودی رو به صورت ماتریس بگیر و به لیست تبدیل کن. کار سختی نیست!

[redflight]

این کدش:
کد DFS ای یوساکو (http://pastebin.ubuntu.com/8393645/)
این الگوریتم هم برای جهت دار هم بی جهت کار می کنه. اگر خواستی جهت دارش کنی یه کم باید کد رو توی قسمت ورودی و مارک کردن تغییر بدی.

نه این کار رو خودت انجام بده. اگر ورودی شما ماتریس مجاورت هست، توی تابع اینپوت ورودی رو به صورت ماتریس بگیر و به لیست تبدیل کن. کار سختی نیست!
خیـــــــــــــــــــــــ ــلی عالی بود
فقط چرا O(EV) ؟

[redflight]

چرا O(EV) ؟

[هووویچ]

الگوریتم دیگه اسمش رو نمیدونم! این الگوریتم برای گرافی که راس با درجه فرد داشته باشه کار نمی کنه (در حالت کلی کار نمیکنه اگر یکمی فک کنی میبینی میتونی یه طوری تف بزنی که کار کنه(راهنمایی اینکه دو تا راسی که درجه فرد دارن رو به هم وصل کنی تا اونا هم درجه زوج داشته باشن!) ).
به این صورت هست که از یکی از راس های گرافت شروع می کنی و یکی از یال هاش رو میری به راس بعدی که رسیدی باز یکی از یال هاش رو میری (در طول مسیر، هر یالی رو که دیدیم حذف میکنیم از گراف) و انقدر اینکار رو می کنی تا به راسی که ازش شروع کردی برسی! الان یک دور پیدا کردی. حالا میری از یک راس دیگه که هنوز یال داره شروع میکنی و همین کار رو می کنی. اگر هیچ راسی نبود که یال داشته باشه تمومه.
حالا یه سری دور داری. تنها کاری که باید بکنی اینه که اینارو سر هم کنی تا بشه یک دور اویلری.
اینکار رو میتونی هم با لینکد لیست هم با وکتور انجام بدی.
من خیلی کلی میگم، اینکه چه جوری کدشو بنویسی با خودت. فرض کن الان دورهامون شدن اینا :
1 2 3 4 3 2 1
2 6 5 2
4 5 4
3 3
دور اویلری جواب میشه 1 2 6 5 2 3 3 4 5 4 3 2 1
برای اینکه قشنگ متوجه بشه چه جوری در آوردیم دور رو یه بار دیگه رنگی نشون میدم.
این ها دور هامون هستند:
1 2 3 4 3 2 1
2 6 5 2
4 5 4
3 3
میخوایم جواب رو بدست بیاریم. شروع می کنیم رو دور اول حرکت می کنیم به هر عددی رسیدیم میبینیم دور اون عدد رو تو جواب گذاشتیم یا نه. اگه نذاشته بودیم اون رو اضافه می کنیم به جواب.
در واقع جواب میشه :
1 2 6 5 2 3 3 4 5 4 3 2 1




سلام
این الگوریتمی که نوشتین خیلی جالب بود من تبدیلش کردم به کد ولی قسمت آخر که باید دور ها را یکی کنه مشکل داری اگه امکانش هست شبه کد قسمت آخر را بنویسید.