Ойлер графики - studopediya

Определяне 1.Eylerovym от графика нарече път, съдържащ всички краища на графиката и преминава през всеки един път.

ПРИМЕР 1 разгледаме графиката

Определяне 2.Eylerovym цикъл в графика е цикъл, който съдържа всички краища на графиката и преминава през всеки един път.

Определяне 3.Graf като цикъл на Ойлер, наречена графиката Ойлер.

Пример 2. Разглеждане на графиката

Теорема 1. Ойлер графика е свързан, и всички върхове са дори.

Свързване от определението на графиката Ойлер. Euler цикъл съдържа всеки ръб и само един път. Следователно степента на всеки връх на графиката трябва да се състои от две еднакви компоненти: броят на входа на върха и на броя на изхода от върха.

Теорема 2. Ако графиката G (X, Т), свързани и всички негови върхове са дори, че има цикъл Ойлеров.

ТЕОРЕМА 3. Ако графиката G (X, Т) има Ойлер от края А и В след това графиката G (X, Т) и свързан А и само нейните нечетни върхове.

Ако пътят започва от А и завършва на Б. а след това и нечетни върхове, дори и ако пътят е многократно преминава през тях. На върха на всеки друг път трябва да води и да се оттегли от него, т.е. дори и на останалите върхове.

Теорема 4. Ако графиката G (X, Т) и свързан А и само нейните нечетни върхове, графиката има Ойлер от края А и Б.

Теорема 5. Ако графиката G (X, Т) е свързан, е възможно да се конструира цикличен маршрут, съдържащ всички ръбове точно два пъти, един път във всяка посока.