Matematické Fórum

slender · 21. 11. 2016 11:35

Zdravím,
nějak jsem se zasekl při řešení úloh z výrokové logiky.

Zadání zní takto:
Je dán (neorientovaný) graf $G$ a dva jeho vrcholy $u$ , $v$ . Sestrojte výrokovou formuli, která je splnitelná, právě když $G$ je bipartitní.

První věc, která mě trochu zarazila je to, že se v zadání ptají na splnitelnost nikoli pravdivost formule.

Další věc, které zcela nerozumím, je to, jak vůbec takovou formuli sestrojit. Nemám pro to málo informací? Jediné, co vím je, že v bipartitním grafu platí, že pokud mezi $u$ a $v$ vede hrana, jsou v různých partitách. Víc o tom nemohu určit, ne? Jenže mezi $u$ a $v$ může vést (či nevést) hrana i v případě, že graf není bipartitní.

Poradíte mi někdo, prosím?

check_drummer · 21. 11. 2016 14:34

↑ slender:
Ahoj, není mi jasné, jakou roli v tom hrají ty vrcholy u,v. Nestačilo by řešit úlohu:
Je dán (neorientovaný) graf $G$ . Sestrojte výrokovou formuli, která je splnitelná, právě když $G$ je bipartitní.
?

slender

↑ check_drummer: Mně právě také ne.

Ale ani u tebou zmiňovaného zadání moc netuším, jak to řešit. Napadlo mě na to jít nějak přes to, že bipartitní graf neobsahuje lichý cyklus, ale nenapadá mě, jak to zapsat.

check_drummer · 24. 11. 2016 18:06

↑ slender:
Já nevím co vše je dovoleno kvantifikovat, třeba by to šlo vyjádřit tak, že existuje dělení vrcholů na dvě disjunktní podmnožiny A,B, kde mezi žádnými dvěma vrcholy z A i z B nevede hrana.

Matematické Fórum

#1 21. 11. 2016 11:35

Formule splnitelná právě v bipartitním grafu

#2 21. 11. 2016 14:34

Re: Formule splnitelná právě v bipartitním grafu

#3 21. 11. 2016 15:21 — Editoval slender (21. 11. 2016 15:45)

Re: Formule splnitelná právě v bipartitním grafu

#4 24. 11. 2016 18:06

Re: Formule splnitelná právě v bipartitním grafu

Zápatí