Faktor grafu: Rozdiel medzi revíziami
Smazaný obsah Přidaný obsah
iný názov |
doplnené, odstranil som sablonu na rozsirenie |
||
Riadok 1:
'''Faktor grafu G''' alebo '''faktorový podgraf''' je taký [[podgraf]] grafu '''G''', ktorý obsahuje všetky vrcholy grafu G.▼
▲'''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'''.
<math>V(H) = V(G)</math>
==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.
Pre 2-faktory platí nasledujúce tvrdenie, ktoré dokázal J. 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==
*[http://cyril.fmph.uniba.sk/mffuk/studium/stud_materialy/stud_materialy/grafy1/g1_11.pdf Párne grafy, skriptá FMFI UK]
{{Matematický výhonok}}
| |||