Ойлер графики - това
Наличие на цикъл Ойлер и Ойлер път
Разбира се, Ойлер цикъл / път съществува само в свързано графика или графики, че след отстраняването на единични пикове стане свързан.
В ненасочена графика
Освен това, съгласно теоремата оказа Ойлер. Euler цикъл единствено и само ако графиката не съществуват върховете на странно степен. Euler път единствено и само ако броят на върховете на странно степен е не по-голям от две.
Теорема: Ойлер път в графиката, ако и само ако графиката е свързан и съдържа не повече от два върха на нечетен степен. [1] [2]
В насочено графика
Свързана насочено графика съдържа цикъл Ойлер ако и само ако за всеки връх му indegree е неговата Half-резултат, който е в горната част на същия брой ребра, голяма част от нея в и навън.
Търсене на Ойлер път в графиката
Винаги може да се намали проблема с намирането на път Ойлер на проблема с намирането на цикъл Ойлер. Всъщност, предполагам, че цикълът на Ойлер не съществува, и съществува пътя на Ойлер. След това в графиката ще бъде точно два върха на странно степен. Свържете горната част на реброто и получаване на графика, в която всички върхове на дори степен, както и цикъл на Ойлер, че съществува. Намираме в тази графика Ойлеров цикъл (алгоритъм. Описани по-долу), и след това се отстранява от nesuschestvueschee ръб отговор.
Търсене цикъл Ойлер в графика
Ще разгледаме най-често срещаният случай - случай на насочено мултиграф. евентуално с вериги. Ние също така ще приемем, че Ойлер цикъл на графиката съществува (и е най-малко по един връх). За да намерите цикъл Ойлер, използвайте факта, че цикъл Ойлер - обединение на всички прости цикли на графиката. Затова нашата задача - да намерите всички контури ефективно и ефикасно да ги комбинирате в една.
Това е възможно да се реализира, например, така рекурсивно:
Достатъчно е да се обадя на тази процедура от всякакви neodinochnoy върхове, и това ще намерите всички цикли в графиката ще ги премахне от графиката и да ги комбинира в един цикъл на Ойлер.
За да търсите за цикъла в стъпка 1, използвайте обхождане в дълбочина.
Сложността на този алгоритъм - О (М), т.е. линейни ребра на брой М в графиката.
Пример изпълнение на C ++
Вижте какво "Euler линия" в други речници:
Графика (математика) - В този мандат, има и други приложения, вижте графиката (стойности) .. Ненасочена графика с шест върхове и седем ръбове в математическа теория графика и компютърна графика науката е набор от не-празен набор от върховете и множество двойки ... ... Wikipedia
Графика (теория на графите) - ненасочена графика с шест върха и седем ръбове в математическата теория на графите и компютърни науки графика е съвкупност от обекти с връзките между тях. Обектите са представени като възли, или възли на графиката, както и арка връзка, или ребра. За ... ... Wikipedia
Двустранен диграфът - ненасочена графика с шест върха и седем ръбове в математическата теория на графите и компютърни науки графика е съвкупност от обекти с връзките между тях. Обектите са представени като възли, или възли на графиката, както и арка връзка, или ребра. За ... ... Wikipedia
Ненасочена графика - с шест върха и седем ръбове в математическата теория на графите и компютърни науки графика е съвкупност от обекти с връзките между тях. Обектите са представени като възли, или възли на графиката, както и арка връзка, или ребра. За различни области на ... ... Wikipedia
Диграфът - ненасочена графика с шест върха и седем ръбове в математическата теория на графите и компютърни науки графика е съвкупност от обекти с връзките между тях. Обектите са представени като възли, или възли на графиката, както и арка връзка, или ребра. За ... ... Wikipedia
Прост цикъл - ненасочена графика с шест върха и седем ръбове в математическата теория на графите и компютърни науки графика е съвкупност от обекти с връзките между тях. Обектите са представени като възли, или възли на графиката, както и арка връзка, или ребра. За ... ... Wikipedia
Euler цикъл - граф Кьонигсберг мостове. Тази графика не е Ойлеров, така че не е решение. Всеки връх на тази графика е chotnuyu степен, така че тази графика на Ойлер. Заобикаляне на ръбове по азбучен ред дава цикъл Ойлер. Euler път (Euler ... ... Wikipedia
Ойлер път - граф Кьонигсберг мостове. Тази графика не е Ойлеров, така че не е решение. Всеки връх на тази графика е chotnuyu степен, така че тази графика на Ойлер. Заобикаляне на ръбове по азбучен ред дава цикъл Ойлер. Euler път (Euler ... ... Wikipedia
Euler цикъл - граф Кьонигсберг мостове. Тази графика не е Ойлеров, така че не е решение ... Wikipedia
Hamiltonian графика - Графиката на додекаедър с избрания Хамилтън линия ... Wikipedia
- Ойлер графики и свързаните с нея въпроси. G. Flyayshner. В монографията е насочен към една от най-важните части на теорията на графики - Ойлер графика теория. Книгата съдържа както класически и съвременни резултати, внимание се отделя на алгоритмични въпроси ... Прочети повече купи за 1178 рубли
- Ойлер графики и свързаните с нея въпроси. Flyayshner Г. Книгата отразява както последните теоретични постижения, както и разнообразие от въпроси за кандидатстване. Математическият изучаване на устройството, използвано в книгата на теорията ... Прочетете още Купи за 1126 рубли
- Ойлер графики и свързаните с нея въпроси. G. Flyayshner. Монографията е посветена на известния австрийски математика теорията на Ойлер графики - един от най-бързо развиващите се раздели на теорията на графите. Това е първото монографично изследване по този въпрос. В книгата ... Прочети още Купи (Украина) за 1023 UAH