Vícedílný graf

K -partitní graf je graf , jehož množinu vrcholů lze rozdělit na k nezávislých množin ( částí ). Ekvivalentně se jedná o graf, který lze obarvit k barvami tak, že koncové body libovolné zvolené hrany jsou obarveny různými barvami. Když k  = 2 , k -partitní graf se nazývá bipartitní [1] .

Rozpoznání bipartitních grafů lze provést v polynomiálním čase, ale pro jakékoli k  > 2 se problém určení, zda daný nevybarvený graf je k -partitní, stává NP-úplným [2] . V některých aplikacích teorie grafů však může být k -partitní graf dán již obarvený na vstupu; k tomu může dojít, když sady vrcholů grafu odpovídají různým typům objektů. Například folksonomie byly matematicky modelovány pomocí tripartitních grafů, ve kterých tři sady vrcholů odpovídají uživatelům systému, zdrojům, které podléhají tagování , a samotným tagům [3]

Úplný k -partitní graf je k -partitní graf takový, že libovolné dva vrcholy v různých částech sousedí [1] . Kompletní k -partitní graf lze popsat notací

kde jsou počty vrcholů v částech grafu. Například je úplný tripartitní graf pravidelného osmistěnu , který se skládá ze tří nezávislých souborů, z nichž každá obsahuje dva protilehlé vrcholy osmistěnu. Úplný vícedílný graf je graf, který je úplný k -partitní pro nějaké k [4] .

Turanův graf je úplný vícedílný graf, jehož mohutnosti jakýchkoli dvou částí se neliší o více než 1. Úplné vícedílné grafy jsou speciálním případem kografů .

Poznámky

  1. ↑ 1 2 Přednášky o teorii grafů, 1990 , str. jedenáct.
  2. ↑ Počítače a neovladatelnost, 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. října 2006 , str. 111–114 , < http://opus.bsz-bw.de/ubhi/volltexte/2011/39/ > 
  4. ↑ Teorie chromatických grafů, 2008 , str. 41.

Literatura