Concept

Line graph

En théorie des graphes, le line graph L(G) d'un graphe non orienté G, est un graphe qui représente la relation d'adjacence entre les arêtes de G. Le nom line graph vient d'un article de Harary et Norman publié en 1960. La même construction avait cependant déjà été utilisée par Whitney en 1932 et Krausz en 1943. Il est également appelé graphe adjoint. Un des premiers et des plus importants théorèmes sur les line graphs est énoncé par Hassler Whitney en 1932, qui prouve qu'en dehors d'un unique cas exceptionnel, la structure de G peut être entièrement retrouvée à partir de L(G) dans le cas des graphes connexes. Étant donné un graphe G, son line graph L(G) est le graphe défini de la façon suivante : Chaque sommet de L(G) représente une arête de G; Deux sommets de L(G) sont adjacents si et seulement si les arêtes correspondantes partagent une extrémité commune dans G (on dit alors qu'elles sont adjacentes). La figure suivante illustre un graphe (à gauche, avec des sommets bleus) et son line graph (à droite, avec des sommets verts). Chaque sommet du line graph est étiqueté avec les extrémités de l'arête correspondante dans le graphe d'origine. File:Line graph construction 1.svg|Graphe ''G'' File:Line graph construction 2.svg|Sommets de ''L''(''G'') construits à partir des arêtes de ''G'' File:Line graph construction 3.svg|Ajout des arêtes de ''L''(''G'') File:Line graph construction 4.svg|Le ''line graph'' ''L''(''G'') Le graphe de Petersen est le graphe complémentaire du line graph du graphe complet . Le line graph du graphe tétraédrique est le graphe octaédrique. Le line graph du graphe hexaédrique est le graphe cuboctaédrique. Le line graph du graphe dodécaédrique est le graphe icosaédrique. Les propriétés d'un graphe G dépendant uniquement de l'adjacence entre arêtes peuvent être traduites sur L(G) en propriétés équivalentes dépendant de l'adjacence entre sommets. Par exemple, un couplage dans G, c'est-à-dire un ensemble d'arêtes qui n'ont pas de sommet en commun, correspond à un ensemble de sommets deux à deux non adjacents dans L(G), donc à un stable de L(G).

Source officielle

https://fr.wikipedia.org/wiki/Line_graph

À 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 (32)

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 machine learning. ...

MATH-448: Statistical analysis of network data

A first course in statistical network analysis and applications. ...

ME-427: Networked control systems

This course offers an introduction to control systems using communication networks for interfacing sensors, actuators, controllers, and processes. Challenges due to network non-idealities and opportunities offered by communication will be analyzed. ...

Afficher plus

Séances de cours associées (32)

Renormalisation : AQFT

Couvre le concept de renormalisation dans la théorie des champs quantiques algébriques.

Algèbre linéaire : Diagonalisation

Explore la diagonalisation des matrices et les conditions de diagonalisation exacte, avec des exemples démontrant le processus.

Algèbre linéaire: base canonique

Explore la base canonique en algèbre linéaire, en se concentrant sur la représentation matricielle, la diagonalisation et les polynômes caractéristiques.

Afficher plus

Unités associées (22)

Laboratoire transport et mobilité

Laboratoire de traitement des signaux 4

SNAI - Gestion

Afficher plus

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/Line_graph

À propos de ce résultat

Proximité ontologique

Mathématiques

Mathématiques discrètes: Théorie des graphes

Cours associés (32)

PHYS-512: Statistical physics of computation

MATH-448: Statistical analysis of network data

A first course in statistical network analysis and applications. ...

ME-427: Networked control systems

Afficher plus

Séances de cours associées (32)

Renormalisation : AQFT

Couvre le concept de renormalisation dans la théorie des champs quantiques algébriques.

Algèbre linéaire : Diagonalisation

Explore la diagonalisation des matrices et les conditions de diagonalisation exacte, avec des exemples démontrant le processus.

