0000037 2

5

Rozdział

MARSZRUTY X SP&3N05Ł GRAFU

5.1. Morozruty, łańcuchy i drogi

Marszruto w grofia G lub hiporgrofle H ■ <X,U,P>

nazywany clęg przeoienny, wierzchołków *_Ł t x 1 gałęzi (hipor-

gałęzi) u. £ U ^Ł6

epełniojęcy worunek

A    V IX ■ ^ ₍ i »X₄    •...»a ^ .....)vx*

Hltl    ‘•“¹    •

i * • • • »^xi r* ••)] ^L» *0-1 ¹

oraz    • x_Ł    jaet hiperpętlo).

W przypadku grafu warunek ton aa poatać

A [<*i »^xi *^ui >^£P*<^xl »^xi *^U1 >^tPJ uuf ^le-l ^ła •    •    •-!    •

Oługoić aarazruty 1 • ildść gałęzi w cięgu Mj.

Marszruta nklerowona M^ apałnla warunek

A V [*•<....*.

H«4l <*M,_ł>CP    ®“^ł

\

dla grafu

A [<*4    .«4 >£P]

U*A •-*    •    •

a cykliczna (*₁    ■    )a(1>0).

Ł_i - jaot to taka aarozrutS M^, ¹Jte wazyet-w niej różna.

aaksyaalny - łańcuch, którego

Marszrut

Łańcuch

kio u^ , o • 1,1,

Ł®o ń c u c nie nożna wydłużyć.

Łańcuch najdłuższy - Jeat to kożdy łańcuch aakayaalny o największej długości w danya grafie (hipar -grafie).

Łańcuch prosty - łańcuch o różnych wierz -chołkach.

Makayaalny    łańcuch    proety - łań

cuch prosty, którego nie nożna wydłużyć.

Najdłuższy    łańcuch    prosty - łań

cuch prosty o największej długości w danyn grafie (hipargrafia).

Łańcuch cykliczny - aarazruta cykliczna, która Jeat łańcuchoa (nazywany Jest cykle a).

Łańcuch cykliczny prosty - Jeat to taki łańcuch cykliczny, w którya wazyatkia wiarzchołki sę

cyklon

prosty a).

0 r o g a łańcuchan.

Droga no wydłużyć.

Droga

różna, z wyjętkiaa x, • x. (nazywany Jaot o 1

^u₁ - jaat to aarazruta akiarowona, . tóra jeat aakaynalna - droga, której nie noż-z a - Jaat to droga o naj -

n a J d ł u ż więkezej długości w danyn grafie.

Droga prosta - droga o różnych wierzchołkach.

Droga prosta nakeyaalna - droga proo ta, której nie nożna wydłużyć.

Najdłuższa droga proata - drogo proata o największej długości w danya grafie.

Droga cykliczna - jaat to łańcuch cykliczny, który jaot drogę (zwana jaat k o n t u r a o).

73