Polku (kuvaajateoria) - Path (graph theory)

Polkuja kuvaavien kuvaajaryhmien osalta katso Reittikaavio .
Kolmiulotteinen hyperkuutiokaavio, joka näyttää Hamiltonin polun punaisena ja pisin indusoidun polun lihavoituna mustana.

In graafiteoria , eli polku on kaavio on äärellinen tai ääretön sekvenssi, ja reunat , jotka tulevat sekvenssin pisteiden , jotka useimmat määritelmät, ovat kaikki erillisiä (ja koska solmut ovat erillisiä, niin ovat reunat). Suunnattu polku (joskus kutsutaan dipath ) on suunnattu verkko on äärellinen tai ääretön sekvenssi reunojen joka yhdistää sekvenssi erillisten pisteiden, mutta lisättynä rajoitus, että reunat on kaikki suunnattu samaan suuntaan.

Polut ovat graafiteorian peruskäsitteitä, jotka on kuvattu useimpien graafiteorian tekstien johdanto -osissa. Katso esim. Bondy ja Murty (1976), Gibbons (1985) tai Diestel (2005). Korte et ai. (1990) kattaa edistyneemmät algoritmiset aiheet, jotka koskevat kaavioita.

Määritelmät

Kävele, polku, polku

Polku, mutta ei path.svg
Olkoon G = ( V , E , ϕ ) kaavio. Äärellinen kulku on reunojen sarja ( e 1 , e 2 ,…, e n - 1 ) , jolle on olemassa pisteiden sarja ( v 1 , v 2 ,…, v n ) siten, että ϕ ( e i ) = { v i , v i + 1 }, kun i = 1, 2,…, n - 1 . ( v 1 , v 2 ,…, v n ) on kävelyn kärkipiste . Tämä kävely on suljettu, jos v 1 = v n , ja auki muuten. Ääretön kävely on tässä kuvattu samantyyppisten reunojen sarja, jossa ei ole ensimmäistä tai viimeistä kärkeä, ja puoli-äärettömällä kävelyllä (tai säteellä ) on ensimmäinen, mutta ei viimeinen kärki.
  • Reitti on kävellä, jossa kaikki reunat ovat erillisiä.
  • Polku on polku, jonka kaikki pisteet (ja näin ollen myös kaikki reunat) ovat erillisiä.

Jos w = ( e 1 , e 2 , ..., e n - 1 ) on äärellinen kävellä piste sekvenssi ( v 1 , v 2 , ..., v n ) sitten w sanotaan olevan kävelymatka v 1 ja v n . Samoin polulle tai polulle. Jos kahden erillisen kärjen välillä on rajallinen kävely, on myös rajallinen polku ja rajallinen polku niiden välissä.

Jotkut kirjoittajat eivät vaadi, että kaikki polun kärkipisteet ovat erillisiä, ja käyttävät sen sijaan termiä yksinkertainen polku viittaamaan tällaiseen polkuun.

Painotettu kaavio liittää arvo ( paino ), jossa jokainen reuna kaaviossa. Paino kävellä (tai polkua tai polku) on painotettu kaavio on summa painot kulki reunat. Joskus painon sijaan käytetään sanoja hinta tai pituus .

Suunnattu kävely, polku, polku

  • Suunnattu kävellä on äärellinen tai ääretön sekvenssin ja reunat on suunnattu samaan suuntaan, joka liittyy sekvenssin pisteiden .
Olkoon G = ( V , E , ϕ ) suunnattu kuvaaja. Äärellinen suunnattu kävely on reunojen sarja ( e 1 , e 2 ,…, e n - 1 ) , jolle on olemassa pisteiden sarja ( v 1 , v 2 ,…, v n ) siten, että ϕ ( e i ) = ( v i , v i + 1 ), kun i = 1, 2,…, n - 1 . ( v 1 , v 2 ,…, v n ) on suunnatun kävelyn kärkipiste . Ääretön suunnattu kävely on tässä kuvattu samantyyppisten reunojen sarja, mutta ilman ensimmäistä tai viimeistä kärkeä, ja puoli-äärettömällä suunnatulla kävelyllä (tai säteellä ) on ensimmäinen, mutta ei viimeinen kärki.
  • Suunnattu polku on suunnattu kävellä, jossa kaikki reunat ovat erillisiä.
  • Suunnattu polku on suunnattu polku, jonka kaikki pisteet ovat erillisiä.