Algèbre linéaire: base canonique

Explore la base canonique en algèbre linéaire, en se concentrant sur la représentation matricielle, la diagonalisation et les polynômes caractéristiques.

Afficher plus

Publications associées (32)

Decentralized Primal-Dual Learning over Directed Graphs

Distributed adaptation and learning over directed, unbalanced graphs poses unique challenges due to asymmetric communication and heterogeneous data across nodes. In this work, we introduce a novel class of first-order primal–dual stochastic gradient algorithms for such graphs. Our flagship algorithm, called primal-dual pull diffusion stochastic gradient, is designed to update both the decision variables (primal) and the associated multipliers (dual) using two left-stochastic combination matrices. This desig

2026

Spectral Clustering with Side Information

In the graph clustering problem with a planted solution, the input is a graph on 𝑛 vertices partitioned into 𝑘 clusters, and the task is to infer the clusters from graph structure. A standard assumption is that clusters induce well-connected subgraphs (i.e. Ω⁡(1)-expanders), and connections between clusters are sparse (i.e. clusters form 𝜖-sparse cuts). Such a graph defines the clustering uniquely up to ≈𝜖 misclassification rate, and efficient algorithms for achieving this rate are known. While this vanill

Society for Industrial and Applied Mathematics2026

Minority takeover in majority dynamics: Searching for rare initializations via the history passing algorithm

We investigate how much bias in the initial configuration is required to drive global agreement in synchronous, deterministic majority dynamics on large random d-regular graphs. Nodes take values ±1 and update their states at each discrete time step to align with the majority of their neighbors. Using the backtracking dynamical cavity method (BDCM), we estimate the minimal fraction of initial +1 nodes required to achieve a +1 consensus in p time steps. Our analysis predicts that for d≥4 an initial global mi

2026

Afficher plus

Personnes associées (32)

Geovani Rizk

Expertise Distributed Machine Learning, Robustness, Safety, Optimization, Multi-Agent, Bandits in Graphs I am a postdoctoral researcher at école Polytechnique Fédérale de Lausanne since 2022, where I work with Rachid Guerraoui on robustness of distributed machine learning algorithms. From 2018 to 2022, I completed my Ph.D. in computer science at Université Paris Dauphine-PSL on multi-agent bandits in graphs under the supervision of Yann Chevaleyre, Rida Laraki, Igor Colin, and Albert Thomas.Pre-prints Over

Friedrich Eisenbrand

Enseignement et PhD Doctorant·es actuel·les Ruben Manuel Skorupinski, Neta Singer, Lukas Vogl, Jiaye Wei A dirigé les thèses EPFL de Thomas Rothvoss, Nicolai Hähnle, Martin Niemeier, Adrian Aloysius Bock, Carsten Moldenhauer, Alfonso Bolívar Cevallos Manzano, Manuel Francesco Aprile, Igor Malinovic, Christoph Hunkenschröder, Moritz Andreas Venzin, Jana Tabea Cslovjecsek A co-dirigé les thèses EPFL de Puck van Gerwen Cours Algèbre linéaire avancée II - diagonalisation MATH-115(a) L'objectif

Pascal Frossard

Teaching & PhD PhD Students Yiming Qin, Alba Carballo Castro, Elisa Messori, Ke Wang, Sevda Ögüt, Tuna Alikasifoglu, William Cappelletti, Manuel Madeira, Mahdi Amiri, Ortal Yona Senouf, Vasiliki Rizou, Cem Bilaloglu, Abdellah Rahmani, Amel Abdelraheem, Jérémy Jean Philippe Baffou, Adam Hazimeh, Vincent Jung, Yike Zhao Past EPFL PhD Students Dan Jurca, Jean-Paul Wagner, Ivana Radulovic, Ivana Tosic, Effrosyni Kokiopoulou, Zafer Arican, Vijayaraghavan Thirumalai, Tamara Tosic, Eirina Bourtsoulatze, Elif Vur

