دور اویلری

در نظریه گراف دور اویلری یا مدار اویلری (به انگلیسی: 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);
}

جستارهای وابسته

پیوند به بیرون

منابع
  1. N. L. Biggs, E. K. Lloyd and R. J. Wilson, Graph Theory 1736–1936, Clarendon Press, Oxford, 1976, 8–9, شابک ‎۰−۱۹−۸۵۳۹۰۱−۰ .
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. Brendan McKay and Robert W. Robinson, Asymptotic enumeration of eulerian circuits in the complete graph, Combinatorica, 10 (1995), no. 4, 367–377.
  7. M.I. Isaev (2009). "Asymptotic number of Eulerian circuits in complete bipartite graphs". Proc. 52-nd MFTI Conference (به Russian). Moscow: 111–114.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.