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 G = (V, E) be a simple graph and let K consist of all 2-element subsets of V. Then 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. Several graph-theoretic concepts are related to each other via complementation: The complement of an edgeless graph is a complete graph and vice versa. Any induced subgraph of the complement graph of a graph G is the complement of the corresponding induced subgraph in G. An independent set in a graph is a clique in the complement graph and vice versa. This is a special case of the previous two properties, as an independent set is an edgeless induced subgraph and a clique is a complete induced subgraph.

À 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.
Cours associés (21)
EE-619: Advanced topics in network neuroscience
The main goal of this course is to give the student a solid introduction into approaches, methods, and tools for brain network analysis. The student will learn about principles of network science and
PHYS-512: Statistical physics of computation
The students understand tools from the statistical physics of disordered systems, and apply them to study computational and statistical problems in graph theory, discrete optimisation, inference and m
CS-250: Algorithms I
The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma
Afficher plus
Séances de cours associées (68)
Contrefaits: SEM et D-Separation
Explore les contre-factuals dans les SEM et D-Separation dans les modèles graphiques.
Modèle de bloc stochastique: Détection communautaire
Couvre le modèle de bloc stochastique pour la détection de la communauté, en se concentrant sur la détection des communautés, des clusters et des groupes.
Modèle de bloc stochastique: Détection communautaire
Couvre le modèle de bloc stochastique pour la détection communautaire.
Afficher plus
Publications associées (85)

High-Throughput and Flexible Belief Propagation List Decoder for Polar Codes

Andreas Peter Burg, Alexios Konstantinos Balatsoukas Stimming, Andreas Toftegaard Kristensen, Yifei Shen, Yuqing Ren, Chuan Zhang

Due to its high parallelism, belief propagation (BP)decoding is amenable to high-throughput applications and thusrepresents a promising solution for the ultra-high peak datarate required by future communication systems. To bridge theperformance gap compare ...
Ieee-Inst Electrical Electronics Engineers Inc2024

Graph generative deep learning models with an application to circuit topologies

Igor Krawczuk

Modern integrated circuits are tiny yet incredibly complex technological artifacts, composed of millions and billions of individual structures working in unison.Managing their complexity and facilitating their design drove part of the co-evolution of moder ...
EPFL2024

The connection of the acyclic disconnection and feedback arc sets - On an open problem of Figueroa et al.

Lukas Fritz Felix Vogl

We examine the connection of two graph parameters, the size of a minimum feedback arcs set and the acyclic disconnection. A feedback arc set of a directed graph is a subset of arcs such that after deletion the graph becomes acyclic. The acyclic disconnecti ...
Elsevier2024
Afficher plus
Concepts associés (38)
Induced subgraph
In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and all of the edges (from the original graph) connecting pairs of vertices in that subset. Formally, let be any graph, and let be any subset of vertices of G. Then the induced subgraph is the graph whose vertex set is and whose edge set consists of all of the edges in that have both endpoints in . That is, for any two vertices , and are adjacent in if and only if they are adjacent in .
Voisinage (théorie des graphes)
En théorie des graphes on dit que deux sommets d'un graphe non-orienté sont voisins ou adjacents s'ils sont reliés par une arête. Le voisinage d'un sommet peut désigner l'ensemble de ses sommets voisins ou bien un sous-graphe associé, par exemple le sous-graphe induit. Dans un graphe orienté, on emploie généralement le terme de prédécesseur ou de successeur. Dans un graphe non orienté , le voisinage d'un sommet , souvent noté (N pour neighbourhood) peut désigner plusieurs choses : L'ensemble des sommets voisins : Les sous-graphe de induit par les sommets précédents, avec ou sans selon les versions.
Graphe cycle
Les graphes cycles, ou n-cycles, forment une famille de graphes. Le graphe cycle est constitué d'un unique cycle élémentaire de longueur n (pour ). C'est un graphe connexe non-orienté d'ordre n à n arêtes. Il est 2-régulier, c'est-à-dire que chacun de ses sommets est de degré 2. Beaucoup de termes sont employés pour désigner le graphe cycle : n-cycle, polygone et n-gone. Le terme de graphe cyclique est parfois employé, mais il pose problème car il s'oppose normalement à graphe acyclique. Nombre chromatique.
Afficher plus

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.