Sti (grafteori)

En sti i en graf er en sekvens af hjørner, hvor hvert hjørne er forbundet med den næste kant.

Definitioner

Lad G være en urettet graf . En sti i G er en endelig eller uendelig række af kanter og hjørner [1] , $S = (..., a_0,E_0, a_1, E_1, ..., E_{n-1}, a_n, ...)$

at hver to tilstødende kanter og har et fælles toppunkt . $E_{i-1}$ $E_{i}$ $a_{i}$

Således kan man skrive $..., E_0=(a_0,a_1), E_1=(a_1,a_2), ... , E_n=(a_n,a_{n+1}), ...$

Bemærk, at den samme kant kan forekomme flere gange i en sti. Hvis der ikke er nogen kanter foran , så kaldes det det indledende toppunkt af S, og hvis der ikke er nogen kanter efter , så kaldes det det endelige toppunkt af S. Ethvert toppunkt, der hører til to tilstødende kanter, kaldes internt . Fordi kanter og toppunkter kan gentages i en sti, kan et indre toppunkt være start- eller sluttoppunktet. $E_{0}$ $a_{0}$ $E_{(n-1)}$ $a_n$

Hvis start- og slutspidserne er de samme, kaldes stien cyklisk . En sti kaldes en kæde , og en cyklisk sti kaldes en cyklus , hvis hver af dens kanter højst forekommer én gang (hjørnepunkter kan gentages). En ikke -cyklisk sti kaldes en simpel sti, hvis ingen toppunkt gentages i den. En cyklus med en ende kaldes en simpel cyklus, hvis den ikke er et mellemliggende toppunkt i den, og ingen andre toppunkter gentages. $a_{0}$ $a_{0}$

Desværre er denne terminologi ikke veletableret. Wilson [2] skrev:

Det, vi har kaldt en rute, kaldes også en sti, en kantsekvens.

Kæden kaldes en sti, en semi-simpel sti; en simpel kæde - en kæde, en sti, en bue, en simpel sti, en elementær kæde; et lukket kredsløb - et cyklisk kredsløb, et kredsløb; cyklus - en kontur, et konturkredsløb, en simpel cyklus, en elementær cyklus.

— [3] [4] [5]

Stier, kæder og cyklusser er grundlæggende begreber i grafteori og er defineret i den indledende del af de fleste grafteoribøger. Se for eksempel Bondi og Marty [6] , Gibbons [7] eller Distel [8] .

Forskellige slags stier

En sti, hvor ingen grafkanter forbinder to hjørner af stien, kaldes en induceret sti .

En simpel sti, der indeholder alle hjørnerne af en graf uden gentagelser, er kendt som en Hamiltonsk sti .

En simpel cyklus, der indeholder alle hjørnerne af en graf uden gentagelser, er kendt som en Hamilton-cyklus .

Cyklusen opnået ved at tilføje en kant af grafen til spændingstræet i den originale graf er kendt som den grundlæggende cyklus.

Stiegenskaber

To stier er toppunktuafhængige , hvis de ikke deler indre toppunkter. På samme måde er to stier kantuafhængige , hvis de ikke deler indvendige kanter.

Stilængden er antallet af kanter, der bruges i stien, hvor genanvendelige kanter tælles det tilsvarende antal gange. Længden kan være nul, hvis stien kun består af et toppunkt.

En vægtet graf forbinder hver kant med en eller anden værdi ( kantvægt ). Vægten af en sti i en vægtet graf er summen af vægten af stiens kanter. Nogle gange bruges i stedet for ordet vægt pris eller længde .

Noter

↑ Ore, 2008 , 2.1 Ruter, kredsløb og simple kredsløb, s. 34-38.
↑ Wilson, 1977 , Nye definitioner, s. 37.
↑ Harari, 2003 , Ruter og forbindelser, s. 232.
↑ Harari, 2003 , Digraphs and Connectivity, s. 232.
↑ Christofides, 1978 , kapitel 1. Indledning 2. Stier og ruter, s. 13.
↑ Bondy, Murty, 1976 .
↑ Gibbons, 1985 .
↑ Distel, 2002 .

Se også

Litteratur

Harari F. Grafteori. — M .: URSS , 2003. — 300 s. — ISBN 5-354-00301-6 .
Malm, Oistin . Grafteori. — M .: URSS , 2008. — 352 s. - ISBN 978-5-397-00044-4 .
N. Christophides. Grafteori. Algoritmisk tilgang. - 2. .. - M . : Forlag "Mir", 1978.
R. Wilson. Introduktion til grafteori. - M . : Forlaget "Mir", 1977. - (Moderne matematik. Introduktionskurser).
JA Bondy, USR Murty. Grafteori med applikationer . - Nordholland, 1976. - S. 12-21. — ISBN 0-444-19451-7 .
Reinhard Distel. Grafteori. - Novosibirsk: Publishing House of the Institute of Mathematics, 2002. - ISBN 5-86134-101-X .
Gibbons, A. Algoritmisk grafteori. - 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. Stier, flows og VLSI-layout. - Algorithms and Combinatorics 9, Springer-Verlag, 1990. - ISBN 0-387-52685-4 .