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 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 in graph theory vary. The following are some of the more basic ways of defining graphs and related mathematical structures. In one restricted but very common sense of the term, a graph is an ordered pair comprising: a set of vertices (also called nodes or points); a set of edges (also called links or lines), which are unordered pairs of vertices (that is, an edge is associated with two distinct vertices). To avoid ambiguity, this type of object may be called precisely an undirected simple graph. In the edge , the vertices and are called the endpoints of the edge. The edge is said to join and and to be incident on and on . A vertex may exist in a graph and not belong to an edge. Multiple edges, not allowed under the definition above, are two or more edges that join the same two vertices. In one more general sense of the term allowing multiple edges, a graph is an ordered triple comprising: a set of vertices (also called nodes or points); a set of edges (also called links or lines); an incidence function mapping every edge to an unordered pair of vertices (that is, an edge is associated with two distinct vertices). To avoid ambiguity, this type of object may be called precisely an undirected multigraph. A loop is an edge that joins a vertex to itself. Graphs as defined in the two definitions above cannot have loops, because a loop joining a vertex to itself is the edge (for an undirected simple graph) or is incident on (for an undirected multigraph) which is not in . So to allow loops the definitions must be expanded.

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 publications (105)

Related people (47)

Related concepts (313)

Related courses (109)

Related lectures (900)

Related MOOCs (16)

MATH-360: Graph theory

The course aims to introduce the basic concepts and results of modern Graph Theory with special emphasis on those topics and techniques that have proved to be applicable in theoretical computer scienc

MATH-260(a): Discrete mathematics

Study of structures and concepts that do not require the notion of continuity. Graph theory, or study of general countable sets are some of the areas that are covered by discrete mathematics. Emphasis

MATH-448: Statistical analysis of network data

A first course in statistical network analysis and applications.

Analyse I

Le contenu de ce cours correspond à celui du cours d'Analyse I, comme il est enseigné pour les étudiantes et les étudiants de l'EPFL pendant leur premier semestre. Chaque chapitre du cours correspond

Analyse I (partie 1) : Prélude, notions de base, les nombres réels

Concepts de base de l'analyse réelle et introduction aux nombres réels.

Analyse I (partie 2) : Introduction aux nombres complexes

Introduction aux nombres complexes

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

IEEE COMPUTER SOC2022

With the increasing prevalence of massive datasets, it becomes important to design algorithmic techniques for dealing with scenarios where the input to be processed does not fit in the memory of a sin

EPFL2022

Spectral Hypergraph Sparsifiers of Nearly Linear Size

Mikhail Kapralov, Jakab Tardos

Graph sparsification has been studied extensively over the past two decades, culminating in spectral sparsifiers of optimal size (up to constant factors). Spectral hypergraph sparsification is a natur

IEEE COMPUTER SOC2022

In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. Adjacent means that two regions share a common boundary curve segment, not merely a corner where three or more regions meet. It was the first major theorem to be proved using a computer. Initially, this proof was not accepted by all mathematicians because the computer-assisted proof was infeasible for a human to check by hand.

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.

Linear Algebra: Canonical Basis

Explores the canonical basis in linear algebra, focusing on matrix representation, diagonalizability, and characteristic polynomials.

Linear Algebra: Diagonalization

Explores the diagonalization of matrices and the conditions for exact diagonalization, with examples demonstrating the process.

Linear Transformations: Matrices and Kernels

Covers linear transformations, matrices, kernels, and properties of invertible matrices.