Теоремаи Кёниг

Теоремаи Кёниг

Муқаддима

Дар ин боб мо теоремаи Кёнигро дар назарияи графҳо баррасӣ мекунем ва мебинем, ки он чӣ гуна метавонад ба мо дар ҳалли масъалаҳо кӯмак кунад.

Баёни теоремаи Кёниг

Ҳамаи мо медонем, ки паросочетание дар назарияи графҳо чист. Биёед боз як мафҳумро баррасӣ кунем — пӯшиши қуллаҳо (аз ҷумла, пӯшиши қуллаҳои минималӣ).

Пӯшиши қуллаҳо

Пӯшиши қуллаҳо дар графи $G$ — ин зермаҷмӯи қуллаҳо

аст, ки ҳар як ребро $e \in E$ ҳадди ақал ба як қулла аз $S$ инцидент аст
(яъне ребро пӯшида шудааст).

Пӯшиши қуллаҳои минималӣ — пӯшиши қуллаҳо бо андозаи минималӣ.

Баёни теоремаи Кёниг

Бигзор — графи дудольный бошад.