Euler ketten en cycles




Lit G in pseudograaf wêze. In ketting (fyts) yn G wurdt neamd Euler (Eulerian) as hy (ien) ien kear troch elke rân fan 'e pseudograaf G.

Om foar in ferbûne pseudograaf G in Eulerianske fyts te hawwen, is it nedich en genôch dat de ôfdielingen fan har hoeken sels wêze.

Om foar in ferbûne pseudograaf G in Euler-ketting te hawwen, is it nedich en genôch dat hy krekt twa heulendeksen hat. As dizze kondysje befrediget, dan is elke Euler-pseudograafkette G de ferbiningen fan 'e ûngeduld te ferbinen.

Lit G in in ferbûne multyraph wêze, waans oftekeningen sels sifers binne.

TASK 4. Konstruearje in Eulerzyklus yn in grafyk.

A l oer ûngefear en t m oanbou fan 'e Euler-syklus

Data: Inkassassatrix B (G) fan multigraaf G.

It resultaat: in folchoarder fan kanten dy't in Euler-syklus foarmje.

1. Kies in willekeurige ftex v .

2. Selektearje in willekeurige kante x foarfal en fy it it nûmer oan. (Litte wy dizze râne "feroare" neame).

3. Krekt elke ferdielde kante en in nûmer oan te jaan, ien grutter dan it oantal fan de foarige delgeare râne.

4. As yn 't wikselje wikselje , selektearje de rânen dy't jo mei v ferbine, as der gjin mooglikheid is foar in oare kar.

5. By it wikselje w wizigje, keuzes gjin kanten, dy't in "islam" is (as fuorthelle is, wurdt de graf dy't ûntstiet troch ûnkrêftige rânen yn twa ferbûne komponinten mei at least one edge).

6. Nei alle rânen binne nûmere yn 'e graf, de fyts m = [ x i 1 , x i 2 , ..., x im ] is foarme troch de rânen nûmere fan 1 oant m , wêrby't m it tal rânen yn' e graf is, is Euler fyts.

Remark Foardat de Eulerianske fyts bouwe, kontrolearje de betingst foar it bestean fan dizze fyts.

TASK 5. bouwe de Eulerianske ketting yn 'e grafyk.

Feroarje de algoritme foar it bouwen fan 'e Euler-fyts, sadat it brûkt wurde kin om de Euler-keatling yn in grafyk te bouwen.





; Datum tafoege: 2018-01-08 ; ; Views: 349 ; Is it publisearre materiaal it urheberrecht? | | Persoanlike data beskerming | ORDER WORK


Hast net fûn wat jo sochten? Brûk it sykjen:

Bêste wurden: Learje te learen, net learje! 9658 - | 7433 - of alles lêze ...

2019 @ edudocs.fun

Sidejager generaasje oer: 0.001 sek.