Moniosainen kaavio

K -osainen graafi on graafi , jonka kärkijoukot voidaan jakaa k itsenäiseksi joukoksi ( osaksi ). Vastaavasti se on graafi, joka voidaan värjätä k värilläsiten, että minkä tahansa valitun reunan päätepisteet värjätään eri väreillä. Kun k  = 2 , k -osaista graafia kutsutaan kaksiosaiseksi [1] .

Kaksiosaisten graafien tunnistus voidaan tehdä polynomiajassa, mutta millä tahansa k  > 2:lla ongelmasta määrittää, onko tietty väritön graafi k - osainen, tulee NP-täydellinen [2] . Kuitenkin joissakin graafiteorian sovelluksissa k -osainen graafi voidaan antaa jo värillisenä syötteessä; tämä voi tapahtua, kun graafin kärkijoukot vastaavat erityyppisiä objekteja. Esimerkiksi folksonomiat mallinnettiin matemaattisesti kolmiosaisilla graafeilla, joissa kolme pistejoukkoa vastaavat järjestelmän käyttäjiä, resursseja, jotka ovat tunnisteen alaisia , ja itse tageja [3]

Täydellinen k -osainen graafi on k -osainen graafi siten, että mitkä tahansa kaksi kärkeä eri osissa ovat vierekkäin [1] . Täydellinen k -osainen graafi voidaan kuvata merkinnällä

missä ovat pisteiden lukumäärät graafin osissa. Esimerkiksi on säännöllisen oktaedrin täydellinen kolmiosainen graafi , joka koostuu kolmesta itsenäisestä joukosta, joista jokainen sisältää kaksi oktaedrin vastakkaista kärkeä. Täydellinen moniosainen graafi on graafi, joka on täydellinen k -osainen jollekin k :lle [4] .

Turana-graafi on täydellinen moniosainen graafi, jonka minkä tahansa kahden osan kardinaliteetti eroaa korkeintaan 1:llä. Täydelliset moniosaiset graafit ovat erikoistapaus graafista .

Muistiinpanot

  1. ↑ 1 2 Graafiteorian luentoja, 1990 , s. yksitoista.
  2. ↑ Tietokoneet ja Intractability, 1979 .
  3. ↑ Hotho, Andreas; Jaschke, Robert; Schmitz, Christoph & Stumme, Gerd (2006), FolkRank: A Ranking Algorithm for Folksonomies , LWA 2006: Lernen - Wissensentdeckung - Adaptivität, Hildesheim, 9.-11.10.2006 , s. 111–114 , < http://opus.bsz-bw.de/ubhi/volltexte/2011/39/ > 
  4. ↑ Chromatic Graph Theory, 2008 , s. 41.

Kirjallisuus