Lecture

Directed Graphs: Introduction and Categories

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.

Description

This lecture introduces the fundamental notion of composition of applications in the context of directed graphs, also known as quivers. It covers the definition of a directed graph, consisting of classes of vertices and edges with domain and codomain functions. Examples of directed graphs are provided, illustrating relations on sets and their representation as directed graphs.

Official source

Ontological neighbourhood

Mathematics

Discrete mathematics: Graph theory

Related concepts (32)

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.

Domain of a function

In mathematics, the domain of a function is the set of inputs accepted by the function. It is sometimes denoted by or , where f is the function. In layman's terms, the domain of a function can generally be thought of as "what x can be". More precisely, given a function , the domain of f is X. In modern mathematical language, the domain is part of the definition of a function rather than a property of it. In the special case that X and Y are both subsets of , the function f can be graphed in the Cartesian coordinate system.

Partial function

In mathematics, a partial function f from a set X to a set Y is a function from a subset S of X (possibly the whole X itself) to Y. The subset S, that is, the domain of f viewed as a function, is called the domain of definition or natural domain of f. If S equals X, that is, if f is defined on every element in X, then f is said to be a total function. More technically, a partial function is a binary relation over two sets that associates every element of the first set to at most one element of the second set; it is thus a functional binary relation.

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.

Cycle graph

In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with n vertices is called C_n. The number of vertices in C_n equals the number of edges, and every vertex has degree 2; that is, every vertex has exactly two edges incident with it. There are many synonyms for "cycle graph".

Related lectures (64)

Graph Theory and Network Flows

Introduces graph theory, network flows, and flow conservation laws with practical examples and theorems.

Graph Algorithms: Modeling and Traversal

Covers graph algorithms, modeling relationships between objects, and traversal techniques like BFS and DFS.

Introduction to Categories

Introduces the concept of categories essential for understanding group theory.

Graphs and Networks: Basics and Applications

Introduces the basics of graphs and networks, covering definitions, paths, trees, flows, circulation, and spanning trees.

Max Flav-Min Cut in Directed Graphs