Roger Hersch

Roger D. Hersch is professor of Computer Science and head of the Peripheral Systems Laboratory at EPFL. He received his engineering degree from ETHZ in 1975, worked in industry from 1975 to 1980, and obtained his PhD degree from EPFL in 1985. He directed the widely known Visible Human Web Server project , which offers a number of services for the visualization of human anatomy. His current research focuses on color reproduction, spectral color prediction models, moiré imaging, and visual document security. Recent achievements include the PhotoProtect technology, which incorporates text as chromatic differences in order to protect identity photographs (Swiss driving license), microstructure imaging, which is used by railways companies (SNCF, RENFE) and festival organizers (Paleo) to print tickets at home and the band moire imaging technology for the protection of security documents.

Simon Guilloud

Expertise I am a PhD student at EPFL working in the Laboratory of Automated Reasoning and Analysis with Prof. Viktor KunÄak.My main domains of research are proof assistants and algorithms for logic-related problems. Expertise I am a PhD student at EPFL working in the Laboratory of Automated Reasoning and Analysis with Prof. Viktor KunÄak.My main domains of research are proof assistants and algorithms for logic-related problems.

Maximilien Claude Robert Dreveton

Patrick Thiran

Patrick Thiran is a full professor in network and systems theory at the School of Computer and Communication Sciences at EPFL. He holds an electrical engineering degree from the Université Catholique de Louvain, Louvain-la-Neuve, Belgium, an M.Sc. degree in electrical engineering from the University of California at Berkeley, USA, and he received the PhD degree from EPFL, in 1996. He became an adjunct professor in 1998, an assistant professor in 2002, an associate professor in 2006 and a full professor in 2011. He was with Sprint Advanced Technology Labs in Burlingame, California, in 2000-01. His research interests are in communication and social networks, performance analysis and stochastic models. He is currently active in the analysis and design of wireless and PLC networks (scaling laws, medium access control), in network monitoring (network tomography, multi-layer networks), and data-driven network science. He also contributed to network calculus and to the theory of locally coupled neural networks and self-organizing maps. He served as an associate editor for the IEEE Transactions on Circuits and Systems in 1997-99 and for the IEEE/ACM Transactions on Networking in 2006-10. He is currently on the editorial board of the IEEE Journal on Selected Areas in Communication. He is/was on the program committee of different conferences in networking, including ACM Sigcomm, Sigmetrics, IMC, CoNext and IEEE Infocom. He was TPC chair of AMC IMC 2011 and CoNext 2012. He is a Fellow of the Belgian American Educational Foundation and of the IEEE. He received the 1996 EPFL Doctoral Prize and the 2008 Crédit Suisse Teaching Award.

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.

Thomas Mountford

D'origine britannique, né en 1961. Il a reçu la bourse présidentielle des jeunes investisseurs (Presidential Young Investigator Grant) en 1990 et le prix de la Fraternité Sloan (Sloan Fellowship) en 1991. Son travail montre que les valeurs critiques d'une classe large de de systèmes de particules proches sont égales à 1, et que, suite à plusieurs travaux sur la trajectoire du mouvement brownien, incluant une simulation numérique, le nombre d'îlots browniens en 2 dimensions tend vers l'infini quand leurs tailles tendent vers 0. Il reçoit le prix Rosenbaum en 1993 lui ouvrant ainsi les portes du Isaac Newton Institute à Cambridge. Il est également décoré par le prix Rollo Davidson en 1995 et nommé membre honoraire de l'Institute of Mathematical Statistics en 2001. Assistant Profeseur de Mathematique a UCLA 1987- 1991 Associate Professeur de Mathematique a UCLA 1991-1993 Professeur de Mathematique a UCLA 1993-2001 Professeur Departement de mathématiques, EPFL dès 2001

Robert Dalang

