Concept

Homéomorphisme de graphes

En théorie des graphes, une branche des mathématiques, deux graphes et sont homéomorphes si l'on peut obtenir un même graphe en subdivisant certaines de leurs arêtes. Deux graphes sont homéomorphes si et seulement si leurs représentations graphiques usuelles (avec des segments de droites reliant les sommets entre eux) sont homéomorphes au sens que ce mot a en topologie. Subdivision La subdivision d'une arête conduit à un graphe contenant un nouveau sommet et où l'on a remplacé l'arête par deux nouvelles arêtes, et . Image:Graph subdivision step1.svg|Avant subdivision Image:Graph subdivision step2.svg|Après subdivision Une subdivision d'un graphe (parfois appelée expansion de graphe) est le graphe résultant de la subdivision d'arêtes de . Lissage L'opération inverse, le lissage (smoothing en anglais) d'un sommet par rapport aux arêtes et arrivant en consiste à supprimer et à remplacer et par . Image:Graph subdivision step2.svg|Avant lissage Image:Graph subdivision step1.svg|Après lissage Seuls les sommets de degré 2 peuvent être lissés. Subdivision barycentrique La subdivision barycentrique subdivise toutes les arêtes du graphe. Ce cas particulier de subdivision donne toujours un graphe biparti. Homéomorphisme Deux graphes et sont homéomorphes s'il existe un isomorphisme entre une certaine subdivision de et une certaine subdivision de . Image:Graph homeomorphism example 1.svg|Graphe G Image:Graph homeomorphism example 2.svg|Graphe H Image:Graph homeomorphism example 3.svg|G' et H', subdivisions de G et de H Déterminer si un sous-graphe d'un graphe donné est homéomorphe à un graphe donné est un problème NP-complet. Il est évident que la subdivision préserve le fait d'être planaire pour un graphe. Le théorème de Kuratowski affirme : De fait, un graphe homéomorphe à ou à est appelé un sous-graphe de Kuratowski. Une généralisation qui découle du théorème de Robertson-Seymour affirme que pour tout nombre entier , il y a un ensemble de graphes « interdits » tels qu'un graphe peut être plongé dans une surface de genre si et seulement si ne contient pas de copie homéomorphe à l'un des graphes .

Source officielle

https://fr.wikipedia.org/wiki/Homéomorphisme_de_graphes

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

Séances de cours associées (7)

Connectivité dans la théorie des graphiques

Couvre les fondamentaux de la connectivité dans la théorie des graphiques, y compris les chemins, les cycles et les arbres qui s'étendent.

Progrès récents dans le modèle Dimer et ses applications

Couvre les progrès récents dans le modèle de dimère, en mettant laccent sur ses applications dans la probabilité et la théorie des champs conforme.

Conception de l'objectif: Mise en œuvre des filtres et fonctionnalité de l'objectif

Explore la conception de l'objectif, les filtres passe-haut et la détection de ligne d'image à l'aide de MATLAB.

Afficher plus

Publications associées (14)

Small-world scale-free brain networks from EEG with application to motor imagery decoding and brain fingerprinting

Developing individualized spatial models that capture the complex dynamics of multi-electrode EEG data is essential for accurately decoding global neural activity. A widely used approach is network modeling, where electrodes are represented as nodes. A key challenge lies in defining the network edges and weights, as precise connectivity estimation is critical for enhancing neural characterization and extracting discriminative features, such as those needed for task decoding. Traditional EEG-derived brain gr

2026

Combinatorial Structures

Dominique de Werra

Mathematical models based on theoretical graph concepts help to formulate and solve fundamental scheduling problems. In this chapter, we consider some elementary sports scheduling problems and concentrate on the combinatorial structures involved in their models and solution approaches.

Springer Nature2023

Extrapolating Paths with Graph Neural Networks

Andreas Loukas, Jean-Baptiste Francis Marie Juliette Cordonnier

