Application of selected methods of graph theory and combinatorial heuristics to minimising the number of transits nodes in an air network

Abstract

In the paper we present the notion of alpha-clique and some of its properties. Covering with alpha-cliques is a preprocessing method for an air network, described as a graph, in which vertices correspond to airports and edges correspond to air connections. Using the alpha-clique cover we obtain a hypergraph, in which we find the minimum transversal. The set of vertices thus obtained is the sought-for set of transits nodes, called hubs. Using the alpha-clique concept instead of proper cliques we can obtain the solution to the graph covering problem easier.

W niniejszej pracy prezentujemy pojęcie alfa-kliki i pewne jej własności. Znalezienie pokrycia alfa-klikami traktujemy jako metodę preprocessingu dla sieci lotniczych opisanych jako graf, w którym węzły odpowiadają lotniskom, a krawędzie odpowiadają połączeniom lotniczym. Znajdując pokrycie alfa-klikami, uzyskujemy hipergraf, dla którego otrzymujemy minimalną transwersalę. W ten sposób uzyskujemy zbiór wierzchołków będących węzłami tranzytowymi czyli hubami. Stosując alfa-kliki zamiast odpowiednich klik, możemy uzyskać lepsze pokrycie grafu.