Eulerjevi in Hamiltonski grafi

O matematiki, številih, množicah in računih...
Odgovori
okazaki
Prispevkov: 1
Pridružen: 30.11.2014 17:17

Eulerjevi in Hamiltonski grafi

Odgovor Napisal/-a okazaki »

Pozdrav,

imam sledeči problem. Dokazati moram naslednje tri trditve iz teorije grafov:
  • 1) Če je graf Eulerjev, je L(Γ) (=povezavni graf) Eulerjev.
    2) Če je graf Eulerjev, je L(Γ) (=povezavni graf) hamiltonski.
    3) Če je graf hamiltonski, je L(Γ) (=povezavni graf) hamiltonski.
Dokazati moram tudi, da obratno ne velja.

Zaenkrat sem ugotovil, da za ugotavljanje Eulerjevega grafa pomaga sledeči izrek:
"Naj bo G povezan graf. Tedaj je G Eulerjev graf natanko tedaj, ko so vsa vozlišča sode stopnje."
Vendar ne vem, kako točno bi utemeljil, da je vsako vozlišče pri povezavnem grafu sode stopnje.

Za ugotavljanje hamiltonskega grafa bi uporabil izrek (Dirac):
Če ima graf vsaj 3 točke in velja deg(v) ≥|V(G)|/2, za vsako vozlišče v, potem je G hamiltonski.
Mimogrede bi bilo dovolj, če bi za dokazovanje obrata izrekov poiskal protiprimer. pri Trditvi 1 sem ugotovil, da je povezavni graf hiperkocke Q3 Eulerjev, dočim sama hiperkocka ni. Torej, obrat ne velja.

Kako bi lahko izreke čimbolj preprosto dokazal?

Hvala za odgovore in pomoč! :)

Zajc
Prispevkov: 1099
Pridružen: 26.6.2008 19:15

Re: Eulerjevi in Hamiltonski grafi

Odgovor Napisal/-a Zajc »

1) Če je graf Eulerjev, je L(Γ) (=povezavni graf) Eulerjev.
To velja pod določenimi pogoji, in sicer, če graf nima zank in "vzporednih" povezav.

Recimo, da je G Eulerjev. Najprej se dokaže, da je L(G) povezan graf. Če sta e=xy in f=zw povezavi grafa G, potem zaradi povezanosti grafa G obstaja pot med y in z. Očitno od tod sledi, da obstaja pot v grafu L(G) med povezavama e in f.

Dokažemo še, da so vse točke v grafu L(G) sode stopnje: če je e=xy povezava grafa G, potem obstaja še liho povezav iz točke x in liho povezav iz točke y. Nobena od teh povezav ni skupna (graf G nima vzporednih povezav), torej je liho+liho=sodo povezav, ki so sosedne povezavi e. Torej je e sode stopnje v grafu L(G).

Odgovori