Графтың қарама-қарсы байланыстары

Graph with same nodes but opposite connections as another

In the mathematical field of graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two distinct vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and removes all the edges that were previously there. The complement is not the set complement of the graph; only the edges are complemented.

Let 1=G = (V, E) be a simple graph and let K consist of all 2 element subsets of V. Then 1=H = (V, K \ E) is the complement of G, where K \ E is the relative complement of E in K. For directed graphs, the complement can be defined in the same way, as a directed graph on the same vertex set, using the set of all 2 element ordered pairs of V in place of the set K in the formula above. In terms of the adjacency matrix A of the graph, if Q is the adjacency matrix of the complete graph of the same number of vertices (i. e. all entries are unity except the diagonal entries which are zero), then the adjacency matrix of the complement of A is Q A. The complement is not defined for multigraphs. In graphs that allow self loops (but not multiple adjacencies) the complement of G may be defined by adding a self loop to every vertex that does not have one in G, and otherwise using the same formula as above. This operation is, however, different from the one for simple graphs, since applying it to a graph with no self loops would result in a graph with self loops on all vertices.

A self complementary graph is a graph that is isomorphic to its own complement. Cographs are defined as the graphs that can be built up from single vertices by disjoint union and complementation operations. They form a self complementary family of graphs: the complement of any cograph is another different cograph. For cographs of more than one vertex, exactly one graph in each complementary pair is connected, and one equivalent definition of cographs is that each of their connected induced subgraphs has a disconnected complement. Another, self complementary definition is that they are the graphs with no induced subgraph in the form of a four vertex path. Another self complementary class of graphs is the class of split graphs, the graphs in which the vertices can be partitioned into a clique and an independent set. The same partition gives an independent set and a clique in the complement graph. The threshold graphs are the graphs formed by repeatedly adding either an independent vertex (one with no neighbors) or a universal vertex (adjacent to all previously added vertices). These two operations are complementary and they generate a self complementary class of graphs.

In the analysis of algorithms on graphs, the distinction between a graph and its complement is an important one, because a sparse graph (one with a small number of edges compared to the number of pairs of vertices) will in general not have a sparse complement, and so an algorithm that takes time proportional to the number of edges on a given graph may take a much larger amount of time if the same algorithm is run on an explicit representation of the complement graph. Therefore, researchers have studied algorithms that perform standard graph computations on the complement of an input graph, using an implicit graph representation that does not require the explicit construction of the complement graph. In particular, it is possible to simulate either depth first search or breadth first search on the complement graph, in an amount of time that is linear in the size of the given graph, even when the complement graph may have a much larger size.