Útvonal (gráfelmélet)

A gráf útvonala olyan csúcsok sorozata, amelyben minden csúcs a következő élhez kapcsolódik.

Definíciók

Legyen G egy irányítatlan gráf . Egy út G-ben élek és csúcsok véges vagy végtelen sorozata [1] , $S = (..., a_0, E_0, a_1, E_1, ..., E_{n-1}, a_n, ...)$

hogy minden két szomszédos élnek és van egy közös csúcsa . $E_{i-1}$ $E_{i}$ $a_{i}$

Így lehet írni $..., E_0=(a_0,a_1), E_1=(a_1,a_2), ... , E_n=(a_n,a_{n+1}), ...$

Vegye figyelembe, hogy ugyanaz az él többször is előfordulhat egy útvonalon. Ha nincsenek élek előtt , akkor S kezdeti csúcsának nevezzük, ha pedig nincsenek élek , akkor S végső csúcsának nevezzük. Minden olyan csúcsot, amely két szomszédos élhez tartozik, belsőnek nevezzük . Mivel az élek és a csúcsok megismételhetők az útvonalon, egy belső csúcs lehet a kezdő vagy a végcsúcs. $E_{0}$ $a_{0}$ $E_{(n-1)}$ $a_n$

Ha a kezdő és a vég csúcsok azonosak, az utat ciklikusnak nevezzük . Egy utat láncnak nevezünk , a ciklikus utat pedig ciklusnak , ha minden éle legfeljebb egyszer fordul elő (a csúcsok ismétlődnek). Egy nem ciklikus útvonalat egyszerű útvonalnak nevezünk , ha egyetlen csúcs sem ismétlődik benne. Egy végű ciklust egyszerű ciklusnak nevezünk , ha az nem egy közbenső csúcs, és nem ismétlődik más csúcs. $a_{0}$ $a_{0}$

Sajnos ez a terminológia nem teljesen megalapozott. Wilson [2] írta:

Amit mi útvonalnak nevezünk, azt útnak is nevezzük, élsorozatnak.

A láncot útnak, félig egyszerű útnak nevezik; egyszerű lánc - lánc, út, ív, egyszerű út, elemi lánc; zárt áramkör - ciklikus áramkör, áramkör; ciklus - egy kontúr, egy kontúrkör, egy egyszerű ciklus, egy elemi ciklus.

— [3] [4] [5]

Az utak, láncok és ciklusok a gráfelmélet alapvető fogalmai, és a legtöbb gráfelméleti könyv bevezető részében vannak meghatározva. Lásd például Bondi és Marty [6] , Gibbons [7] vagy Distel [8] .

Különféle útvonalak

Indukált útvonalnak nevezzük azt az utat, amelynél a gráfélek nem kötik össze az út két csúcsát .

Egy egyszerű útvonalat, amely a gráf összes csúcsát tartalmazza ismétlődés nélkül, Hamilton-útnak nevezzük .

Egy egyszerű ciklust, amely a gráf összes csúcsát tartalmazza ismétlődés nélkül, Hamilton-ciklusnak nevezzük .

Azt a ciklust, amelyet úgy kapunk, hogy a gráf élét hozzáadjuk az eredeti gráf feszítőfájához , Alapciklusnak nevezzük.

Útvonal tulajdonságai

Két út csúcsfüggetlen , ha nem osztoznak a belső csúcsokon. Hasonlóképpen, két útvonal élfüggetlen, ha nem osztoznak a belső éleken.

Az útvonal hossza az útvonalban használt élek száma, és az újrafelhasználható éleket a megfelelő számú alkalommal megszámolja. A hossza nulla lehet, ha az út csak egy csúcsból áll.

A súlyozott gráf minden élt valamilyen értékkel ( élsúly ) társít. Egy súlyozott gráfban egy útvonal súlya az útvonal éleinek súlyának összege. Néha a súly szó helyett az ár vagy a hossz szót használják .

Jegyzetek

↑ Ore, 2008 , 2.1 Útvonalak, áramkörök és egyszerű áramkörök, p. 34-38.
↑ Wilson, 1977 , Új definíciók, p. 37.
↑ Harari, 2003 , Routes and Connectivity, p. 232.
↑ Harari, 2003 , Digraphs and Connectivity, p. 232.
↑ Christofides, 1978 , 1. fejezet. Bevezetés 2. Utak és útvonalak, p. 13.
↑ Bondy, Murty, 1976 .
↑ Gibbons, 1985 .
↑ Distel, 2002 .

Lásd még

Irodalom

Harari F. Gráfelmélet. — M .: URSS , 2003. — 300 p. — ISBN 5-354-00301-6 .
Érc, Oistin . Gráfelmélet. — M .: URSS , 2008. — 352 p. - ISBN 978-5-397-00044-4 .
N. Christophides. Gráfelmélet. Algoritmikus megközelítés. - 2. .. - M . : "Mir" kiadó, 1978.
R. Wilson. Bevezetés a gráfelméletbe. - M . : "Mir" kiadó, 1977. - (Modern matematika. Bevezető kurzusok).
JA Bondy, USR Murty. Gráfelmélet alkalmazásokkal . - Észak-Hollandia, 1976. - S. 12-21. — ISBN 0-444-19451-7 .
Reinhard Distel. Gráfelmélet. - Novoszibirszk: Matematikai Intézet Kiadója, 2002. - ISBN 5-86134-101-X .
Gibbons, A. Algoritmikus gráfelmélet. - Cambridge University Press, 1985. - S. 5-6. — ISBN 0-521-28881-9 .
Bernhard Korte, Lovász László, Hans Jürgen Prömel Alexander Schrijver. Útvonalak, folyamatok és VLSI-elrendezés. - Algorithms and Combinatorics 9, Springer-Verlag, 1990. - ISBN 0-387-52685-4 .

Linkek

Weisstein, Eric W. Path Graph (angol) a Wolfram MathWorld webhelyen .