0000043 2

Oowód togo twie rdzeniu nozno znolezć w [53]. ror.yzsze twierdzenie jest uiytoczno na przykład przy projektowaniu kodów dla przesyłania informacji o 2QdonoJ odporności na zakłócenia.

5.6. Łańcuchy Eulera

Łańcuchem Eulera nazywamy łańcuch zawierający wszystkie gałęzie grafu. Oznaczymy go przez «£_E(x^p,x^k). Możo on być cykliczny (x^p ■ x^k). Nie każdy graf zawiera łańcuch Eulera. Graf. w któryś istnieje łańcuch Eulera nazywamy grafem Eulera.

T> OZENIE 5.12

f

Dowolny graf zawiero łańcuch Eulera wtedy i tylko wtedy, gdy Jeet spójny (z wyjątkiem wierzchołków gołych) i gdy liczbo wierzchołków o nieparzystych roz-wldleniach w tym grafie Jeat równa 0 lub 2.

Dowód konieczności warunków je*.t natychmiastowy - wystarczy wzięć pod uwagę cięg -j *^p• • • • *^ui_a#x^k j i zeuwaiyć.te

jozoli x^p / x^k, to Jedynymi wierzchołkami o nieporzyetych roz-widloniech oę wierzchołki okrojne tego łańcucha. OeZell neto -miast x^p ■ x^k, to wszystkie wierzchołki auozę mleć parzyate rozwidlenia.

Dowód dODtateczności aoZne znoleźć między innymi w [53] i [ój. Oowód zomieezczony w [53] wykorzystuje algorytm opracowany przez Hoang Tuy (1964) ełuZęcy do wyznaczania łańcucha Eulera w dowolnym grafie Eulera.

5.6.1. Algorytm Ho&ng Tuy

1° .'tybieromy wierzchołek poczętkowy x^p (o nieparzystym rozwidleniu r(x^p) lub dowolny, gdy nie ma takich). 3ako wierzchołek końcowy'wybieramy x^k (o nleparzyotye rozwidleniu r(x^k) lub x^k ■ x^p).

2° £noJduiemy dowolny łańcuch prooty (lub cykl proety dla

*^P ■ ^x ), jC (^xP»*^k) 1 gałęzie tego łańcucha cechujemy cechę

c ■ O.

3° wśród nieocochowanych gałęzi znajdujemy dowolny cykl proaty, zawierający przynajanlej Jedną gałąź przyległą do gałęzi już ocachowanaj 1 gałęzie tago cyklu cachujaay cechą o ja* dan wląkazą od oetatnlo nadawanaj. Oeśli zoataly gałęzla nlaocachowana, to akok do 3°,

4° Tworzyoy ciąg łańcucha Eulara poczynając od wiarzoholka *^p l zaliczając do łańcucha gałęzie o największych wartośelaoh cach,

Hołng Tuy dowiódł, ża dla grafu spełniającego założania tWier-dzania 5.12, zawsze wśród nlaooachowanych gałęzi (punkt 3° al-gorytau) iatnlaja cykl proaty. Ty* aaaya zawaza iatniaja w taki* grafia łańcuch Eulara.

Przykład 5.4

Wyznaczyay łańcuch Eulara w grafia przadatawlonyn na ry-aunku 5.2. Graf tan apałnia założania twiardzania 5.12, a wiarz-chołkaal o nlaparzyatych rozwldlanlach r(x) eą wlarzchołkl 3 15,

0 a

Rya.5.2

Realizując procedurę caehowanla z algorytau Hcing Tuy, otrzy -■ujany cachy przedstawiona jako liczby przy gałąziaety na ry -aunku 5.3,

05