دور اویلری
در نظریه گراف دور اویلری یا مدار اویلری (به انگلیسی: Eulerian circuit) به مسیری گفته میشود که از یک رأس شروع شود و از تمامی یالها یکبار (و فقط یکبار) بگذرد و به همان رأس بازگردد. اگر مسیر از تمام یالها عبور کند ولی به جای اولش بازنگردد به آن مسیر اویلری (به انگلیسی: Eulerian path) میگویند.
دور اویلری زمانی وجود دارد که گراف همبند باشد و درجه هر رأس زوج باشد، یعنی تعداد یالهای متصل به آن عددی زوج باشد. به یک گراف، گراف اویلری گفته میشود اگر و فقط اگر گراف همبند باشد و درجه تمام رأسهای آن زوج باشد. (با فرض اینکه مؤلفه بدیهی نداشته باشیم)[1]
کاربردها
مسیرهای اویلری در بیوانفورماتیک برای بازسازی توالی دیانای (توالی اسید نوکلئیک) از قطعات آن مورد استفاده قرار میگیرد.[2] مسیرهای اویلری همچنین در طراحی مدار CMOS برای پیدا کردن ترتیب دروازه منطقی بهینه مورد استفاده قرار می گیرند.[3] مضاف بر این الگوریتمهای متعددی برای پردازش درختها وجود دارد که از دورهای اویلری استفاده میکنند.[4][5]
تعداد دورهای اویلری
مککِی و رابینسون اثبات کردند که تعدادِ دورهای اویلری در گرافهای کامل به فرمول پایین میل میکند:[6]
بعدها ایزائف اثبات کرد تعداد دورهای اویلری در گرافهای کامل دو بخشی به صورت مجانبی برابر است با:[7]
الگوریتم
الگوریتم پیدا کردن مدار اویلری:
# include <stdio.h> # include <math.h> # define max 100 double f(double y); void copyarray(double[], double[]); int k, i; double y[max]; double x[max]; int main(void) { FILE *file; double h, x, y; printf("this program does a first order ODE for dy/dx=-y+1 with initial condition of y(0)=0 from x=0 to x=0.9\n"); printf("input the step size (h>0):\n"); scanf("%lf",&h); k = (int)((0.9-0)/h); x[0] = 0; y[0] = 0; file = fopen("euler.data", "w"); for(i=0; i<k; i++) { x[i+1] = x[i] + h; y[i+1] = y[i] + h * f(y[i]); fprintf(file,"4.2%lf\t4.2%lf\n", x[i], y[i]); } fclose(file); return 0; } double f(double y) { int i; double sum, ysum; copyarray(x,y); for(i=0; i<k; i++) ysum=-y[i]; sum = ysum+1; return (sum); }
جستارهای وابسته
پیوند به بیرون
منابع
- N. L. Biggs, E. K. Lloyd and R. J. Wilson, Graph Theory 1736–1936, Clarendon Press, Oxford, 1976, 8–9, شابک ۰−۱۹−۸۵۳۹۰۱−۰ .
- Pevzner, Pavel A.; Tang, Haixu; Waterman, Michael S. (2001). "An Eulerian trail approach to DNA fragment assembly". Proceedings of the National Academy of Sciences of the United States of America. 98 (17): 9748–9753. Bibcode:2001PNAS...98.9748P. doi:10.1073/pnas.171285098. PMC 55524. PMID 11504945.
- Roy, Kuntal (2007). "Optimum Gate Ordering of CMOS Logic Gates Using Euler Path Approach: Some Insights and Explanations". Journal of Computing and Information Technology. 15 (1): 85–92. doi:10.2498/cit.1000731.
- Tarjan, Robert E.; Vishkin, Uzi (1985). "An efficient parallel biconnectivity algorithm". SIAM Journal on Computing. 14 (4): 862–874. CiteSeerX 10.1.1.465.8898. doi:10.1137/0214061.
- Berkman, Omer; Vishkin, Uzi (Apr 1994). "Finding level-ancestors in trees". J. Comput. Syst. Sci. 2. 48: 214–230. doi:10.1016/S0022-0000(05)80002-9.
- Brendan McKay and Robert W. Robinson, Asymptotic enumeration of eulerian circuits in the complete graph, Combinatorica, 10 (1995), no. 4, 367–377.
- M.I. Isaev (2009). "Asymptotic number of Eulerian circuits in complete bipartite graphs". Proc. 52-nd MFTI Conference (به Russian). Moscow: 111–114.