Invariant de graphe

In graph theory, a graph property or graph invariant is a property of graphs that depends only on the abstract structure, not on graph representations such as particular labellings or drawings of the graph. While graph drawing and graph representation are valid topics in graph theory, in order to focus only on the abstract structure of graphs, a graph property is defined to be a property preserved under all possible isomorphisms of a graph. In other words, it is a property of the graph itself, not of a specific drawing or representation of the graph. Informally, the term "graph invariant" is used for properties expressed quantitatively, while "property" usually refers to descriptive characterizations of graphs. For example, the statement "graph does not have vertices of degree 1" is a "property" while "the number of vertices of degree 1 in a graph" is an "invariant". More formally, a graph property is a class of graphs with the property that any two isomorphic graphs either both belong to the class, or both do not belong to it. Equivalently, a graph property may be formalized using the indicator function of the class, a function from graphs to Boolean values that is true for graphs in the class and false otherwise; again, any two isomorphic graphs must have the same function value as each other. A graph invariant or graph parameter may similarly be formalized as a function from graphs to a broader class of values, such as integers, real numbers, sequences of numbers, or polynomials, that again has the same value for any two isomorphic graphs. Many graph properties are well-behaved with respect to certain natural partial orders or preorders defined on graphs: A graph property P is hereditary if every induced subgraph of a graph with property P also has property P. For instance, being a perfect graph or being a chordal graph are hereditary properties. A graph property is monotone if every subgraph of a graph with property P also has property P. For instance, being a bipartite graph or being a triangle-free graph is monotone.

À 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.

Publications associées (2)

Concepts associés (34)

Cours associés (5)

Séances de cours associées (39)

Scalable Robust Graph Embedding with Spark

Karl Aberer, Quoc Viet Hung Nguyen, Chi Thang Duong, Trung-Dung Hoang

Graph embedding aims at learning a vector-based representation of vertices that incorporates the structure of the graph. This representation then enables inference of graph properties. Existing graph embedding techniques, however, do not scale well to large graphs. While several techniques to scale graph embedding using compute clusters have been proposed, they require continuous communication between the compute nodes and cannot handle node failure. We therefore propose a framework for scalable and robust graph embedding based on the MapReduce model, which can distribute any existing embedding technique. Our method splits a graph into subgraphs to learn their embeddings in isolation and subsequently reconciles the embedding spaces derived for the subgraphs. We realize this idea through a novel distributed graph decomposition algorithm. In addition, we show how to implement our framework in Spark to enable efficient learning of effective embeddings. Experimental results illustrate that our approach scales well, while largely maintaining the embedding quality.

ASSOC COMPUTING MACHINERY2021

Finite graphs and amenability

Gábor Elek

Hyperfiniteness or amenability of measurable equivalence relations and group actions has been studied for almost fifty years. Recently, unexpected applications of hyperfiniteness were found in computer science in the context of testability of graph properties. In this paper we propose a unified approach to hyperfiniteness. We establish some new results and give new proofs of theorems of Schramm, Lovasz, Newman Sohler and Ornstein-Weiss. (c) 2012 Elsevier Inc. All rights reserved.

Academic Press Inc Elsevier Science2012

PHYS-118: Building physics

Ce cours traite des principaux phénomènes physiques observables dans le bâtiment et doit permettre à l'étudiant d'acquérir des connaissances de base dans le domaine de la physique du bâtiment.

EE-626: Graph representations for biology and medicine

Systems of interacting entities, modeled as graphs, are pervasive in biology and medicine. The class will cover advanced topics in signal processing and machine learning on graphs and networks, and wi

MATH-302: Functional analysis I

Concepts de base de l'analyse fonctionnelle linéaire: opérateurs bornés, opérateurs compacts, théorie spectrale pour les opérateurs symétriques et compacts, le théorème de Hahn-Banach, les théorèmes d

Problème de l'isomorphisme de graphes

vignette|Le problème est de savoir si deux graphes sont les mêmes. En informatique théorique, le problème de l'isomorphisme de graphes est le problème de décision qui consiste, étant donné deux graphes non orientés, à décider s'ils sont isomorphes ou pas, c'est-à-dire s'ils sont les mêmes, quitte à renommer les sommets. Ce problème est particulièrement important en théorie de la complexité, plus particulièrement pour le problème P=NP.

Invariant de graphe

En théorie des graphes, un invariant de graphe est une quantité qui n'est pas modifiée par isomorphisme de graphes. Un invariant de graphe ne dépend donc que de la structure abstraite et pas des particularités de la représentation comme l'étiquetage ou le tracé. De nombreux invariants sont conservés par certains préordres ou ordres partiels naturels sur les graphes : Une propriété est monotone si elle est héritée par les sous-graphes. Le caractère biparti, sans triangle, ou planaire sont des exemples de propriétés monotones.

Théorie algébrique des graphes

vignette|Le graphe de Petersen, qui possède 10 sommets et 15 arêtes. Hautement symétrique, il est en particulier distance-transitif. Son groupe d'automorphisme a 120 éléments et est en fait le groupe symétrique S. De diamètre 2, il possède 3 valeurs propres. En mathématiques, la théorie algébrique des graphes utilise des méthodes algébriques pour résoudre des problèmes liés aux graphes, par opposition à des approches géométriques, combinatoires ou algorithmiques.

Estimation du modèle de bloc stochastique MATH-448: Statistical analysis of network data

Explore l'estimation stochastique du modèle de bloc, le regroupement spectral, la modularité du réseau, la matrice laplacienne et le regroupement des moyennes k.

Bases de programmation entières MATH-261: Discrete optimization

Introduit les bases de la programmation entière, y compris les programmes binaires entiers et les stratégies de contrainte.

Bases graphiques: MATLAB et Octave pour les débutants MOOC: Matlab et Octave pour débutants

Couvre les bases de la création de graphiques 2D à l'aide de MATLAB et Octave.