Concept# Graph theory

Summary

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 nodes or points) which are connected by edges (also called links or lines). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics.
Definitions
Definitions in graph theory vary. The following are some of the more basic ways of defining graphs and related mathematical structures.
Graph
In one restricted but very common sense of the term, a graph is an ordered pair G=(V,E) comprising:

- V, a set of vertices (also called nodes or points);
- E \subseteq { {x, y} \mid x, y \in V ;\textrm{ and }; x \neq y }, a set of edges (also called links or lines)

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 courses (110)

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.

CS-411: Digital education

This course addresses the relationship between specific technological features and the learners' cognitive processes. It also covers the methods and results of empirical studies on this topic: do student actually learn due to technologies?

CS-250: Algorithms

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.

Related people (63)

Related publications (100)

Loading

Loading

Loading

Related concepts (147)

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

Graph (discrete mathematics)

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 corre

Planar graph

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it c

Related units (33)

Related lectures (288)

Mika Tapani Göös, Siddhartha Jain

We exhibit an unambiguous k-DNF formula that requires CNF width (Omega) over tilde (k(2)), which is optimal up to logarithmic factors. As a consequence, we get a near-optimal solution to the Alon-Saks-Seymour problem in graph theory (posed in 1991), which asks: How large a gap can there be between the chromatic number of a graph and its biclique partition number? Our result is also known to imply several other improved separations in query and communication complexity.

Alexandre Thierry Robert Cherqui

This master thesis provides in-depth explanations of how deep learning and graph theory can be used together to perform pointwise classification in 3D point clouds obtained by combinations of geospatial images. That scene understanding problem arises in a number of practical scenarios, e.g. for governments to survey deforestation from aerial images taken by drones. After an introduction on the problem statement and the main assets of typical architectures used for images, this thesis introduces the neural network architecture we developed, and describes how to build its main elements together with the graphs. To assess its performances, our architecture based on graph convolutions was tested under two different scenarios and compared to traditional machine learning algorithms.

2018Graph 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.