Ê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 GraphSearch.
Concept
Produit fort (graphe)
Résumé
In graph theory, the strong product is a way of combining two graphs to make a larger graph. Two vertices are adjacent in the strong product when they come from pairs of vertices in the factor graphs that are either adjacent or identical. The strong product is one of several different graph product operations that have been studied in graph theory. The strong product of any two graphs can be constructed as the union of two other products of the same two graphs, the Cartesian product of graphs and the tensor product of graphs.
An example of a strong product is the king's graph, the graph of moves of a chess king on a chessboard, which can be constructed as a strong product of path graphs. Decompositions of planar graphs and related graph classes into strong products have been used as a central tool to prove many other results about these graphs.
Care should be exercised when encountering the term strong product in the literature, since it has also been used to denote the tensor product of graphs.
The strong product G ⊠ H of graphs G and H is a graph such that
the vertex set of G ⊠ H is the Cartesian product V(G) × V(H); and
distinct vertices (u,u' ) and (v,v' ) are adjacent in G ⊠ H if and only if:
u = v and u' is adjacent to v', or
u' = v' and u is adjacent to v, or
u is adjacent to v and u' is adjacent to v'.
It is the union of the Cartesian product and the tensor product.
For example, the king's graph, a graph whose vertices are squares of a chessboard and whose edges represent possible moves of a chess king, is a strong product of two path graphs. Its horizontal edges come from the Cartesian product, and its diagonal edges come from the tensor product of the same two paths. Together, these two kinds of edges make up the entire strong product.
Every planar graph is a subgraph of a strong product of a path and a graph of treewidth at most six. This result has been used to prove that planar graphs have bounded queue number, small universal graphs and concise adjacency labeling schemes, and bounded nonrepetitive chromatic number and centered chromatic number.
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.