Знайте, Intuit, лекция, Ойлер графики

Проблеми с Ойлер графики често се срещат в книги за развлечение математиката - например, дали е възможно да се направи някоя графика, без да вдигате молива от хартията и без да минава през всяка една линия, два пъти. Името "Ойлер" е възникнала в резултат на факта, че Ойлер е първият, който да реши проблема с известния мостовете на Кьонигсберг, в които е необходимо да се установи дали има графиката. показано на фигурата, веригата Ойлер (това не е така!).

Взети всяка затворена линия. ако това може да се направи, без да вдигате молива от хартията, докато се подава всеки раздел само веднъж, обадете unicursal. Фигура графика като Ойлеров път или Ойлеров цикъл е unicursal линия.

Теорема 4.1. Ако графиката има Ойлеров цикъл, той е свързан, и всички негови върхове - дори.

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

Обратното е вярно.

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

Доказателство Ако започнете пътя от произволен връх на графиката, има един цикъл, съдържащи всички краища на графиката.