Polku (graafiteoria)

Graafin polku on kärkijono, jossa kukin kärki on kytketty seuraavaan reunaan.

Määritelmät

Olkoon G suuntaamaton graafi . Polku G:ssä on äärellinen tai ääretön reunojen ja kärkien sarja [1] , $S = (..., a_0, E_0, a_1, E_1, ..., E_{n-1}, a_n, ...)$

että jokaisella kahdella vierekkäisellä reunalla ja on yhteinen kärkipiste . $E_{i-1}$ $E_{i}$ $a_{i}$

Näin ollen voi kirjoittaa $..., E_0=(a_0,a_1), E_1=(a_1,a_2), ... , E_n=(a_n,a_{n+1}), ...$

Huomaa, että sama reuna voi esiintyä polulla useita kertoja. Jos edeltäviä reunoja ei ole , niin sitä kutsutaan S:n alkupisteeksi, ja jos :n jälkeen ei ole kulmia , sitä kutsutaan S:n lopulliseksi kärjeksi. Mitä tahansa kahteen vierekkäiseen reunaan kuuluvaa kärkeä kutsutaan sisäiseksi . Koska polun reunat ja kärjet voivat toistua, sisäinen kärkipiste voi olla alku- tai loppupiste. $E_{0}$ $a_{0}$ $E_{(n-1)}$ $a_n$

Jos alku- ja loppupisteet ovat samat, polkua kutsutaan sykliseksi . Polkua kutsutaan ketjuksi ja syklistä polkua sykliksi , jos jokainen sen reuna esiintyy enintään kerran (pisteet voivat toistua). Ei- syklistä polkua kutsutaan yksinkertaiseksi poluksi , jos siinä ei toistu kärkeä. Jaksoa, jolla on loppu, kutsutaan yksinkertaiseksi sykliksi, jos se ei ole siinä oleva välipiste eikä muita huippuja toistu. $a_{0}$ $a_{0}$

Valitettavasti tämä terminologia ei ole vakiintunut. Wilson [2] kirjoitti:

Sitä, mitä olemme kutsuneet reitiksi, kutsutaan myös poluksi, reunasekvenssiksi.

Ketjua kutsutaan poluksi, puoliyksinkertaiseksi poluksi; yksinkertainen ketju - ketju, polku, kaari, yksinkertainen polku, perusketju; suljettu piiri - syklinen piiri, piiri; sykli - ääriviiva, ääriviivapiiri, yksinkertainen sykli, perussykli.

— [3] [4] [5]

Polut, ketjut ja syklit ovat graafiteorian peruskäsitteitä, ja ne määritellään useimpien graafiteorian kirjojen johdanto-osassa. Katso esimerkiksi Bondi ja Marty [6] , Gibbons [7] tai Distel [8] .

Erilaisia polkuja

Polkua, jolla ei graafin reunaa yhdistä polun kahta kärkeä, kutsutaan indusoiduksi poluksi .

Yksinkertaista polkua, joka sisältää kaikki graafin kärjet ilman toistoja, kutsutaan Hamiltonin poluksi .

Yksinkertaista sykliä, joka sisältää kaikki graafin kärjet ilman toistoja, kutsutaan Hamiltonin sykliksi .

Sykliä, joka saadaan lisäämällä graafin reuna alkuperäisen graafin virittävä puuhun , kutsutaan perussykliksi.

Polun ominaisuudet

Kaksi polkua ovat kärjestä riippumattomia , jos niillä ei ole yhteisiä sisäpisteitä. Samoin kaksi polkua ovat reunasta riippumattomia , jos niillä ei ole yhteisiä sisäreunoja.

Polun pituus on polussa käytettyjen reunojen lukumäärä, jolloin uudelleenkäytettävät reunat lasketaan vastaava määrä kertoja. Pituus voi olla nolla, jos polku koostuu vain yhdestä kärjestä.

Painotettu graafi liittää jokaisen reunan johonkin arvoon ( reunapaino ). Reitin paino painotetussa graafissa on polun reunojen painojen summa. Joskus sanan paino sijasta käytetään hintaa tai pituus .

Muistiinpanot

↑ Ore, 2008 , 2.1 Reitit, piirit ja yksinkertaiset piirit, s. 34-38.
↑ Wilson, 1977 , Uudet määritelmät, s. 37.
↑ Harari, 2003 , Routes and Connectivity, s. 232.
↑ Harari, 2003 , Digraphs and Connectivity, s. 232.
↑ Christofides, 1978 , luku 1. Johdanto 2. Polut ja reitit, s. 13.
↑ Bondy, Murty, 1976 .
↑ Gibbons, 1985 .
↑ Distel, 2002 .

Katso myös

Kirjallisuus

Harari F. Graafiteoria. — M .: URSS , 2003. — 300 s. — ISBN 5-354-00301-6 .
Malmi, Oistin . Graafiteoria. — M .: URSS , 2008. — 352 s. - ISBN 978-5-397-00044-4 .
N. Christophides. Graafiteoria. Algoritminen lähestymistapa. - 2. .. - M . : Kustantaja "Mir", 1978.
R. Wilson. Johdatus graafiteoriaan. - M . : Kustantaja "Mir", 1977. - (Nykyaikainen matematiikka. Alkukurssit).
JA Bondy, USR Murty. Graafiteoria sovellusten kanssa . - Pohjois-Hollanti, 1976. - S. 12-21. — ISBN 0-444-19451-7 .
Reinhard Distel. Graafiteoria. - Novosibirsk: Matematiikan instituutin kustantamo, 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. Polut, kulkureitit ja VLSI-asettelu. - Algorithms and Combinatorics 9, Springer-Verlag, 1990. - ISBN 0-387-52685-4 .

Linkit

Weisstein, Eric W. Path Graph (englanniksi) Wolfram MathWorld -verkkosivustolla .