Flerdelad graf

En k -partitgraf är en graf vars uppsättning av hörn kan delas in i k oberoende uppsättningar ( delar ). På motsvarande sätt är det en graf som kan färgas med k färger så att ändpunkterna på valfri vald kant färgas med olika färger. När k  = 2 kallas en k -partit graf bipartit [1] .

Identifiering av tvådelade grafer kan göras i polynomtid, men för varje k  > 2 blir problemet med att avgöra om en given ofärgad graf är k -partit NP-komplett [2] . I vissa tillämpningar av grafteori kan emellertid en k -partitgraf ges redan färgad vid ingången; detta kan hända när toppens uppsättningar av grafen motsvarar olika typer av objekt. Till exempel modellerades folksonomier matematiskt av tredelade grafer, där tre uppsättningar av hörn motsvarar användarna av systemet, resurser som är föremål för taggning och själva taggar [3]

En komplett k -partitgraf är en k -partitgraf så att två hörn i olika delar är intilliggande [1] . En komplett k -partitgraf kan beskrivas med notationen

var är antalet hörn i delar av grafen. Till exempel är en komplett tredelad graf av en vanlig oktaeder , bestående av tre oberoende uppsättningar, som var och en inkluderar två motsatta hörn av oktaedern. En komplett flerdelad graf är en graf som är komplett k -partit för några k [4] .

Turana-grafen är en komplett flerdelad graf, vars kardinaliteter för två delar av dessa inte skiljer sig mer än 1. Kompletta flerdelade grafer är ett specialfall av kografer .

Anteckningar

  1. ↑ 1 2 Föreläsningar om grafteori, 1990 , sid. elva.
  2. ↑ Datorer och 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 oktober 2006 , sid. 111–114 , < http://opus.bsz-bw.de/ubhi/volltexte/2011/39/ > 
  4. ↑ Chromatic Graph Theory, 2008 , sid. 41.

Litteratur