Ê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
Graphe d'intersection
Résumé
In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types of sets that are used to form an intersection representation of them.
Formally, an intersection graph G is an undirected graph formed from a family of sets
by creating one vertex v_i for each set S_i, and connecting two vertices v_i and v_j by an edge whenever the corresponding two sets have a nonempty intersection, that is,
Any undirected graph G may be represented as an intersection graph. For each vertex vi of G, form a set Si consisting of the edges incident to vi; then two such sets have a nonempty intersection if and only if the corresponding vertices share an edge. Therefore, G is the intersection graph of the sets Si.
provide a construction that is more efficient, in the sense that it requires a smaller total number of elements in all of the sets Si combined. For it, the total number of set elements is at most n2/4, where n is the number of vertices in the graph. They credit the observation that all graphs are intersection graphs to , but say to see also . The intersection number of a graph is the minimum total number of elements in any intersection representation of the graph.
Many important graph families can be described as intersection graphs of more restricted types of set families, for instance sets derived from some kind of geometric configuration:
An interval graph is defined as the intersection graph of intervals on the real line, or of connected subgraphs of a path graph.
An indifference graph may be defined as the intersection graph of unit intervals on the real line
A circular arc graph is defined as the intersection graph of arcs on a circle.
A polygon-circle graph is defined as the intersection of polygons with corners on a circle.
One characterization of a chordal graph is as the intersection graph of connected subgraphs of a tree.
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.