Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Networks: Trees

Description

This lecture introduces the concept of trees in graph theory, defining them as connected graphs without cycles. It explains the analogy of leaves in trees and the definition of a spanning tree as a subgraph that includes all nodes but only some edges.

In MOOC

Optimization: principles and algorithms - Network and discrete optimization

Official source

Ontological neighbourhood

Mathematics

Discrete mathematics: Graph theory

Related concepts (19)

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.

Component (graph theory)

In graph theory, a component of an undirected graph is a connected subgraph that is not part of any larger connected subgraph. The components of any graph partition its vertices into disjoint sets, and are the induced subgraphs of those sets. A graph that is itself connected has exactly one component, consisting of the whole graph. Components are sometimes called connected components. The number of components in a given graph is an important graph invariant, and is closely related to invariants of matroids, topological spaces, and matrices.

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

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.

Related lectures (30)

Graph Algorithms II: Traversal and Paths

Explores graph traversal methods, spanning trees, and shortest paths using BFS and DFS.

Minimal Spanning Tree

Covers the concept of weighted graphs and the Greedy algorithm for finding a minimal spanning tree.

Minimum Spanning Trees: Prim's Algorithm

Explores Prim's algorithm for minimum spanning trees and introduces the Traveling Salesman Problem.

Connectivity in Graph Theory

Covers the fundamentals of connectivity in graph theory, including paths, cycles, and spanning trees.

Shortest Paths: Negative Weights & Applications

Covers Minimum Spanning Trees, Kruskal's Algorithm, and Shortest Paths in directed graphs.