تور اویلری در گراف جهت دار و بی جهت¶
شرط لازم و کافی¶
گراف بدون جهت¶
در ابتدا فرض کنید گراف مورد بحث یک گراف بدون جهت است. حالا شرط لازم و کافی وجود داشتن تور اویلری را بررسی می کنیم. ابتدا راس های ایزوله گراف را حذف کنید. حالا لازم و کافی است که :
- الف) گراف همبند باشد.
- ب) درجه هر راس زوج باشد.
ابتدا ثابت می کنیم دو شرط بالا لازم هستند.
شرط الف به وضوح لازم است چون اگر دو یال در دو مولفه همبندی متفاوت باشد یک گذر نمی تواند همزمان شامل هر دوی آنها باشد.
برای اثبات لازم بودن شرط ب توجه کنید که هر گاه به یک یال وارد می شویم باید بلافاصله از آن خارج شویم.(در مورد راس شروع دقت کنید) بنابرین تعداد یال های مجاور هر راس باید مضربی از ۲ باشند.
حالا ثابت می کنیم دو شرط بالا کافی هستند. برای این کار از استقرا روی تعداد یال ها استفاده می کنیم.
ابتدا فرض کنید یک گذر بسته داریم که از راس \(start\) شروع شده و به همان راس باز می گردد. \(a_1 = start, a_2, ..., a_k = start\) که لزوما شامل همه یال ها نیست.
حالا یال های این گذر را از گراف حذف کنید. گراف به چند مولفه همبندی افراز می شود. به هر مولفه اولین \(i\) را نسبت دهید که \(a_i\) درون آن مولفه باشد.
حالا شروع به طی کردن گشتی که حذف کردیم بکنید. هر گاه به راس \(a_i\) رسیدیم به صورت استقرایی تور اویلری مولفه هایی که \(i\) به آن ها نسبت داده شده است را بسازید و آنها را طی کنید.
در نهایت گشتی که طی کرده ایم تور اویلری گراف ما است!
تنها یک قسمت از اثبات باقی می ماند. چرا توانستیم فرض کنیم یک گشت بسته شامل \(start\) وجود دارد؟
کافیست از \(start\) شروع کنیم و در هر مرحله اگر در راس \(u\) باشیم که \(u \neq start\) یک یال مجاور \(u\) را طی کنیم که قبلا طی نشده است و این کار را تا زمانی ادامه دهیم که دوباره به \(start\) برسیم.
چرا چنین یالی وجود دارد؟ زیرا وقتی به راس \(u\) رسیده ایم فرد بار به این راس وارد شده ایم و زوج بار خارج شده ایم. پس تعداد یال هایی که قبلا طی شده است فرد است و از طرفی طبق فرض درجه هر راس زوج است. پس باید یک یال که قبلا طی نشده است وجود داشته باشد!
گراف جهت دار¶
بررسی تور اویلری در گراف جهت دار بسیار مشابه گراف بدون جهت است. مشابه بالا ابتدا راس های ایزوله را حذف کنید سپس لازم و کافی است که :
- الف) گراف زمینه (جهت دهی ها را در نظر نگیرید) همبند باشد.
- ب) \({d^+}_u = {d^-}_u\)
در اینجا \({d^+}_u\) درجه خروجی راس \(u\) و \({d^-}_u\) درجه ورودی راس \(u\) می باشد.
اثبات لازم و کافی بودن مشابه اثبات برای گراف های بی جهت انجام می شود.
گراف نیم اویلری¶
هر گرافی که دو راس فرد داشته باشد و بقیه رئوس زوج باشد را نیم اویلری میگویند . زیرا گذر اویلری دارد که راس شروع و پایانش دو راس فرد هستند .
در مورد گراف جهتدار هم به ازای هر راس \(u\) ، :math:`{d^+}_u = {d^-}_u`به جز دو راس که آن دو راس هم خروجی و ورودیشان تفاضلشان یک است و در یکی خروجی بزرگتر و در دیگری ورودی بزرگتر از خروجی است .
پیاده سازی¶
ابتدا گراف را با لینکد لیست ذخیره سازی می کنیم. در تابع add_edge (که در اینجا برای گراف جهت دار نوشته شده است) دو راس داده می شود به عنوان ورودی داده می شود و تابع یالی بین آن دو می کشد. (جهت دار یا بی جهت)
توجه کنید که تفاوت کد پیدا کردن تور اویلری گراف جهت دار و بدون جهت تنها در تابع add_edge است.
const int max_edges = 1010, max_vertices = 1010;
int edge_counter = 1;
int to[max_edges], next[max_edges], top[max_edges];
bool used[max_edges];
void add_edge(int a, int b){
to[edge_counter] = b;
next[edge_counter] = top[a];
top[a] = edge_counter;
edge_counter++;
}
vector<int> ans;
void build(int start){
while(top[start] != 0 && used[top[start]])
top[start] = next[top[start]];
if(top[start] == 0)
return;
vector <int> tmp;
int u = start;
do{
while(top[u] != 0 && used[top[u]])
top[u] = next[top[u]];
assert(top[u] == 0); // agar shart bargharar bashad graph euleri nist.
used[top[u]] = 1;
tmp.push_back(top[u]);
u = to[top[u]];
}while(start != u);
u = start;
for(int id : tmp){
build(u);
ans.push_back(id);
u = to[id];
}
}
int main(){
// graph ra voroodi begirid va baraye har yal add_edge ra seda bezanid
// taabe build ra seda bezanid
// hala tartib yal ha dar vector ans gharar darad
}
اگر راس شروع و پایان یکسان نباشند چه؟¶
فرض کنید می خواهید یک گذر پیدا کنید که از راس \(a\) شروع شده و به راس \(b\) ختم شود و تمام یال ها را ببینیم و \(a \neq b\).
حالا برای تبدیل مسئله جدید به مسئله تور اویلری کافی است یک یال بین \(a\) و \(b\) اضافه کنید. (اگر گراف جهت دار بود از \(b\) به \(a\)).
حالا اگر فرض کنید در ابتدا یال جدید را طی می کنیم(در تور اویلری مهم نیست که از کدام یال شروع می کنیم) بقیه گذر همان چیزی است که دنبالش بودیم.(چرا؟) پس توانستیم این مسئله را به مسئله تور اویلری تبدیل کنیم.
این کتاب توسط مشارکت کنندگان شاززز به وجود آمده است.
این کتاب عمومی است و تحت پروانه cc-by-sa در دسترس است.
آخرین به روز رسانی در ژوئن 09, 2022.
