DÚ 4: Súvislosť grafov
Požiadavky na absolvovanie
Termín: piatok, 18 marca 2022, 23:59
1.
Nájdite graf
s najmenším počtom vrcholov a hrán,
v ktorom existuje sled (resp. ťah, cesta) dĺžky 1,2 resp.
2. Majme päťprvkovú množinu . Nech je graf, ktorého vrcholy budú všetky dvojprvkové podmnožiny množiny . Dva vrcholy spojíme hranou, pokiaľ sú zodpovedajúce podmnožiny disjunktné.
a. Ukážte, že graf je súvislý.
b. Nakreslite diagram takého grafu.