Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
Stránky: 1
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 a dva jeho vrcholy , . Sestrojte výrokovou formuli, která je splnitelná, právě když 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 a vede hrana, jsou v různých partitách. Víc o tom nemohu určit, ne? Jenže mezi a může vést (či nevést) hrana i v případě, že graf není bipartitní.
Poradíte mi někdo, prosím?
Offline
↑ 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 . Sestrojte výrokovou formuli, která je splnitelná, právě když je bipartitní.
?
Offline
↑ 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.
Offline
↑ 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.
Offline
Stránky: 1