drzewo i graf krawędzowy

glupiablondyna · Post autor: **glupiablondyna** » 12 wrz 2013, o 21:31

może ktoś pomoże z zadaniem ?
Niech T będzie dowolnym drzewem o trzech wierzchołkach. Udowodnić , że graf krawędziowy drzewa ma cykl eulera wtedy i tylko wtedy gdy każdy wierzchołek w T ma stopień nieparzysty .

z góry dziękuję

grejon · Post autor: **grejon** » 12 wrz 2013, o 22:16

3 wierzchołkach czy 3 liściach?

glupiablondyna · Post autor: **glupiablondyna** » 13 wrz 2013, o 07:00

już wiem , T było drzewem o conajmniej trzech krawędziach-- 13 wrz 2013, o 08:28 --tak to jest jak się pisze zadania z pamięci

grejon · Post autor: **grejon** » 13 wrz 2013, o 08:53

To co mi przychodzi do głowy - ponieważ każdy wierzchołek w grafie ma stopień nieparzysty, to każda krawędź ma wspólny każdy z wierzchołków z parzystą liczbą krawędzi (tzn. każda krawędź łączy 2 wierzchołki i zarówno jeden jak i drugi ma wspólny z parzystą liczbą krawędzi). Dlatego graf krawędziowy takiego drzewa jest spójny i każdy jego wierzchołek ma stopień parzysty, a z tego wynika istnienie cyklu Eulera.