W pracy rozważany jest problem defensywnej równowagi strategicznej dla zbiorów defensywnych w drzewach (spójnych grafach acyklicznych), który polega na znalezieniu dwóch rozłącznych globalnych zbiorów defensywnych. Zagadnienie to znajduje zastosowanie w modelo- waniu problemów komunikacyjnych w sieciach. Dla danego grafu G podzbiór jego wierzchołków S jest zbiorem defensywnym, jeśli dla każdego wierzchołka v należącego do S spełniony jest warunek koalicyjny, tzn. w jego domkniętym sąsiedztwie jest co najmniej tyle samo wierzchołków z S co spoza S lub istnieje wierzchołek u sąsiedni do v taki, że w domkniętym sąsiedztwie krawędzi {v, u} jest co najmniej tyle samo wierzchołków z S co spoza S. W pracy pokazana została równoważność między problemami równowagi strategicznej oraz doskonałej równowagi strategicznej dla zbiorów defensywnych w drzewach oraz przedstawiony został wielomianowy algorytm rozwiązujący problem równowagi strategicznej dla zbiorów defensywnych w drzewach
Authors
Additional information
- Category
- Publikacja monograficzna
- Type
- rozdział, artykuł w książce - dziele zbiorowym /podręczniku o zasięgu krajowym
- Language
- polski
- Publication year
- 2017
