**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Graph (discrete mathematics)

Summary

In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called vertices (also called nodes or points) and each of the related pairs of vertices is called an edge (also called link or line). Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges. Graphs are one of the objects of study in discrete mathematics.
The edges may be directed or undirected. For example, if the vertices represent people at a party, and there is an edge between two people if they shake hands, then this graph is undirected because any person A can shake hands with a person B only if B also shakes hands with A. In contrast, if an edge from a person A to a person B means that A owes money to B, then this graph is directed, because owing money is not necessar

Official source

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 publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related publications (33)

Loading

Loading

Loading

Related units (1)

Related concepts (111)

Graph theory

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called no

Glossary of graph theory

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.
Symbols
A

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

Related lectures (169)

Related people (2)

,

Parity (matching theory) and connectivity (network flows) are two main branches of combinatorial optimization. In an attempt to understand better their interrelation, we study a problem where both parity and connectivity requirements are imposed. The main result is a characterization of undirected graphs G = (V,E) having a k-edge-connected T-odd orientation for every subset with |E| + |T| even. (T-odd orientation: the in-degree of v is odd precisely if v is in T.) As a corollary, we obtain that every (2k)-edge- connected graph with |V| + |E| even has a (k-1)-edge- connected orientation in which the in-degree of every node is odd. Along the way, a structural characterization will be given for digraphs with a root-node s having k edge- disjoint paths from s to every node and k-1 edge-disjoint paths from every node to s.

2001We present an algorithm that generates natural and intuitive deformations via direct manipulation for a wide range of shape representations and editing scenarios. Our method builds a space deformation represented by a collection of affine transformations organized in a graph structure. One transformation is associated with each graph node and applies a deformation to the nearby space. Positional constraints are specified on the points of an embedded object. As the user manipulates the constraints, a nonlinear minimization problem is solved to find optimal values for the affine transformations. Feature preservation is encoded directly in the objective function by measuring the deviation of each transformation from a true rotation. This algorithm addresses the problem of "embedded deformation" since it deforms space through direct manipulation of objects embedded within it, while preserving the embedded objects' features. We demonstrate our method by editing meshes, polygon soups, mesh animations, and animated particle systems. © 2007 ACM.

2007Related courses (54)

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics as diverse as mathematical reasoning, combinatorics, discrete structures & algorithmic thinking.

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, major algorithmic paradigms such as dynamic programming, sorting and searching, and graph algorithms.

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.

Graph theory is an important topic in discrete mathematics. It is particularly interesting because it has a wide range of applications. Among the main problems in graph theory, we shall mention the following ones: graph coloring and the Hamiltonian circuit problem. Chapter 1 presents basic definitions of graph theory, such as graph coloring, graph coloring with color-classes of bounded size b, and Hamiltonian circuits and paths. We also present online algorithms and online coloring. Chapter 2 starts with some general remarks about online graph covering with sets of bounded sizes (such as online bounded coloring): we give a simple method for transforming an online covering algorithm into an online bounded covering algorithm, and to derive the performance ratio of the bounded algorithm from the performance ratio of the unbounded algorithm. As will be shown in later chapters, this method often leads to optimal results. Furthermore, some basic preliminary results on online graph covering with sets of bounded size are given: for every graph, the performance ratio is bounded above by 1/2 + b/2 and for b = 2, this bound is optimal. In the second part, online coloring of co-interval graphs is studied. Based on two industrial applications, two different versions of this problem are discussed. In the case where the intervals are presented in increasing order of their left ends, we show that the performance ratio is 1 in the unbounded case and 2 - 1/b in the bounded case. In the case where the intervals may be presented in any order, we show that the performance ratio is at most 3 in the bounded case. Chapter 3 deals with online coloring of permutation and comparability graphs. First, we give a tight analysis of the First-Fit algorithm on bipartite permutation graphs and we show that its performance ratio is O(√n), even for some simple presentation orders. For both classes of graphs, we show that the performance ratio is bounded above by (χ+1)/2 in the unbounded case and that the performance ratio of First-Fit is equal to 1/2 + b/2 in the bounded case. In the second part of this chapter, we study cocoloring of permutation graphs. We show that the performance ratio is n/4 + 1/2 and we give better bounds in some more restricted cocoloring problems. Chapter 4 deals with an application of online coloring: the online Track Assignment Problem. Depending on the assumptions that are made, the Track Assignment Problem can be reduced to coloring permutation or overlap graphs online. We show that when a permutation graph is presented on a latticial plane, from west to east, then the performance ratio is exactly 2 - (min{b,k})-1, where k is the best known upper bound on the bounded chromatic number. We also show that, when a permutation graph is presented on a latticial plan, starting from the origin and growing, simultaneously or not, towards west and east, then the performance ratio is exactly 2 - 1/χ. We also show that online coloring overlap graphs does not have a performance ratio bounded by a constant, even if the overlap graph is bipartite and presented in increasing order of the intervals left ends. In this special case, we show that First-Fit has a tight performance ratio of O(√n). We consider coloring overlap graphs online where the intervals have a bounded size between 1 and a given number M. In this case, we show that the performance ratio can be bounded above by 2√M if M ≤ M0, and by log M (⎡log M / log log M⎤ + 1) if M > M0, M0 being defined by the equation 2√M0 = 3 log(M0). For large values of M, the ratio is O(log2 M / log log M). Chapter 5 is about online coloring of trees, forests and split-graphs. For trees, we show that the performance ratio of online coloring is exactly ½log2(2n) in the unbouded case and at most 1 + ⎣log2(b)⎦/χb in the bounded case. For split-graphs, we show that the performance ratio of online coloring is exactly 1 + 1/χ in the unbounded case and is at most 2 + 1/χb + 3/b in the bounded case. In Chapter 6, we present a class of digraphs: the quasi-adjoint graphs. These are a super class of both the graphs used for a DNA sequencing algorithm in (Blazewicz, Kasprzak, "Computational complexity of isothermic DNA sequencing by hybridization", 2006) and the adjoints. A polynomial recognition algorithm in O(n3), as well as a polynomial algorithm in O(n2 + m2) for finding a Hamiltonian circuit in quasi-adjoint graphs are given. Furthermore, some results about related problems such as finding a Eulerian circuit while respecting some forbidden transitions (a sequence of two consecutive arcs) are discussed.