Matematické Fórum

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

#1 21. 11. 2016 11:35

slender
Příspěvky: 151
Pozice: student
Reputace:   
 

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

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?

Offline

 

#2 21. 11. 2016 14:34

check_drummer
Příspěvky: 3867
Reputace:   91 
 

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

↑ 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í.
?


Ve 21. století i vzdělaní lidé učili své děti, že látka je tvořená z atomů.

Offline

 

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

slender
Příspěvky: 151
Pozice: student
Reputace:   
 

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

↑ 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

 

#4 24. 11. 2016 18:06

check_drummer
Příspěvky: 3867
Reputace:   91 
 

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

↑ 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.


Ve 21. století i vzdělaní lidé učili své děti, že látka je tvořená z atomů.

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson