Cunoaște Intuit, prelegerea, grafice Euler

Probleme cu grafice ale lui Euler sunt adesea găsite în cărți despre divertisment matematică - de exemplu, dacă este posibil să se tragă orice grafic, fără a ridica creionul de pe hârtie și fără a trece prin orice linie de două ori. „Euler“ Numele a apărut din cauza faptului că Euler a fost primul pentru a rezolva problema faimoasa a podurilor de Koenigsberg, în care a fost necesar pentru a afla dacă graficul are. se arată în figură, lanțul Euler (nu!).

Luate orice linie închisă. în cazul în care poate fi trasă fără a ridica creionul de pe hârtie în timp ce trece fiecare secțiune exact o dată, apel unicursal. Figura grafic având traiectorie Eulerian sau ciclu Eulerian este linia unicursal.

Teorema 4.1. Dacă graficul are un ciclu Eulerian, acesta este conectat, și toate nodurile sale - chiar.

Dovada graficului din definiția ciclului Euler. Ciclul Euler conține fiecare margine și doar o singură dată, astfel încât numărul de ori traseul Euler va conduce la capătul de sus al creionului, atât de multe display-uri, și are o margine diferită. Prin urmare, gradul de fiecare nod al diagramei ar trebui să constea din două componente egale: unul de intrare numărul de la vârful, și alta - ieșiri.

Reciproca este adevărată.

Teorema 4.2. Dacă graficul este conectat și toate nodurile sale este chiar, atunci acesta are un ciclu Euler.

Dovada Dacă începe calea de la un vârf arbitrar al graficului, există un ciclu care conține toate marginile graficului.