We consider the problem of path inference: given a path prefix, i.e., a partially observed sequence of nodes in a graph, we want to predict which nodes are in the missing suffix. In particular, we focus on natural paths occurring as a by-product of the int ...

IJCAI, Inc.2019

Afficher plus

Notebooks associés (1)

Modeling Epidemics with Signal Processing Techniques

Epidemics and Signal Processing[1]¶

                                      [2]Paolo Prandoni, [3]LCAV, EPFL

In [1]: import matplotlib.pyplot as plt import numpy as np import scipy.signal as sp import seaborn as sns sns.set() In [2]: plt.rcParams["figure.figsize"] = (14,4) The basic reproduction number[4]¶ The propagation mechanism of an epidemic such as the one caused by SARS-CoV-2 virus can be roughly modeled, at least in its inital phase, as a process in which each infected individ

Graph Chat

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.

Source officielle

https://fr.wikipedia.org/wiki/Homéomorphisme_de_graphes

À propos de ce résultat

Séances de cours associées (7)

Connectivité dans la théorie des graphiques

Couvre les fondamentaux de la connectivité dans la théorie des graphiques, y compris les chemins, les cycles et les arbres qui s'étendent.

Progrès récents dans le modèle Dimer et ses applications

Couvre les progrès récents dans le modèle de dimère, en mettant laccent sur ses applications dans la probabilité et la théorie des champs conforme.

Conception de l'objectif: Mise en œuvre des filtres et fonctionnalité de l'objectif

Explore la conception de l'objectif, les filtres passe-haut et la détection de ligne d'image à l'aide de MATLAB.

Afficher plus

Publications associées (14)

Small-world scale-free brain networks from EEG with application to motor imagery decoding and brain fingerprinting

2026

Combinatorial Structures

Dominique de Werra

Springer Nature2023

Extrapolating Paths with Graph Neural Networks

Andreas Loukas, Jean-Baptiste Francis Marie Juliette Cordonnier

IJCAI, Inc.2019

Afficher plus

Personnes associées (3)

Paolo Ienne

Paolo Ienne has been a Professor at the EPFL since 2000 and heads the Processor Architecture Laboratory (LAP). Prior to that, he worked for the Semiconductors Group of Siemens AG, Munich, Germany (which later became Infineon Technologies AG) where he was at the head of the Embedded Memories unit in the Design Libraries division. His research interests include various aspects of computer and processor architecture, FPGAs and reconfigurable computing, electronic design automation, and computer arithmetic. Ienne was a recipient of Best Paper Awards at the 20th, 24th, and 28th ACM/SIGDA International Symposia on Field-Programmable Gate Arrays (FPGA), in 2012, 2016 and 2020, at the 19th and 30th International Conference on Field-Programmable Logic and Applications (FPL), in 2009 and 2020, at the International Conference on Compilers, Architectures, and Synthesis for Embedded Systems (CASES), in 2007, and at the 40th Design Automation Conference (DAC), in 2003; many other papers have been candidates to Best Paper Awards in prestigious venues. He has served as general, programme, and topic chair of renown international conferences, including organizing in Lausanne the 26th International Conference on Field-Programmable Logic and Applications (FPL) in 2016. He serves on the steering committee of the IEEE Symposium on Computer Arithmetic (ARITH) and of the International Conference on Field-Programmable Logic and Applications (FPL). Ienne has guest edited a number of special issues and special sections on various topics for IEEE and ACM journals. He is regularly member of program committees of international workshops and conferences in the areas of design automation, computer architecture, embedded systems, compilers, FPGAs, and asynchronous design. He has been an associate editor of ACM Transactions on Architecture and Code Optimization (TACO), since 2015, of ACM Computing Surveys (CSUR), since 2014, and of ACM Transactions on Design Automation of Electronic Systems (TODAES) from 2011 to 2016.

Pierre Vandergheynst

