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.

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 

Kategória:Teória grafov