A kommunikációs gráfok és a fekete-fehér SAT probléma közti összefüggések vizsgálata

Rajna, Franciska (2021) A kommunikációs gráfok és a fekete-fehér SAT probléma közti összefüggések vizsgálata. In: Agria Média 2020. Eszterházy Károly Egyetem Líceum Kiadó, Eger, pp. 321-330.

Preview

Text 321_330_Rajna.pdf - Published Version Download (1MB) | Preview

Abstract

Ebben a cikkben a kommunikációs gráfok és a fekete-fehér SAT probléma közötti összefüggéseket vizsgálom. A kommunikációs gráfok olyan speciális hurokélmentes irányított gráfok, amelyeknek csúcsai logikai változók, az élei pedig a kommunikációt reprezentálják. Ilyen típusú gráfokkal lehet többek között vezeték nélküli szenzorhálózatokat is modellezni. A cikkben bemutatom a fekete-fehér SAT problémát. A fekete-fehér SAT problémák olyan logikai formulák, amelyek majdnem kielégíthetetlenek, csak két megoldásuk van, az úgynevezett fehér hozzárendelés, ahol minden változó igaz, és a fekete hozzárendelés, amelyben minden változó hamis. A fekete-fehér SAT problémák ekvivalensek az olyan konjunktív normálformában lévő logikai formulákkal, amelyekben minden klózban pozitív és negatív literálok vegyesen szerepelnek (például ilyen 3SAT klózok a -++, --+), de sem a fehér klóz, amelyben minden literál pozitív, sem a fekete klóz, amelyben minden literál negatív, nem vezethető le. Továbbá ismertetem, és hatékonyság szempontjából elemzem a kommunikációs gráfok különböző logikai modelljeit (Erős modell, Balatonboglár modell, Egyszerűsített BB modell, Gyenge modell). ----- Investigation of the relationship between communication graphs and the black and white sat ----- In this article, I examine the relationships between communication graphs and the black-andwhite SAT problem. Communication graphs are special loop-free directed graphs whose vertices are logical variables and whose edges represent communication. These types of graphs can be used to model wireless sensor networks (WSNs), among other things. I present the black-and-white SAT problem. Black-and-white SAT problems are logical formulas that are almost unsatisfiable, they have only two solutions, the so-called white assignment, where all variables are true, and the black assignment, in which all variables are false. Black-and-white SAT problems are equivalent to logical formulas in a conjunctive normal form in which positive and negative literals are mixed in each clause (e.g., such 3-SAT clauses are - ++, - +), but not the white clause in which all literals are positive, nor the black clause in which all literals are negative cannot be deduced. I also describe and analyze the different logical models of communication graphs (Strong model, Balatonboglár model, Simplified BB model, Weak model) in terms of efficiency.

Actions (login required)

Edit Item