Rute, căi și cicluri în grafice

Route în graful G = (. V E) se numește o secvență finită de muchiile adiacente ale formei: (v0, v1), (v1, v2), (v2, v3), ¼, (vk # 8209; 1, vk), sau rută poate fi considerată ca o secvență de noduri: (v0, v1, ¼, vk), că orice pereche de noduri (vi # 8209; 1, vi), unde 1 £ i £ k este o muchie a graficului G. Această cale este numită (v0 Vk) -path și nodurile v0 și vk sunt vârfurile inițiale și finale sau terminale ale traseului. Toate celelalte topuri ale traseului sunt numite interne. Rețineți că marginile și vârfurile din traseu pot fi repetate.







Traseul se numește deschis. dacă vârfurile sale terminale sunt diferite și închise sau ciclice altfel.







O ruta deschisă este numită lanț. dacă toate margini sunt diferite (se pot repeta vârfurile).

Un lanț în care nodurile nu se repetă este denumit în mod obișnuit o cale (lanț simplu).

Un lanț închis este numit un ciclu. calea închisă - un ciclu simplu (în digraph - un contur). O margine a unui grafic este numită ciclică. Dacă există un ciclu în graficul care conține această margine.

Un non-graf fără cicluri este denumit de obicei aciclic. Graficul fără contur este fără contur.

Lungimea traseului (calea, ciclul) este denumită de obicei numărul de margini din aceasta.

Rute, căi și cicluri în grafice
Pentru graficul din figura 24: traseul deschis: (v2, v4, v1, v2, v3, v4, v1)







Articole similare

Trimiteți-le prietenilor: