دور اویلری
از ویکیپدیا، دانشنامهٔ آزاد
در نظریه گراف دور اویلری (به انگلیسی: Eulerian circuit) به مسیری گفته میشود که از یک رأس شروع شود و از تمامی یالها یکبار (و فقط یکبار) بگذرد و به همان رأس بازگردد. اگر مسیر از تمام یال ها عبور کند ولی به جای اولش باز نگردد به آن مسیر اویلری(به انگلیسی: Eulerian path) میگویند.
دور اویلری زمانی وجود دارد که گراف همبند باشد و درجه هر رأس زوج باشد، یعنی تعداد یالهای متصل به آن عددی زوج باشد. به یک گراف، گراف اویلری گفته میشود اگر و فقط اگر گراف همبند باشد و درجه تمام رأسهای آن زوج باشد.
محتویات |
[ویرایش] الگوریتم
الگوریتم پیدا کردن مدار اویلری:
#include<stdio.h>
#include<math.h>
#define max 100
double f(double y);
int k, i;
double y[max];
double x[max];
void copyarray(double[], double[]);
main()
{
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);
}
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);
}
