Existența unui ciclu Euler și calea Euler
Euler ciclu / cale există doar într-un grafic conectat sau grafice care după îndepărtarea vârfurilor unice devin conectate.
Într-un graf neorientat
Mai mult decât atât, în conformitate cu teorema Euler dovedit. ciclu Euler, dacă și numai dacă. Când graficul este conectat și nu există noduri de grad impar.
calea de Euler în grafic, dacă și numai dacă graful este conectat și nu conține mai mult de două noduri de grad impar. [1] [2] Având în vedere handshake lemă. cu un număr impar de vârfuri de grad trebuie să fie chiar. Deci, calea de Euler există numai atunci când numărul este zero sau doi. Și când este zero, traseul Euler degenerează în ciclul Eulerian.
Într-un grafic direcționat
Grafic regia conține un ciclu Euler, dacă și numai dacă acesta este puternic conectat și fiecare nod indegree său este jumătate-un rezultat care sa se află în partea de sus a aceluiași număr de nervuri, o mare parte din ea și în afară.
Cale de căutare Euler în grafic
Puteți reduce întotdeauna problema de a găsi o cale Euler la problema găsirii unui ciclu Euler. Într-adevăr, să presupunem că ciclul Euler nu exista, iar calea Euler există. Apoi, în graficul va fi exact 2 noduri de grad impar. Conectați partea de sus a nervurii, și să obțină un grafic în care există toate nodurile chiar și ciclul de studii, Euler. Găsim în acest grafic ciclu Eulerian (algoritm. Descris mai jos), și apoi eliminați din nervura inexistentă de răspuns.
Căutare ciclu Euler într-un grafic
Vom lua în considerare cel mai frecvent caz - cazul unui multigraf direcționat. eventual cu bucle. De asemenea, vom presupune că ciclul Euler în grafic există (și este de cel puțin un nod). Pentru a găsi un ciclu Euler, utilizați faptul că ciclul Euler - o asociație a tuturor ciclurilor simple ale graficului. Prin urmare, sarcina noastră - pentru a găsi toate buclele în mod eficient și să le combine în mod eficient într-o singură.
Este posibil să se realizeze, de exemplu, așa recursiv:
Este suficient să numim această procedură de la orice noduri neodinochnoy, și va găsi toate ciclurile din grafic le va elimina din grafic și să le combine într-un singur ciclu Euler.
Pentru a căuta ciclul în pasul 1, utilizați căutarea adancime.
Complexitatea acestui algoritm - O (M), adică nervurile liniare pe numărul M în grafic.
notițe
Vezi ce „ciclu Euler“ în alte dicționare:
Ciclul Euler - Count poduri Koenigsberg. Acest grafic nu este Eulerian, astfel încât nu există nici o soluție. Fiecare nod al acestui grafic a chotnuyu grade, astfel încât acest grafic Euler. margini de bypass în ordine alfabetică dă ciclu Euler. calea lui Euler (Euler ... ... Wikipedia
cale Euler - Count poduri Koenigsberg. Acest grafic nu este Eulerian, astfel încât nu există nici o soluție. Fiecare nod al acestui grafic a chotnuyu grade, astfel încât acest grafic Euler. margini de bypass în ordine alfabetică dă ciclu Euler. calea lui Euler (Euler ... ... Wikipedia
Ciclul (teoria grafurilor) - conține definiții ale teoriei graficului. Italicele indică trimiterile la termenii din dicționar (pe această pagină). # A B C D E F G H I J K L M N O P Q R S T U V ... Wikipedia
Ciclul în digraph - conține definiții ale teoriei graficului. Italicele indică trimiterile la termenii din dicționar (pe această pagină). # A B C D E F G H I J K L M N O P Q R S T U V ... Wikipedia
Ciclul Hamiltonian - Count dodecaedru cu ciclu selectat Graficul Hamilton Hamiltonian teoretic grafic este un grafic care conține un lanț hamiltonian sau ciclu hamiltonian. cale hamiltonianul (sau un circuit hamiltonian) cale (lanț) cuprinzând fiecare nod al grafului exact o dată. ... ... Wikipedia
Ciclul simplu - graf neorientat cu șase vârfuri și șapte muchii în teoria grafurilor matematică și informatică grafic este un set de obiecte cu legături între ele. Obiectele sunt reprezentate ca noduri, sau noduri ale grafului, precum și un arc de conexiune, sau coaste. Pentru ... ... Wikipedia
grafice ale lui Euler - Count poduri Koenigsberg. Acest grafic nu este Eulerian, astfel încât nu există nici o soluție. Fiecare nod al acestui grafic a chotnuyu grade, astfel încât acest grafic Euler. margini de bypass în ordine alfabetică dă ciclu Euler. calea lui Euler (Euler ... ... Wikipedia
Glosar de teoria grafurilor - conține definiții ale teoriei graficului. Italicele indică trimiterile la termenii din dicționar (pe această pagină). # A B C D E F G H I J K L M N O P Q R S ... Wikipedia