Ciclul Eulerian - un ciclu care conține toate marginile graficului. Euler grafic - grafic cu ciclu Eulerian.
Conceptul ciclului Euler este legat de problema bine-cunoscut de poduri Euler Koenigsberg pe râul Pregal. Conducerea aceste poduri de legătură pe malul râului 2,3 până la 1,4 sale două insule și insulele împreună, prezentat în Fig. 3.8a. Euler a formulat această problemă după cum urmează: Este posibil, pornind de la un anumit punct, pentru a merge prin toate podurile doar o singură dată și pentru a reveni la punctul de plecare. Pentru a rezolva problema Euler convertit desen într-un grafic care indică malurile fluviului și insulele ca vârful graficului, și poduri ca marginile graficului (Fig. 3.8.b).
Fig. 3.8 Schema și numărul pentru problema de poduri Koenigsberg.
Este ușor de observat că în această formulare problema punților Koenigsberg problemă echivalentă determinării graficului ciclului (traseul ciclic care nu conține margini repetitive) care trece prin toate marginile graficului. Solutia sa este dată de următoarea teoremă.
Teorema lui Euler. finit graf neorientat Eulerian dacă și numai dacă este conectat, iar gradele de toate nodurile sale sunt chiar.
Necesitatea acestor condiții este destul de evident. În graficul deconectat de la fiecare ciclu aparține oricăreia din partea sa conectat, adică Ea nu trece prin toate părțile sale. Pe de altă parte, de fiecare dată când ciclu Euler vine la orice summit-ul, el trebuie să iasă din ea pe cealaltă margine, și anume, marginile incidente vertexul poate fi împărțită într-o pereche de ciclu Eulerian adiacente. Acest lucru se aplică și la vârful inițial, care este, de asemenea, la sfârșitul anului. Pentru ea, incidentul marginile și se rup în perechi, dar, în plus, există o margine, referindu-se la începutul ciclului și marginea referitoare la sfârșitul ciclului.
Închide în sens problema găsirii unui grafic Euler este așa-numita problemă a plotterului. Se poate afirma, după cum urmează: având în vedere un grafic plan este necesar pentru a parcelei fără a ridica creionul de pe hârtie și circling de două ori aceeași margine.
Sarcina plotterul nu este echivalentă cu cea a podurilor Koenigsberg și are o soluție nu numai în clasa de cicluri Euler, așa că nu impune ca șeful plotterul se întoarce la punctul de plecare. Soluția poate consta în clasa circuitelor Euler.
lanț Euler - lanțul cuprinzând toate marginile n-grafic. dar având un alt început și de sfârșit noduri.
Teorema. Pentru a termina de n-coloană a existat lanț Euler, este necesar și suficient de coeziune și paritate grade de toate nodurile cu excepția începutului și sfârșitului, care trebuie să aibă grad impar.
Luați în considerare câteva exemple.
Exemplu. Circuitul și numărul pentru problema podurilor Koenigsberg sunt prezentate în Fig. 3.8.
În graficul toate nodurile au grad impar. Prin urmare, graficul nu are un ciclu Euler și soluția problemei este imposibilă.
Exemplu. Do pentahedron piramidă pentagonală și prezentat în figura 3.9, bucla Euler (circuit)?
Gradul local al fiecărui vârf al pentagonului este de două, adică, chiar. Prin urmare, un pentagon - Euler grafic.
Pentagon piramida este un grade ciudat de toate nodurile și nu este un grafic Euler.
Exemplu. Găsiți ciclu Euler pentru graficul prezentat în Fig. 3.10.
Fig. 3.10. Găsirea unui tur Euler
Graficul este conectat și are 6 noduri, toate chiar. Prin urmare, acest grafic - Euler și pot fi trase într-o singură lovitură a pen-ului. De unde să înceapă complot?
Există următoarea metodă pentru determinarea ordinii de desen: în coloana, selectați o regiune și umbra sa; zonele limitrofe hașurată, sari, și având o nuanță comună vertex, și deci să acționeze până când toate zonele posibile nu vor fi umbrite (Fig. 3.10b).
În plus, graficul ar trebui să fie umbrită pentru a deconecta una sau mai multe dintre vârfuri astfel încât să formeze un simplu conectat (fără „găuri“) zonă umbrită (ris.3.10s). Astfel, teoria grafurilor dată nu numai condițiile de solvabilitatii a problemei, dar, de asemenea, o metodă constructivă de rezolvare.