Faktor grafu

Faktor grafu G alebo faktorový podgraf je taký podgraf grafu G, ktorý obsahuje všetky vrcholy grafu G.

Podgraf H je faktor grafu G, ak množina vrcholov grafu H je totožná s množinou vrcholov grafu G.

${\displaystyle V(H)=V(G)}$

k-faktor grafu

Definícia: Nech je G = (V, E) graf a nech je H = (V, F) podgraf grafu G. Ak je H pravidelný graf stupňa k, tak H nazývame k-faktor grafu G.

Kompletné párovanie je 1-faktor grafu, a teda pravidelný párny graf stupňa p možno rozložit na p 1-faktorov. Ak graf nie je párny, tak nie vždy je možné rozložit pravidelný graf na 1-faktory, pretože tento graf nemusí obsahovat žiaden 1-faktor.

Petersenova veta

Pre 2-faktory platí nasledujúce tvrdenie, ktoré dokázal Julius Petersen v roku 1891.

Petersenova veta: Nech je G = (V, E) pravidelný graf stupňa 2p. Potom množinu hrán E možno rozložit na p 2-faktorov grafu G.

Externé odkazy

• Párne grafy, skriptá FMFI UK Archivované 2007-06-12 na Wayback Machine