Кіріспе
Граф теориясында Эйлер траекториясы (немесе Эйлер жолы) — шекті графтағы траектория, ол әр қабырғаны дәл бір рет кесіп өтеді (бұл ретте төбелерді қайта қарауға рұқсат етіледі). Сол сияқты, Эйлер циклы немесе Эйлер айналымы — бір төбеден басталып, сол төбеде аяқталатын Эйлер траекториясы. Оларды алғаш рет Леонхард Эйлер 1736 жылы Кёнигсбергтің жеті көпірі мәселесін шешкен кезде талқылаған. Мәселе математикалық тұрғыдан былай қойылуы мүмкін:
In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. The problem can be stated mathematically like this:
Given the graph in the image, is it possible to construct a path (or a cycle; i. e., a path starting and ending on the same vertex) that visits each edge exactly once? Euler proved that a necessary condition for the existence of Eulerian circuits is that all vertices in the graph have an even degree, and stated without proof that connected graphs with all vertices of even degree have an Eulerian circuit. The first complete proof of this latter claim was published posthumously in 1873 by Carl Hierholzer. This is known as Euler's Theorem:
A connected graph has an Euler cycle if and only if every vertex has even degree. The term Eulerian graph has two common meanings in graph theory. One meaning is a graph with an Eulerian circuit, and the other is a graph with every vertex of even degree. These definitions coincide for connected graphs. For the existence of Eulerian trails it is necessary that zero or two vertices have an odd degree; this means the Königsberg graph is not Eulerian. If there are no vertices of odd degree, all Eulerian trails are circuits. If there are exactly two vertices of odd degree, all Eulerian trails start at one of them and end at the other. A graph that has an Eulerian trail but not an Eulerian circuit is called semi Eulerian.
Суретте көрсетілген граф бойынша, әр қабырғаны дәл бір рет кесіп өтетін жол (немесе айналым, яғни бір төбеден басталып, сол төбеде аяқталатын жол) салуға бола ма? Эйлер эйлерлік айналымдардың болуы үшін қажетті шарты — графтың барлық төбелерінің жұп дәрежеде болуы екенін дәлелдеді және барлық төбелері жұп дәрежедегі байланысқан графтардың эйлерлік айналымы бар екенін дәлелсіз айтты. Бұл соңғы талаптың толыққанды дәлелі алғаш рет Карл Йерхольцер 1873 жылы, оның өлімінен кейін жарияланды. Бұл Эйлер теоремасы деп аталады:
In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. The problem can be stated mathematically like this:
Given the graph in the image, is it possible to construct a path (or a cycle; i. e., a path starting and ending on the same vertex) that visits each edge exactly once? Euler proved that a necessary condition for the existence of Eulerian circuits is that all vertices in the graph have an even degree, and stated without proof that connected graphs with all vertices of even degree have an Eulerian circuit. The first complete proof of this latter claim was published posthumously in 1873 by Carl Hierholzer. This is known as Euler's Theorem:
A connected graph has an Euler cycle if and only if every vertex has even degree. The term Eulerian graph has two common meanings in graph theory. One meaning is a graph with an Eulerian circuit, and the other is a graph with every vertex of even degree. These definitions coincide for connected graphs. For the existence of Eulerian trails it is necessary that zero or two vertices have an odd degree; this means the Königsberg graph is not Eulerian. If there are no vertices of odd degree, all Eulerian trails are circuits. If there are exactly two vertices of odd degree, all Eulerian trails start at one of them and end at the other. A graph that has an Eulerian trail but not an Eulerian circuit is called semi Eulerian.
Байланысқан граф Эйлер айналымына ие болу үшін, әр төбесінің дәрежесі жұп болуы керек және керісінше. Эйлерлік граф термині граф теориясында екі мағынада қолданылады. Бір мағынасы — Эйлер айналымы бар граф, ал екіншісі — барлық төбелерінің дәрежесі жұп граф. Бұл анықтамалар байланысқан графтар үшін сәйкес келеді. Эйлер траекториясының болуы үшін нөл немесе екі төбе тақ дәрежеде болуы керек; бұл Кёнигсберг графы эйлерлік емес екенін білдіреді. Егер тақ дәрежелі төбелер болмаса, барлық Эйлер траекториялары айналымдар болады. Егер дәл екі тақ дәрежелі төбе болса, барлық Эйлер траекториялары олардың бірінен басталып, екіншісінде аяқталады. Эйлер траекториясы бар, бірақ Эйлер айналымы жоқ граф жартылай Эйлерлік деп аталады.
In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. The problem can be stated mathematically like this:
Given the graph in the image, is it possible to construct a path (or a cycle; i. e., a path starting and ending on the same vertex) that visits each edge exactly once? Euler proved that a necessary condition for the existence of Eulerian circuits is that all vertices in the graph have an even degree, and stated without proof that connected graphs with all vertices of even degree have an Eulerian circuit. The first complete proof of this latter claim was published posthumously in 1873 by Carl Hierholzer. This is known as Euler's Theorem:
A connected graph has an Euler cycle if and only if every vertex has even degree. The term Eulerian graph has two common meanings in graph theory. One meaning is a graph with an Eulerian circuit, and the other is a graph with every vertex of even degree. These definitions coincide for connected graphs. For the existence of Eulerian trails it is necessary that zero or two vertices have an odd degree; this means the Königsberg graph is not Eulerian. If there are no vertices of odd degree, all Eulerian trails are circuits. If there are exactly two vertices of odd degree, all Eulerian trails start at one of them and end at the other. A graph that has an Eulerian trail but not an Eulerian circuit is called semi Eulerian.
Анықтама
Эйлерлік із немесе Эйлерлік жүріс – бағытталмаған графтың әр қабырғасын дәл бір рет пайдаланатын жүріс. Мұндай жүріс болса, граф өтімді немесе жартылай Эйлерлік деп аталады. Эйлерлік цикл. "Эйлерлік граф" термині кейде әр төбесінің дәрежесі жұп болатын графты көрсету үшін әлсіз мағынада қолданылады. Шектелген байланысты графтар үшін екі анықтама да сәйкес келеді, ал байланысты емес граф әлсіз мағынада Эйлерлік болып табылады, егер және тек қана әрбір байланысқан компонентінде Эйлерлік цикл болса. Бағытталған графтар үшін "жол" сөзі бағытталған жолмен, ал "цикл" сөзі бағытталған циклмен алмастырылуы керек. Эйлерлік іздердің, циклдардың және графтардың анықтамалары мен қасиеттері көп қабырғалы графтар үшін де жарамды. Эйлерлік бағыттау – бұл графтың әр қабырғасына бағыт беру, яғни әр төбеде кіретін қабырғалардың саны шығатын қабырғалардың санына тең болуы керек. Мұндай бағыттау кез келген граф үшін, егер әр төбесінің дәрежесі жұп болса, бар және оны графтың әрбір байланысқан компонентінде Эйлерлік айналым құрастырып, содан кейін қабырғаларды айналым бойынша бағыттап табуға болады. Байланысқан графтың кез келген Эйлерлік бағыттауы – күшті бағыттау, яғни нәтижесіндегі бағытталған графты күшті байланысты ететін бағыттау.
Қасиеттері
Бағытталмаған графтың Эйлер циклы бар, егер және тек қана егер әрбір төбесінің дәрежесі жұп болса, және оның нөлдік емес дәрежедегі барлық төбелері бір байланысты компонентке тиесілі болса. Бағытталмаған графты, егер және тек қана егер оның барлық төбелерінің дәрежесі жұп болса, қабырғалары бір-бірімен қиылыспайтын циклдарға бөлуге болады. Демек, графтың Эйлер циклы бар, егер және тек қана егер оны қабырғалары бір-бірімен қиылыспайтын циклдарға бөлуге болады және оның нөлдік емес дәрежедегі төбелері бір байланысты компонентке тиесілі болса. Бағытталмаған графтың Эйлер жолы бар, егер және тек қана егер дәл нөл немесе екі төбесінің дәрежесі тақ болса, және оның нөлдік емес дәрежедегі барлық төбелері бір байланысты компонентке тиесілі болса. Барлық қабырғалары бір компонентте және ең көп дегенде екі тақ дәрежелі төбесі бар графты қарастырайық. Алгоритм тақ дәрежелі төбеден басталады, немесе егер графта мұндай төбелер болмаса, кездейсоқ таңдалған төбеден басталады. Әр қадамда ол жолдағы келесі қабырғаны таңдайды, егер мұндай қабырға болмаса, онда ол ағымдағы төбеде қалған қабырғаны таңдайды. Содан кейін ол сол қабырғаның екінші ұшына өтеді және қабырғаны жояды. Алгоритмнің соңында қабырғалар қалмайды, ал қабырғалар таңдалған реті Эйлер циклын (егер графтың тақ дәрежелі төбелері болмаса) немесе Эйлер жолын (егер дәл екі тақ дәрежелі төбесі болса) құрайды. Флюри алгоритміндегі графты аралау қабырғалар саны бойынша сызықтық, алайда біз көпірлерді анықтаудың күрделілігін де ескеруіміз керек. Егер біз әр қабырғаны жойғаннан кейін Таржанның сызықтық уақытта көпірді табу алгоритмін қайта іске қоссақ, Флюри алгоритмінің уақыт күрделілігі болады. Динамикалық көпірді табу алгоритмі оны жақсартуға мүмкіндік береді, бірақ бұл әлі де баламалы алгоритмдерге қарағанда айтарлықтай баяу.
Күрделілік мәселелері
Диграфтардағы Эйлерлік контурлардың санын де Брюйн, ван Аарден Эренфест, Смит және Тютте есімдерімен аталған BEST теоремасы арқылы есептеуге болады. Формула бойынша, диграфтағы Эйлерлік контурлардың саны белгілі бір дәрежедегі факторлардың көбейтіндісіне және тамырланған арборесценциялардың санына тең. Соңғысы матрицалық ағаш теоремасы бойынша детерминант ретінде есептелуі мүмкін, бұл полиномиалдық уақыт алгоритмін ұсынады. BEST теоремасы алғаш рет осы түрінде Аарден Эренфест пен де Брюйннің (1951) еңбегіне қосылған "дәлелге қосымша" деген жазбада келтірілген. Алғашқы дәлел биективті болды және де Брюйн тізбектерін жалпылады. Бұл Смит пен Тюттедің (1941) бұрынғы нәтижесінің бір түрі. Бағытталмаған графтардағы Эйлерлік контурлардың санын есептеу әлдеқайда қиын. Бұл мәселе #P-толық деп белгілі. Жағымды жағынан, Котциг түрлендірулері (1968 жылы Антон Котциг енгізген) арқылы қолданылатын Марков тізбегі Монте-Карло әдісі графтардағы Эйлерлік контурлардың санын жақсы жуықтауға мүмкіндік береді деп есептеледі, бірақ әзірге бұл факт дәлелденген жоқ (тіпті шектеулі дәрежелі графтар үшін де).
Қолданбалар
Эулериялық іздер биоинформатикада ДНК тізбегін оның фрагменттерінен қайта құруға қолданылады. Олар сонымен қатар CMOS тізбектерін жобалауда ең тиімді логикалық қақпалар тізбегін табу үшін пайдаланылады. Ағаштарды өңдеуге арналған кейбір алгоритмдер ағаштың Эйлерлік айналымын (әр қабырғасы екі доға ретінде қарастырылады) пайдаланады. Де Брюйн тізбектерін Де Брюйн графтарының Эулериялық іздері ретінде құруға болады.
Шексіз графиктерде
Шексіз графикте Эйлер жолына немесе Эйлер циклына сәйкес келетін түсінік – Эйлер сызығы, ол графиктің барлық қабырғаларын қамтитын екі жақты шексіз жол. Мұндай жолдың болуы үшін графтың байланысты болуы және барлық төбелерінің дәрежесі жұп болуы жеткіліксіз; мысалы, көрсетілген шексіз Кейли графигінде барлық төбелерінің дәрежесі төртке тең, бірақ Эйлер сызығы жоқ. Эйлер сызығын қамтитын шексіз графтар былай сипатталады: шексіз граф немесе көпграф G-де Эйлер сызығы болуы үшін келесі шарттардың бәрі қанағаттандырылуы керек және жеткілікті: G байланысқан. G-де төбелер мен қабырғалардың санаулы жиыны бар. G-де (шекті) тақ дәрежелі төбелер жоқ. G-ден кез келген шекті кішіграфты алып тастағанда, қалған графта ең көп дегенде екі шексіз байланысқан компонент қалады, ал егер S-тің әр төбесінде жұп дәреже болса, онда S-ті алып тастағанда дәл бір шексіз байланысқан компонент қалады.
G is connected. G has countable sets of vertices and edges. G has no vertices of (finite) odd degree. Removing any finite subgraph S from G leaves at most two infinite connected components in the remaining graph, and if S has even degree at each of its vertices then removing S leaves exactly one infinite connected component.
Бағытталмаған Эйлер графиктері
Ойлер шекті графтың Эйлерлік болуы үшін қажетті шарты барлық төбелерінің жұп дәрежеде болуы керек екенін айтты. Иерхольцер 1873 жылы жарияланған мақаласында бұл шарт жеткілікті екенін дәлелдеді. Бұл шекті графтың Эйлерлік болуы үшін келесі қажетті және жеткілікті талапқа әкеледі: Бағытталмаған, байланысқан шекті граф Эйлерлік болады, егер және тек қана G-нің әрбір төбесі жұп дәрежеде болса. 1912 жылы Веблен келесі нәтижені дәлелдеді: Бағытталмаған, байланысқан граф Эйлерлік болады, егер және тек қана ол кейбір циклдердің біріккен жиыны болса. Иерхольцер бағытталмаған графта Эйлерлік айналу құру үшін сызықтық уақыт алгоритмін жасады.
Бағытталған Эйлер графиктері
Барлық шығу дәрежелері жұп болатын, бірақ Эйлерлік емес бағытталған граф болуы мүмкін. Эйлерлік айналымдағы түйінге кірген сайын, сол түйінден де дәл сол ретте шығылу керек болғандықтан, Эйлерлік айналымның болуы үшін қажетті шарт – әрбір түйінде кіріс дәрежесі мен шығу дәрежесінің тең болуы. Әрине, байланыстылық та қажет. Кёниг бұл шарттардың жеткілікті екенін дәлелдеді. Яғни, бағытталған граф байланысқан және әрбір түйінде кіріс дәрежесі мен шығу дәрежесі тең болса, ол Эйлерлік граф болады. Бұл теоремада "байланысқан" сөзі "әлсіз байланысқан" немесе "күшті байланысқан" мағынасында қолданылса да маңызды емес, себебі Эйлерлік графтар үшін олар эквивалентті. Иерхольцердің Эйлерлік айналымды құруға арналған сызықтық уақыт алгоритмі де бағытталған графтарға қолданылады.
Аралас Эулероволық графиктер
Барлық жұп және симметриялық аралас графиктер Эйлерлік болатыны кепілдендірілген. Дегенмен, бұл қажетті шарт емес, себебі Эйлерлік болатын, симметриялы емес жұп графикті құру мүмкін. Форд пен Фулкерсон 1962 жылы жариялаған "Торлардағы ағындар" кітабында графтың Эйлерлік болуы үшін қажетті және жеткілікті шартты дәлелдеді: әрбір төбесі жұп болуы керек және тепе-теңдік шартын орындауы керек, яғни төбелердің кез келген S жиыны үшін, S жиынынан шығатын және S жиынына кіретін доғалардың санының айырмасы S жиынымен байланысты жиектер санынан кем немесе тең болуы керек. Аралас графиктің Эйлерлік екенін тексеру, бағытталмаған немесе бағытталған графиктің Эйлерлік екенін тексеруге қарағанда қиын, себебі тепе-теңдік жиынтық шарты төбелердің барлық мүмкін кіші жиынтығына қатысты.
The process of checking if a mixed graph is Eulerian is harder than checking if an undirected or directed graph is Eulerian because the balanced set condition concerns every possible subset of vertices.