دور اولری

از ویکی‌پدیا، دانشنامهٔ آزاد
(تغییرمسیر از دور اویلری)
پرش به: ناوبری، جستجو

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

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

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

الگوریتم[ویرایش]

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

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

مقالات مرتبط[ویرایش]

پانویس[ویرایش]

پیوند به بیرون[ویرایش]