Flerdelt graf

En k -partite graf er en graf, hvis sæt af hjørner kan opdeles i k uafhængige sæt ( dele ). Tilsvarende er det en graf, der kan farves med k farver, således at endepunkterne af enhver valgt kant farves med forskellige farver. Når k  = 2 , kaldes en k -partit graf todelt [1] .

Genkendelse af todelte grafer kan udføres i polynomisk tid, men for enhver k  > 2 bliver problemet med at bestemme, om en given ufarvet graf er k - partit, NP-komplet [2] . Men i nogle anvendelser af grafteori kan en k -partite graf gives allerede farvet ved input; dette kan ske, når toppunkterne i grafen svarer til forskellige typer objekter. For eksempel blev folksonomier matematisk modelleret af tredelte grafer, hvor tre sæt hjørner svarer til brugere af systemet, ressourcer, der er underlagt tagging , og tags selv [3]

En komplet k -partite graf er en k -partite graf, således at to vilkårlige spidser i forskellige dele støder op til hinanden [1] . En komplet k -partite graf kan beskrives med notationen

hvor er antallet af hjørner i dele af grafen. For eksempel er en komplet tredelt graf af et regulært oktaeder , bestående af tre uafhængige sæt, som hver omfatter to modsatte hjørner af oktaederet. En komplet multipartite graf er en graf, der er komplet k -partite for nogle k [4] .

Turana-grafen er en komplet flerdelt graf, hvis kardinaliteter af to dele ikke afviger mere end 1. Komplette multipartite grafer er et særligt tilfælde af kografer .

Noter

  1. ↑ 1 2 Forelæsninger om grafteori, 1990 , s. elleve.
  2. ↑ Computers and 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 , s. 111–114 , < http://opus.bsz-bw.de/ubhi/volltexte/2011/39/ > 
  4. ↑ Chromatic Graph Theory, 2008 , s. 41.

Litteratur