Robert Dalang, né en 1961, a reçu le diplôme de Mathématicien-EPFL en 1983 et est lauréat du Prix Dommer. Il passe l'année 1985-86 à Cornell University (USA) comme chercheur invité. Il obtient le doctorat au Département de mathématiques de l'EPFL en 1987. Son domaine de spécialisation est la théorie des processeurs stochastiques. En 1987, Robert Dalang est nommé professeur assistant au Département de statistiques de l'Université de Californie à Berkeley (USA). En 1988, il reçoit une bourse post-doctorale du Fonds national scientifique américain et effectue des recherches sur les propriétés markoviennes de processus stochastiques à plusieurs paramètres. En 1990, il est nommé à Tufts University (Boston, USA). Il est promu professeur associé en mai 1993. Une partie importante de ses recherches se font dans le cadre de contrats avec le Fonds national scientifique américain et l'Office de la recherche de l'armée américaine. En collaboration avec le Prof. R. Cairoli du Département de mathématiques de l'EPFL, il a écrit un livre sur l'optimisation stochastique séquentielle publié en 1996 aux éditions John Wiley. M. Dalang est nommé professeur extraordinaire de probabilités au Département de mathématiques en 1995. Il y poursuit des travaux de recherche en processus stochastiques et probabilité appliquée et participe à l'enseignement des processus stochastiques, de la théorie des probabilités et des cours de mathématiques aux sections d'ingénieurs. Il dirige régulièrement des thèses de doctorats, est éditeur de plusieurs journaux de recherche mathématique et travail en collaboration avec des chercheurs de plusieurs universités européennes et américaines.

Afficher plus

Unités associées (22)

Laboratoire transport et mobilité

Laboratoire de traitement des signaux 4

SNAI - Gestion

Afficher plus

Concepts associés (31)

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.

Coloration des arêtes d'un graphe

thumb|Coloration des arêtes du graphe de Desargues avec trois couleurs. En théorie des graphes et en algorithmique, une coloration des arêtes d'un graphe consiste à attribuer à chaque arête une couleur, en évitant que deux arêtes ayant une extrémité commune soient de la même couleur. La figure ci-contre est un exemple de coloration d'arêtes correcte. On vérifie en effet qu'aucun sommet n'est commun à deux arêtes de même couleur. On remarquera qu'ici, il n'aurait pas été possible de colorer les arêtes du graphe avec seulement deux couleurs.

Claw-free graph

In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph. A claw is another name for the complete bipartite graph K1,3 (that is, a star graph comprising three edges, three leaves, and a central vertex). A claw-free graph is a graph in which no induced subgraph is a claw; i.e., any subset of four vertices has other than only three edges connecting them in this pattern. Equivalently, a claw-free graph is a graph in which the neighborhood of any vertex is the complement of a triangle-free graph.

Afficher plus

Exercices associés (3)

Graphiques

The position as a function of time of a car in linear motion is given by

\begin{cases} \displaystyle{\frac{1}{2}a_0t^2} \qquad\quad\ \,\, \text{if} \quad t\leq \displaystyle{\frac{v_0}{a_0}} \\ v_0t - \displaystyle{\frac{v_0^2}{2a_0}} \qquad \text{if} \quad t> \displaystyle{\frac{v_0}{a_0}} \end{cases}$$ where v₀ and a₀ are positive constants. The position of the car is illustrated on the graph below: 1. Draw the graphs of velocity v(t) and acceleration a(t) as a function of time. 1. The po

Courant induit par une autre boucle de courant

The current through the coil on the right in Fig.xa0fig:fig7 varies as shown in Fig.xa0fig:fig7a. Which graph in Fig.xa0fig:fig7b best shows the ammeter reading as a function of time? The field created by the first loop:

first, it constantly grows with time ⟹ should induce a constant current in the second loop;
then it’s constant ⟹ no current in the second loop;
finally, it constantly drops with time ⟹ should induce a constant current in the opposite directi

Aller-Retour

