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. Eger, Eszterházy Károly Egyetem Líceum Kiadó. pp. 321-330.

pdf 321_330_Rajna.pdf Download (1MB) [error in script]

Absztrakt (kivonat)

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.

Mű típusa:	Könyvrészlet - Book section
Szerző:	Szerző neve Email MTMT azonosító ORCID azonosító Közreműködés Rajna, Franciska NEM RÉSZLETEZETT NEM RÉSZLETEZETT NEM RÉSZLETEZETT Szerző
Kapcsolódó URL-ek:	Befoglaló kötet
Kulcsszavak:	fekete-fehér SAT probléma, kommunikációs gráf, Erős modell, Gyenge modell, Balatonboglár modell, Egyszerűsített Balatonboglár modell ----- black-and-white SAT problem, communication graph, Strong model, Weak model, Balatonboglár model, Simplified Balatonboglár model
Nyelv:	magyar
DOI azonosító:	10.17048/AM.2020.321
ISBN:	978-963-496-199-4
Felhasználó:	Tibor Gál
Dátum:	02 Szep 2021 15:13
Utolsó módosítás:	02 Szep 2021 15:13
URI:	http://publikacio.uni-eszterhazy.hu/id/eprint/7056

Műveletek (bejelentkezés szükséges)

Tétel nézet