Absztrakt

A kritikus infrastruktúrák hálózatokat alkotnak, legyen szó akár vasúthálózatról, úthálózatról, elektromos hálózatról, vagy informatikai hálózatról. Ezen hálózatok matematikai elemzése gráfelméleti módszerek segítségével történhet. Kritikus infrastruktúrákkal szemben természetes elvárás lehet, hogy egy (vagy esetleg néhány) infrastruktúra elem meghibásodása esetén az infrastruktúra összefüggő maradjon, azaz lehetőség szerint ne jöjjenek létre egymástól elválasztott komponensek a hálózatban. Ezen hibatűrő képesség gráfelméleti megfelelője a többszörös összefüggőség, melynek kiszámítására ismertek hatékony algoritmusok. Fontos kérdés, hogy ha egy kritikus infrastruktúra nem teljesít bizonyos gráfelméleti megbízhatósággal kapcsolatos követelményeket, akkor hogyan lehet a lehető legkisebb költséggel kibővíteni az infrastruktúrát oly módon, hogy ezen követelményeknek eleget tegyen. A cikk kutatásaihoz az Új Széchenyi Terv keretein belül az EFOP-3.6.2-16-2017-00016 számú projekt biztosított forrást. A kutatás az Európai Unió támogatásával, az Európai Szociális Alap társfinanszírozásával valósult meg.

Critical infrastructures form networks, including railway networks, road networks, electronic networks, or computer networks. Mathematical analysis of these networks is often done with graph theory. We can set up a natural requirement regarding to critical infrastructures, namely, even if some failures occur in the infrastructure, and some component become unreachable for a while, the infrastructure itself has to remain connected, i.e. we have to avoid separated components in the infrastructure. This fault tolerance capability is called multiple connectivity in graph theory. Given a critical infrastructure, we can ask the following important question. If the infrastructure does not satisfy some robustness requirements, then what is the minimal cost of the completion of the infrastructure, such that it becomes robust enough to satisfy these requirements. The research presented in this paper was carried out as part of the EFOP-3.6.2-16-2017-00016 project in the framework of the New Széchenyi Plan. The completion of this project is funded by the European Union and co-financed by the European Social Fund.

Kulcsszavak: kritikus infrastruktúrák, gráfelmélet ~ critical infrastructures, graph theory