In graph theory, an edge contraction is an operation that removes an edge from a graph while simultaneously merging the two vertices that it previously joined. Edge contraction is a fundamental operation in the theory of graph minors. Vertex identification is a less restrictive form of this operation. The edge contraction operation occurs relative to a particular edge, . The edge is removed and its two incident vertices, and , are merged into a new vertex , where the edges incident to each correspond to an edge incident to either or . More generally, the operation may be performed on a set of edges by contracting each edge (in any order). The resulting induced graph is sometimes written as . (Contrast this with , which means removing the edge .) As defined below, an edge contraction operation may result in a graph with multiple edges even if the original graph was a simple graph. However, some authors disallow the creation of multiple edges, so that edge contractions performed on simple graphs always produce simple graphs. Let be a graph (or directed graph) containing an edge with . Let be a function that maps every vertex in to itself, and otherwise, maps it to a new vertex . The contraction of results in a new graph , where , , and for every , is incident to an edge if and only if, the corresponding edge, is incident to in . Vertex identification (sometimes called vertex contraction) removes the restriction that the contraction must occur over vertices sharing an incident edge. (Thus, edge contraction is a special case of vertex identification.) The operation may occur on any pair (or subset) of vertices in the graph. Edges between two contracting vertices are sometimes removed. If and are vertices of distinct components of , then we can create a new graph by identifying and in as a new vertex in . More generally, given a partition of the vertex set, one can identify vertices in the partition; the resulting graph is known as a quotient graph.

About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related lectures (10)
Directed Networks & Hypergraphs
Explores directed networks with asymmetric relationships and hypergraphs that generalize graphs by allowing edges to connect any subset of nodes.
Introduction to Graph Theory
Covers the basics of graph theory, including network flows, degrees of vertices, walks, and subgraphs.
Memory Management: Part I
Covers memory management concepts such as block headers, external fragmentation, reference counting, and mark & sweep garbage collection.
Show more
Related publications (32)

GRAMM: Fast CGRA Application Mapping Based on A Heuristic for Finding Graph Minors

Mirjana Stojilovic, Guanglei Zhou

A graph H is a minor of a second graph G if G can be transformed into H by two operations: 1) deleting nodes and/or edges, or 2) contracting edges. Coarse-grained reconfigurable array (CGRA) application mapping is closely related to the graph minor problem ...
2023

Modeling Structured Data in Attention-based Models

Alireza Mohammadshahi

Natural language processing has experienced significant improvements with the development of Transformer-based models, which employ self-attention mechanism and pre-training strategies. However, these models still present several obstacles. A notable issue ...
EPFL2023

GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation

Daniel Gatica-Perez, Sina Sajadmanesh

In this paper, we study the problem of learning Graph Neural Networks (GNNs) with Differential Privacy (DP). We propose a novel differentially private GNN based on Aggregation Perturbation (GAP), which adds stochastic noise to the GNN's aggregation functio ...
Berkeley2023
Show more
Related people (2)
Related concepts (5)
Directed graph
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. In formal terms, a directed graph is an ordered pair where V is a set whose elements are called vertices, nodes, or points; A is a set of ordered pairs of vertices, called arcs, directed edges (sometimes simply edges with the corresponding set named E instead of A), arrows, or directed lines.
Graph minor
In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges, vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only if its minors include neither the complete graph K5 nor the complete bipartite graph K3,3. The Robertson–Seymour theorem implies that an analogous forbidden minor characterization exists for every property of graphs that is preserved by deletions and edge contractions.
Directed acyclic graph
In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called arcs), with each edge directed from one vertex to another, such that following those directions will never form a closed loop. A directed graph is a DAG if and only if it can be topologically ordered, by arranging the vertices as a linear ordering that is consistent with all edge directions.
Show more

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.