Bezpieczeństwo w grafach

• Autorzy: Jesse-Józefczyk K.

Warianty tytułu

EN

Security in graphs

• Języki publikacji: PL

Abstrakty

PL

P. Kristiansen, TW. Hedetniemi i S.T. Hedetniemi jako pierwsi zdefiniowali pojęcie koalicji w grafie. I tak mówimy, że zbiór SV jest koalicją, jeżeli dla każdego wierzchołka x E S zachodzi |N[x] (\ S|]N (x) -S|. W tym modelu wierzchołki graf u mogą oznaczać, np. kraje, firmy, ludzi. Krawędzie natomiast odnoszą się zarówno do możliwości zaatakowania wierzchołka sąsiedniego jak i jego obrony. Co ważne, w tym samym czasie zaatakowany może zostać tylko jeden członek koalicji. Jest to wadą tego podejścia, gdyż w rzeczywistym świecie najczęściej zdarza się, że atakowana jest cała koalicja lub przynajmniej kilku jej członków. Dlatego też Brigham, Dutton i Hedetniemi przedstawili ostatnio pojęcie bezpiecznego zbioru. Mianowicie mówimy, że zbiór S V jest bezpieczny, jeżeli atak na dowolny podzbiór zbioru S może zostać obroniony co jest równoznaczne z tym, że dla każdego zbioru X S zachodzi IN[ X] (\ S| _ |N[ X]-S|.

EN

P. Kristiansen, T.W. Hedetniemi and S.T. Hedetniemi first introduced a concept of an alliance in a graph. We say that a set S V is an alliance, if for every vertex x E S |N[x]S| |N(x)-S|. In this model the vertices of a graph can represent e.g. countries, companies, people, where the edges mean the possibility of attacking as well as defending the neighbour. So we can consider as the defenders all the vertices which belong to the alliance and as the attackers all the other vertices. What is important in the same time only one member of the alliance can be attacked. This is a drawback of this concept, because in reality most often the who le alliance or at least several of its members are attacked in the same time. That is why Brigham, Dutton and Hedetniemi defined the concept of secure sets. We say that a set S V is secure, if for every set X S;;; S |N[ X] S| |N[X] - S|.

Słowa kluczowe

PL

grafy; bezpieczeństwo

• Wydawca: Wydział Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej
• Czasopismo: Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
• Rocznik: 2008
• Tom: T. 16
• Strony: 409--414
• Opis fizyczny: Bibliogr. 6 poz., rys.

Twórcy

autor

Jesse-Józefczyk K.

• Uniwersytet Zielonogórski, Zakład Matematyki Dyskretnej i Informatyki Teoretycznej

Bibliografia

• [1] Haynes T.W., Hedetniemi S.T., Henning M.A: Global defensive alliances in graphs, The Electronic Journal of Combinatorics 10 1 2003, R47.
• [2] Langley L.J.: Alliances in directed graphs, JCMCC 61 2007, s. 149-158.
• [3] Kristiansen P., Hedetniemi AM., Hedetniemi S.T.: Alliances in graphs, JCMCC 48 2004, s.157-177.
• [4] Cami A, Balakrishnan H., Deo N., Dutton R.D.: On the complexity of finding optimal global alliances, JCMCC 58 2006, s. 23-31.
• [5] Flake G.W, Lawrence S., Giles C.L.: Efficient Identification of Web Communities, Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining 2000, s. 150-160.
• [6] Brigham R.C., Dutton R.D., Hedetniemi S.T.: Security in graphs, Discrete Applied Mathematics 155 2007, s. 1708-1714.