Jos w = ( e 1 , e 2 , ..., e n - 1 ) on äärellinen suunnattu kävellä piste sekvenssi ( v 1 , v 2 , ..., v n ) sitten w sanotaan olevan kävelymatka v 1 ja v n . Samoin suunnatulle polulle tai polulle. Jos kahden erillisen kärjen välillä on äärellinen suunnattu kävely, silloin on myös äärellinen suunnattu polku ja rajallinen suunnattu polku niiden välillä.

Jotkut kirjoittajat eivät vaadi, että kaikki suunnatun polun pisteet ovat erillisiä, ja käyttävät sen sijaan termiä yksinkertainen suunnattu polku viittaamaan tällaiseen suunnattuun polkuun.

Painotettu suunnattu graafi liittää arvo ( paino ), jossa jokainen reuna suunnatun verkon. Paino suunnatun kävellä (tai polkua tai polku) on painotettu suunnattu kuvio on summa painot kulki reunat. Joskus painon sijaan käytetään sanoja hinta tai pituus .

Esimerkkejä

  • Kaavio yhdistetään, jos on olemassa polkuja, jotka sisältävät jokaisen kärkiparin.
  • Suunnattu kuvaaja on vahvasti yhteydessä toisiinsa, jos kukin kärkipari sisältää vastakkaisia ​​suuntautuneita suunnattuja polkuja.
  • Reittiä, jolla ei ole graafin reunoja, jotka yhdistävät kahta peräkkäistä polkua, kutsutaan indusoiduksi poluksi .
  • Polku, joka sisältää kaavion kaikki kärkipisteet, tunnetaan Hamiltonin polkuna .
  • Kaksi polkua ovat pisteistä riippumattomia (vaihtoehtoisesti sisäisesti vertex-disjoint ), jos niillä ei ole yhteistä sisäistä kärkeä. Vastaavasti kaksi polkua ovat reunasta riippumattomia (tai reunaerotettuja ), jos niillä ei ole yhteistä sisäreunaa. Kaksi sisäisesti vertex-disjoint-polkua ovat reuna-disjoint, mutta päinvastoin ei välttämättä ole totta.
  • Etäisyys välillä kaksi pistettä graafisesti on pituus on lyhin polku niiden välillä, jos sellainen on olemassa, ja muuten etäisyys on ääretön.
  • Yhdistetyn kuvaajan halkaisija on suurin (edellä määritelty) etäisyys kuvaajan kärkiparien välillä.

Polkujen etsiminen

On olemassa useita algoritmeja lyhyimpien ja pisimpien polkujen löytämiseksi kaavioista, ja siinä on tärkeä ero, että ensimmäinen ongelma on laskennallisesti paljon helpompi kuin jälkimmäinen.

Dijkstran algoritmi tuottaa luettelon lyhyimmistä poluista lähteen kärjestä jokaiseen muuhun kärkeen suunnatuissa ja suunnattomissa kaavioissa, joilla on ei-negatiiviset reunapainot (tai ilman reunapainoja), kun taas Bellman-Ford-algoritmia voidaan soveltaa kohdistettuihin kaavioihin, joilla on negatiiviset reunapainot . Floyd-Warshallin algoritmia voidaan käyttää löytämään lyhimmän polun kaikkien parien pisteiden painotettu suunnattuja graafeja.

Katso myös

Viitteet

  • Bender, Edward A .; Williamson, S. Gill (2010). Luettelot, päätökset ja kaaviot. Johdatus todennäköisyyteen .
  • Bondy, JA; Murty, USR (1976). Graafiteoria sovelluksineen . Pohjois -Hollanti. s. 12-21 . ISBN 0-444-19451-7.
  • Diestel, Reinhard (2005). Kaavioteoria . Springer-Verlag. s. 6–9. ISBN 3-540-26182-6.
  • Gibbons, A. (1985). Algoritmisen kuvaajan teoria . Cambridge University Press. s. 5–6. ISBN 0-521-28881-9.
  • Korte, Bernhard ; Lovász, László ; Prömel, Hans Jürgen; Schrijver, Alexander (1990). Polut, virtaukset ja VLSI-asettelu . Springer-Verlag. ISBN 0-387-52685-4.