A vehicle is in linear motion. The scalar velocity as a function of time is given by v(t)u2004=u2004b₀t²−u2006a₀txa0, where b₀ and a₀ are positive constants.

Determine the position x(t) of the vehicle as a function of time knowing that it is initially at the origin, i.e. x(0)u2004=u20040.
For b₀u2004=u20041 and a₀u2004=u20041, draw the graphs of the position x(t) and of the velocity v(t).
For b₀u2004=u20041 and a₀u2004=u20041, what happens at times tu2004=u20041 and $t=\frac{3}{2}

Notebooks associés (6)

Density of States in 1D Systems

This notebook shows density of states in 1D. Note that all graphs are cut off at Fermi Energy Ef, hence if the cut is visible on the graph consider increasing number of electrons in the system."

Interactive Phonon Band Structure Visualization

In [1]: import numpy as np import matplotlib.pyplot as plt from matplotlib import animation from matplotlib import rc import ipywidgets as ipw from ipywidgets import interact,interactive import ipywidgets as widgets from IPython.display import HTML %matplotlib widget global global_K1 global global_K2 global global_branche global global_selected_k In [2]: def get_closest_point(clic_x,clic_y): # Get the data from the figure ax= plt.gca() # get axis handle acoustic_data = ax.lines[1] op

Temperature Dependence of the Fermi-Dirac Distribution

This notebook serves to show how the Fermi-Dirac distribution and its derivative change with temperature.\n", " \n", "The Fermi-dirac distribution is

f(E)=\\frac{1}{e^{(E-\\mu)/k_bT}+1}

\n", "\n", "For the purpose of simplicity, we will plot the graph of

f(E-\\mu)

. This allows us to avoid complications connected with

\\mu

being a function of temperature (consult the other notebook for this week or section 2.2.3 in the notes for more details)\n", "\n", "We first define the r

Powder X-Ray Diffraction Analysis: Exploring Crystal Structures.

XRay Diffraction[1]¶ The purpose of this notebook is to study the powder XRay diffraction spectra of some systems. When the crystal is hit with an XRay wave, the wave is diffracted only for specific case where the Bragg condition is satisfied for one of the lattice planes in the material. For single crystal diffraction, the condition is satisfied only for specific orientation of the crystal, such that the incident ray has the correct

\theta

value for the plane. In powder XRay data, however, any plane ori

Estimation of Electron Density and Mean Free Time for Transparent Conductors

Chapter 1: Transparent Conductors[1]¶ Instruction: The purpose of this notebook is to try and find values of electron density and mean free time for a material suitable to be used as a transparent conductors. The final estimate should be the order of the two parameters to be used[2]¶ In [1]: import numpy as np from bokeh.io import push_notebook, output_notebook, show from bokeh.layouts import row, column from bokeh.plotting import figure output_notebook() from ipywidgets import interact from collect

Afficher plus

Personnes associées (32)

Maximilien Claude Robert Dreveton

Notebooks associés (6)

Density of States in 1D Systems

This notebook shows density of states in 1D. Note that all graphs are cut off at Fermi Energy Ef, hence if the cut is visible on the graph consider increasing number of electrons in the system."

Interactive Phonon Band Structure Visualization

Temperature Dependence of the Fermi-Dirac Distribution

This notebook serves to show how the Fermi-Dirac distribution and its derivative change with temperature.\n", " \n", "The Fermi-dirac distribution is

f(E)=\\frac{1}{e^{(E-\\mu)/k_bT}+1}

\n", "\n", "For the purpose of simplicity, we will plot the graph of

f(E-\\mu)

. This allows us to avoid complications connected with

\\mu

being a function of temperature (consult the other notebook for this week or section 2.2.3 in the notes for more details)\n", "\n", "We first define the r

Powder X-Ray Diffraction Analysis: Exploring Crystal Structures.

\theta

value for the plane. In powder XRay data, however, any plane ori

Estimation of Electron Density and Mean Free Time for Transparent Conductors

Afficher plus