Pierre Vandergheynst received the M.S. degree in physics and the Ph.D. degree in mathematical physics from the Université catholique de Louvain, Louvain-la-Neuve, Belgium, in 1995 and 1998, respectively. From 1998 to 2001, he was a Postdoctoral Researcher with the Signal Processing Laboratory, Swiss Federal Institute of Technology (EPFL), Lausanne, Switzerland. He was Assistant Professor at EPFL (2002-2007), where he is now a Full Professor of Electrical Engineering and, by courtesy, of Computer and Communication Sciences. As of 2015, Prof. Vandergheynst serves as EPFL’s Vice-Provost for Education. His research focuses on harmonic analysis, sparse approximations and mathematical data processing in general with applications covering signal, image and high dimensional data processing, computer vision, machine learning, data science and graph-based data processing. He was co-Editor-in-Chief of Signal Processing (2002-2006), Associate Editor of the IEEE Transactions on Signal Processing (2007-2011), the flagship journal of the signal processing community and currently serves as Associate Editor of Computer Vision and Image Understanding and SIAM Imaging Sciences. He has been on the Technical Committee of various conferences, serves on the steering committee of the SPARS workshop and was co-General Chairman of the EUSIPCO 2008 conference. Pierre Vandergheynst is the author or co-author of more than 70 journal papers, one monograph and several book chapters. He has received two IEEE best paper awards. Professor Vandergheynst is a laureate of the Apple 2007 ARTS award and of the 2009-2010 De Boelpaepe prize of the Royal Academy of Sciences of Belgium.

Wulfram Gerstner

Wulfram Gerstner is Director of the Laboratory of Computational Neuroscience LCN at the EPFL. His research in computational neuroscience concentrates on models of spiking neurons and spike-timing dependent plasticity, on the problem of neuronal coding in single neurons and populations, as well as on the link between biologically plausible learning rules and behavioral manifestations of learning. He teaches courses for Physicists, Computer Scientists, Mathematicians, and Life Scientists at the EPFL. After studies of Physics in Tübingen and at the Ludwig-Maximilians-University Munich (Master 1989), Wulfram Gerstner spent a year as a visiting researcher in Berkeley. He received his PhD in theoretical physics from the Technical University Munich in 1993 with a thesis on associative memory and dynamics in networks of spiking neurons. After short postdoctoral stays at Brandeis University and the Technical University of Munich, he joined the EPFL in 1996 as assistant professor. Promoted to Associate Professor with tenure in February 2001, he is since August 2006 a full professor with double appointment in the School of Computer and Communication Sciences and the School of Life Sciences. Wulfram Gerstner has been invited speaker at numerous international conferences and workshops. He has served on the editorial board of the Journal of Neuroscience, Network: Computation in Neural Systems', Journal of Computational Neuroscience', and `Science'.

Concepts associés (11)

Mineur (théorie des graphes)

La notion de mineur d'un graphe est un concept de théorie des graphes. Il a été défini et étudié par Robertson et Seymour dans une série d'articles intitulée Graph minors (I à XXIII), publiée dans le Journal of Combinatorial Theory entre 1983 et 2011. Soit un graphe non orienté fini. Un graphe est un mineur de s'il peut être obtenu en contractant des arêtes d'un sous-graphe de .

Wagner's theorem

In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither K5 (the complete graph on five vertices) nor K3,3 (the utility graph, a complete bipartite graph on six vertices). This was one of the earliest results in the theory of graph minors and can be seen as a forerunner of the Robertson–Seymour theorem.

Forbidden graph characterization

In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidden graphs as (induced) subgraph or minor. A prototypical example of this phenomenon is Kuratowski's theorem, which states that a graph is planar (can be drawn without crossings in the plane) if and only if it does not contain either of two forbidden graphs, the complete graph K_5 and the complete bipartite graph K_3,3.

Afficher plus

Notebooks associés (1)

Modeling Epidemics with Signal Processing Techniques

Epidemics and Signal Processing[1]¶

                                      [2]Paolo Prandoni, [3]LCAV, EPFL

Personnes associées (3)

Paolo Ienne

Pierre Vandergheynst

Wulfram Gerstner