دور اویلری

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

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

کاربردها

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

تعداد دورهای اویلری

مک‌کِی و رابینسون اثبات کردند که تعدادِ دورهای اویلری در گرافهای کامل به فرمول پایین میل می‌کند:

$\operatorname {ec} (K_{n})=2^{(n+1)/2}\pi ^{1/2}e^{-n^{2}/2+11/12}n^{(n-2)(n+1)/2}{\bigl (}1+O(n^{-1/2+\epsilon }){\bigr )}.$

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

$\operatorname {ec} (K_{n,n})=(n/2-1)!^{2n}2^{n^{2}-n+1/2}\pi ^{-n+1/2}n^{n-1}{\bigl (}1+O(n^{-1/2+\epsilon }){\bigr )}.$

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

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

الگوریتم

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

# 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 بایگانی‌شده در ۱۵ ژانویه ۲۰۱۹ توسط Wayback Machine