Grafic multipartit

Un graf k -partit este un graf al cărui set de vârfuri poate fi împărțit în k mulțimi independente ( părți ). În mod echivalent, este un grafic care poate fi colorat cu k culori, astfel încât punctele finale ale oricărei muchii alese să fie colorate cu culori diferite. Când k  = 2 , un graf k -partit se numește bipartit [1] .

Recunoașterea graficelor bipartite se poate face în timp polinomial, dar pentru orice k  > 2 problema de a determina dacă un graf dat necolorat este k -partit devine NP-complet [2] . Cu toate acestea, în unele aplicații ale teoriei grafurilor, un graf k -partit poate fi dat deja colorat la intrare; acest lucru se poate întâmpla atunci când seturile de vârfuri ale graficului corespund diferitelor tipuri de obiecte. De exemplu, folksonomiile au fost modelate matematic prin grafice tripartite, în care trei seturi de vârfuri corespund utilizatorilor sistemului, resurselor care sunt supuse etichetării și etichetelor în sine [3]

Un graf complet k - partit este un graf k -partit astfel încât oricare două vârfuri din părți diferite sunt adiacente [1] . Un graf k -partit complet poate fi descris prin notație

unde sunt numărul de vârfuri din părți ale graficului. De exemplu, este un grafic tripartit complet al unui octaedru regulat , constând din trei mulțimi independente, fiecare dintre ele incluzând două vârfuri opuse ale octaedrului. Un graf complet multipartit este un graf complet k - partit pentru unele k [4] .

Graficul Turana este un graf complet multipartit, ale cărui cardinalități ale oricăror două părți diferă cu cel mult 1. Graficele complete multipartite sunt un caz special de cograf .

Note

  1. ↑ 1 2 Prelegeri despre teoria grafurilor, 1990 , p. unsprezece.
  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 octombrie 2006 , p. 111–114 , < http://opus.bsz-bw.de/ubhi/volltexte/2011/39/ > 
  4. ↑ Teoria graficelor cromatice, 2008 , p. 41.

Literatură