دور اویلری

در نظریه گراف دور اویلری یا مدار اویلری  به مسیری گفته می‌شود که از یک رأس شروع شود و از تمامی یال‌ها یکبار (و فقط یکبار) بگذرد و به همان رأس بازگردد. اگر مسیر از تمام یال‌ها عبور کند ولی به جای اولش بازنگردد به آن مسیر اویلری  می‌گویند.

دور اویلری زمانی وجود دارد که گراف همبند باشد و درجه هر رأس زوج باشد، یعنی تعداد یال‌های متصل به آن عددی زوج باشد. به یک گراف، گراف اویلری گفته می‌شود اگر و فقط اگر گراف همبند باشد و درجه تمام رأس‌های آن زوج باشد. (با فرض اینکه مؤلفه بدیهی نداشته باشیم)N. L. Biggs, E. K. Lloyd and R. J. Wilson, Graph Theory 1736–1936, Clarendon Press, Oxford, 1976, 8–9, .

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

 تعداد دورهای اویلری 
مک‌کِی و رابینسون اثبات کردند که تعدادِ دورهای اویلری در گرافهای کامل به فرمول پایین میل می‌کند:Brendan McKay and Robert W. Robinson, Asymptotic enumeration of eulerian circuits in the complete graph, Combinatorica, 10 (1995), no. 4, 367–377.



بعدها ایزائف اثبات کرد تعداد دورهای اویلری در گرافهای کامل دو بخشی به صورت مجانبی برابر است با:



بندانگشتی|165px|گراف مسئله پل‌های کونیگسبرگ. این گراف اویلری نیست و دور اویلری ندارد.
بندانگشتی|درجه تمام رأس‌ها در این گراف زوج است بنابراین دور اویلری دارد. دنبال کردن یال‌ها بر اساس ترتیب الفبایی دور را مشخص می‌کند

 الگوریتم 
الگوریتم پیدا کردن مدار اویلری:

# 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);
}

 جستارهای وابسته 
 مسئله پل‌های کونیگسبرگ
 یادواره‌های لئونارد اویلر

 پیوند به بیرون 
 ce.sharif.edu
 economicexpert.com
 /daneshnameh.roshd.ir 

 منابع 

رده:اشیاء نظریه گراف
رده:لئونارد اویلر
رده:نظریه گراف