Lecture

Geometry: Eulerian Circuits

Graph Chat

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.

In course

MATH-124: Geometry for architects I

Ce cours entend exposer les fondements de la géométrie à un triple titre : 1/ de technique mathématique essentielle au processus de conception du projet, 2/ d'objet privilégié des logiciels de conception paramétrique 3/ de composante à part entière de l'h ...

Description

This lecture introduces the concept of Eulerian circuits by exploring the famous problem of Königsberg bridges in 1736, where the goal is to find a walk passing through each bridge exactly once and returning to the starting point. The instructor explains how this problem led to the development of graph theory and topology, highlighting the fundamental principles that govern Eulerian circuits and their application in modern mathematics.

Instructor

Bernard Cache

Official source

Ontological neighbourhood

Mathematics

Discrete mathematics: Graph theory

Related concepts (31)

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.

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.

Connectivity (graph theory)

In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network. In an undirected graph G, two vertices u and v are called connected if G contains a path from u to v.

Path (graph theory)

In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices which, by most definitions, are all distinct (and since the vertices are distinct, so are the edges). A directed path (sometimes called dipath) in a directed graph is a finite or infinite sequence of edges which joins a sequence of distinct vertices, but with the added restriction that the edges be all directed in the same direction. Paths are fundamental concepts of graph theory, described in the introductory sections of most graph theory texts.

Eulerian path

In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. The problem can be stated mathematically like this: Given the graph in the image, is it possible to construct a path (or a cycle; i.

Related lectures (64)

Invariance of Domain

Delves into the invariance of domain theorem, proving that a subset homeomorphic to an open subset is open itself, with implications for embeddings and homeomorphisms.

Topology in Complex Networks: Insights from Topological Data Analysis

Explores the role of higher-order topological properties in complex networks using topological data analysis for structural break and price anomaly detection.

Cheeger's Inequalities

Explores Cheeger's inequalities for random walks on graphs and their implications.

Power of a Point in Geometry

Explores the power of a point outside a circle and its practical applications.

Interlacing Families and Ramanujan Graphs

Explores interlacing families, Ramanujan graphs, and their construction using signed adjacency matrices.