Abstract

W niniejszej pracy przeprowadzono analizę złożoności istnienia struktur defensywnych oraz równowag strategicznych w grafach. W przypadku struktur defensywnych badano modele koalicji defensywnych, zbiorów defensywnych i koalicji krawędziowych – każdy z nich w wersji globalnej, tj. z wymogiem dominacji całego grafu. W przypadku modeli równowagi strategicznej badano równowagę strategiczną koalicji defensywnych, równowagę strategiczną zbiorów defensywnych i równowagę strategiczną koalicji krawędziowych. Przedstawiono wielomianowe algorytmy konstruujące najmniejsze struktury defensywne oraz weryfikujące ich istnienie i konstruujące równowagi strategiczne w przypadku drzew. Dodatkowo zweryfikowano trudność obliczeniową badanych problemów poprzez wykazanie ich NP–zupełności dla możliwie wąskich klas grafów. W ten sposób określono zakres stosowalności modeli w przypadku dużych grafów, a dalsze badania skierowano w kierunku podejść aproksymacyjnych, które poszerzą zakres zastosowań dyskutowanych modeli w praktyce. Przebadano również własności teoretyczne modeli, takie jak oszacowania rozmiaru badanych struktur i związki między nimi. Zaproponowano także ogólną koncepcję stanowiącą wspólny trzon dla dyskutowanych modeli, otwierając tym samym kierunki badań w obrębie tego zagadnienia.

Author (1)