Parcurgere grafuri - Matematica Discreta

Extras din document

Definiţie: Se numeşte lanţ în graful neorientat G=(X,U), o succesiune de vârfuri L=(z1,z2,.......,zk), unde z1, z2,.......,zk X, cu proprietatea că oricare două vârfuri consecutive sunt adiacente, adică există muchiile [z1,z2], [z2,z3],........,[zk-1,zk] U. Vârfurile z1 şi zk se numesc extremităţile lanţului, iar numărul de muchii care intră în componenţa sa reprezintă lungimea lanţului. Exemplu: În graful din figura alăturată putem distinge lanţurile: L1=(1,2,3,5,4,8) L2=(1,2,3,2) L3=(9,3,5,4,3,2) L4=(6,7,3,5,4,8) Un lanţ poate fi interpretat ca un traseu care pleacă din vârful z1 şi ajunge în vârful zk, trecând prin mai multe vârfuri şi parcurgând mai multe muchii. De exemplu, lanţul L1=(1,2,3,5,4,8) pleacă din vârful z1=1, şi parcurgând muchiile [1,2], [2,3], [3,5], [5,4], [4,8] (în acestă ordine) ajunge în vârful zk=8. Acest lanţ are lungimea 5, întrucât include cinci muchii.