Faktor grafu

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

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.

V(H) = V(G)

k-faktor grafu[upraviť | upraviť zdroj]

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[upraviť | upraviť zdroj]

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[upraviť | upraviť zdroj]