Luotu alikaavio

Graafin generoitu aligraafi  on toinen graafi, joka on muodostettu graafin kärkien osajoukosta sekä kaikista reunoista, jotka yhdistävät tämän osajoukon kärkipareja.

Määritelmä

Olkoon G = ( V , E ) muodollisesti  mikä tahansa graafi ja olkoon S ⊂ V G  :n pisteiden osajoukko . Tällöin generoitu osagraafi G [ S ]  on graafi, jonka kärjet ovat S :n alkioita ja jonka reunat koostuvat kaikista joukon E reunoista , joiden lopulliset kärjet kuuluvat S :lle [1] . Sama määritelmä pätee ohjaamattomiin kaavioihin , suunnattuihin kaavioihin ja jopa monikuvaaviin .

Generoitua aligraafia G [ S ] voidaan kutsua myös G :ssä joukon pisteitä S generoimaksi aligraafiksi tai (jos konteksti ei johda epäselvyyteen) generoiduksi pisteiden S aligraafiksi .

Esimerkkejä

Tärkeitä alagraafien tyyppejä ovat seuraavat:

• generoidut polut  ovat generoituja alikaavioita, jotka ovat polkuja . Lyhin polku minkä tahansa kahden pisteen välillä painottamattomassa graafissa on aina generoitu polku. Sitä vastoin etäisyyden periytyvissä kaavioissa mikä tahansa luotu graafi on lyhin polku [2] .
• Syntyneet syklit  ovat synnytettyjä alikaavioita, jotka ovat silmukoita . Graafin ympärysmitta määräytyy sen lyhimmän syklin pituuden mukaan, joka on aina generoitu jakso. Tiukan täydellisen graafin lauseen mukaan generoidut syklit ja niiden komplementit ovat ratkaisevassa asemassa täydellisten graafien karakterisoinnissa [3] .
• Klikit ja riippumattomat joukot ovat generoituja aligraafia, jotka ovat täydellisiä aligraafia tai graafisia ilman reunoja.
• Vertex- naapuruus on generoitu aligraafi valitun kärjen kaikista vierekkäisistä pisteistä.

Laskenta

Generoitu aligraafin isomorfismiongelma on eräänlainen isomorfisen osagraafin hakutehtävä , jossa tavoitteena on testata, löytyykö yksi graafi toisen graafin generoituna osagraafina. Koska tämä ongelma sisältää klikkiongelman erikoistapauksena, se on NP-täydellinen [4] .

Muistiinpanot

1. ↑ Diestel, 2006 , s. 3–4.
2. ↑ Howorka, 1977 , s. 417–420.
3. ↑ Chudnovsky, Robertson, Seymour, Thomas, 2006 , s. 51–229.
4. ↑ Johnson, 1985 , s. 434–451.

Kirjallisuus

• Reinhard Diestel. graafiteoria . - Springer-Verlag, 2006. - T. 173. - S. 3–4. — (Matematiikan tutkinnon tekstit). — ISBN 9783540261834 .
  • Reinhard Distel. Graafiteoria. - Novosibirsk: Matematiikan instituutin kustantamo, 2002. - ISBN 5-86134-101-X .
• Edward Howorka. Etäisyysperinnöllisten kaavioiden luonnehdinta  // The Quarterly Journal of Mathematics. Oxford. toinen sarja. - 1977. - T. 28 , no. 112 . — S. 417–420 . doi : 10.1093 / qmath/28.4.417 .
• Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. Vahva täydellisen graafin lause  // Matematiikan Annals . - 2006. - T. 164 , no. 1 . — S. 51–229 . doi : 10.4007 / annals.2006.164.51 .
• David S Johnson NP-täydellisyyssarake: jatkuva opas // Journal of Algorithms. - 1985. - T. 6 , no. 3 . — S. 434–451 . - doi : 10.1016/0196-6774(85)90012-4 .