Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Bipartite double cover
Résumé
In graph theory, the bipartite double cover of an undirected graph G is a bipartite, covering graph of G, with twice as many vertices as G. It can be constructed as the tensor product of graphs, G × K_2. It is also called the Kronecker double cover, canonical double cover or simply the bipartite double of G.
It should not be confused with a cycle double cover of a graph, a family of cycles that includes each edge twice.
The bipartite double cover of G has two vertices u_i and w_i for each vertex v_i of G. Two vertices u_i and w_j are connected by an edge in the double cover if and only if v_i and v_j are connected by an edge in G. For instance, below is an illustration of a bipartite double cover of a non-bipartite graph G. In the illustration, each vertex in the tensor product is shown using a color from the first term of the product (G) and a shape from the second term of the product (K_2); therefore, the vertices u_i in the double cover are shown as circles while the vertices w_i are shown as squares.
The bipartite double cover may also be constructed using adjacency matrices (as described below) or as the derived graph of a voltage graph in which each edge of G is labeled by the nonzero element of the two-element group.
The bipartite double cover of the Petersen graph is the Desargues graph: K_2 × G(5,2) = G(10,3).
The bipartite double cover of a complete graph K_n is a crown graph (a complete bipartite graph K_n,n minus a perfect matching). In particular, the bipartite double cover of the graph of a tetrahedron, K_4, is the graph of a cube.
The bipartite double cover of an odd-length cycle graph is a cycle of twice the length, while the bipartite double of any bipartite graph (such as an even length cycle, shown in the following example) is formed by two disjoint copies of the original graph.
If an undirected graph G has a matrix A as its adjacency matrix, then the adjacency matrix of the double cover of G is
and the biadjacency matrix of the double cover of G is just A itself.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.