Cesta (teorie grafů)

Cesta v grafu je posloupnost vrcholů, ve kterých je každý vrchol připojen k další hraně.

Definice

Nechť G je neorientovaný graf . Cesta v G je konečná nebo nekonečná posloupnost hran a vrcholů [1] , $S = (..., a_0, E_0, a_1, E_1, ..., E_{n-1}, a_n, ...)$

že každé dvě sousední hrany a mají společný vrchol . $E_{i-1}$ $E_{i}$ $a_{i}$

Tak se dá psát $..., E_0=(a_0,a_1), E_1=(a_1,a_2), ... , E_n=(a_n,a_{n+1}), ...$

Všimněte si, že stejná hrana se může na cestě vyskytnout několikrát. Pokud před ním nejsou žádné hrany , pak se nazývá počáteční vrchol S, a pokud nejsou žádné následující hrany , pak se nazývá konečný vrchol S. Jakýkoli vrchol, který patří dvěma sousedním hranám, se nazývá vnitřní . Protože se hrany a vrcholy mohou v cestě opakovat, vnitřní vrchol může být počátečním nebo koncovým vrcholem. $E_{0}$ $a_{0}$ $E_{(n-1)}$ $a_n$

Pokud jsou počáteční a koncové vrcholy stejné, cesta se nazývá cyklická . Cesta se nazývá řetězec a cyklická cesta se nazývá cyklus , pokud se každá její hrana vyskytuje nejvýše jednou (vrcholy se mohou opakovat). Necyklická cesta se nazývá jednoduchá cesta , pokud se v ní neopakuje žádný vrchol. Cyklus s koncem se nazývá jednoduchý cyklus , pokud v něm není mezilehlým vrcholem a žádné další vrcholy se neopakují. $a_{0}$ $a_{0}$

Bohužel tato terminologie není dobře zavedená. Wilson [2] napsal:

To, co jsme nazvali trasa, se také nazývá cesta, posloupnost okrajů.

Řetězec se nazývá cesta, polojednoduchá cesta; jednoduchý řetěz - řetěz, cesta, oblouk, jednoduchá cesta, elementární řetězec; uzavřený okruh - cyklický okruh, okruh; cyklus - obrys, obrysový obvod, jednoduchý cyklus, elementární cyklus.

— [3] [4] [5]

Cesty, řetězce a cykly jsou základními pojmy v teorii grafů a jsou definovány v úvodní části většiny knih o teorii grafů. Viz například Bondi a Marty [6] , Gibbons [7] nebo Distel [8] .

Různé druhy cest

Cesta, pro kterou žádné hrany grafu nespojují dva vrcholy cesty, se nazývá indukovaná cesta .

Jednoduchá cesta obsahující všechny vrcholy grafu bez opakování je známá jako hamiltonovská cesta .

Jednoduchý cyklus obsahující všechny vrcholy grafu bez opakování je známý jako hamiltonovský cyklus .

Cyklus získaný přidáním okraje grafu do kostry původního grafu je známý jako základní cyklus.

Vlastnosti cesty

Dvě cesty jsou nezávislé na vrcholu , pokud nesdílejí vnitřní vrcholy. Podobně jsou dvě cesty nezávislé na hranách , pokud nesdílejí vnitřní hrany.

Délka cesty je počet hran použitých v cestě, přičemž opakovaně použitelné hrany se počítají odpovídající počet opakování. Délka může být nulová, pokud se cesta skládá pouze z jednoho vrcholu.

Vážený graf spojuje každou hranu s nějakou hodnotou ( tloušťka hrany ). Váha cesty ve váženém grafu je součtem vah hran cesty. Někdy se místo slova hmotnost cena nebo délka používá .

Poznámky

↑ Ruda, 2008 , 2.1 Trasy, okruhy a jednoduché okruhy, str. 34-38.
↑ Wilson, 1977 , Nové definice, str. 37.
↑ Harari, 2003 , Trasy a konektivita, str. 232.
↑ Harari, 2003 , Digraphs and Connectivity, str. 232.
↑ Christofides, 1978 , Kapitola 1. Úvod 2. Cesty a cesty, str. 13.
↑ Bondy, Murty, 1976 .
↑ Gibbons, 1985 .
↑ Distel, 2002 .

Viz také

Literatura

Harari F. Teorie grafů. — M .: URSS , 2003. — 300 s. — ISBN 5-354-00301-6 .
Ore, Oistine . Teorie grafů. — M .: URSS , 2008. — 352 s. - ISBN 978-5-397-00044-4 .
N. Christophides. Teorie grafů. Algoritmický přístup. - 2. .. - M . : Nakladatelství "Mir", 1978.
R. Wilson. Úvod do teorie grafů. - M . : Nakladatelství "Mir", 1977. - (Moderní matematika. Úvodní kurzy).
JA Bondy, USR Murty. Teorie grafů s aplikacemi . - Severní Holandsko, 1976. - S. 12-21. — ISBN 0-444-19451-7 .
Reinhard Distel. Teorie grafů. - Novosibirsk: Nakladatelství Ústavu matematiky, 2002. - ISBN 5-86134-101-X .
Gibbons, A. Algorithmic Graph Theory. - Cambridge University Press, 1985. - S. 5-6. — ISBN 0-521-28881-9 .
Bernhard Korte, László Lovász, Hans Jürgen Prömel Alexander Schrijver. Cesty, toky a rozložení VLSI. - Algorithms and Combinatorics 9, Springer-Verlag, 1990. - ISBN 0-387-52685-4 .

Odkazy

Weisstein, Eric W. Path Graph (anglicky) na webových stránkách Wolfram MathWorld .