networkx.algorithms.asteroidal.find_asteroidal_triple¶
-
find_asteroidal_triple(G)[source]¶ Find an asteroidal triple in the given graph.
An asteroidal triple is a triple of non-adjacent vertices such that there exists a path between any two of them which avoids the closed neighborhood of the third. It checks all independent triples of vertices and whether they are an asteroidal triple or not. This is done with the help of a data structure called a component structure. A component structure encodes information about which vertices belongs to the same connected component when the closed neighborhood of a given vertex is removed from the graph. The algorithm used to check is the trivial one, outlined in 1, which has a runtime of \(O(|V||\overline{E} + |V||E|)\), where the second term is the creation of the component structure.
- Parameters
G (NetworkX Graph) – The graph to check whether is AT-free or not
- Returns
An asteroidal triple is returned as a list of nodes. If no asteroidal triple exists, i.e. the graph is AT-free, then None is returned. The returned value depends on the certificate parameter. The default option is a bool which is True if the graph is AT-free, i.e. the given graph contains no asteroidal triples, and False otherwise, i.e. if the graph contains at least one asteroidal triple.
- Return type
Notes
The component structure and the algorithm is described in 1. The current implementation implements the trivial algorithm for simple graphs.
References
- 1(1,2)
Ekkehard Köhler, “Recognizing Graphs without asteroidal triples”, Journal of Discrete Algorithms 2, pages 439-452, 2004. https://www.sciencedirect.com/science/article/pii/S157086670400019X