Discrete Mathsfor Engineers

Structures, proofs, and intuition
EN | PT

Graph Theory → Foundations

Part 10 of 11 — Connected Graph

Series: Foundations Part 10 of 11
← Previous Next →
1 2 3 4 5 6 7 8 9 10 11

Concept: undirected graph

An undirected graph G = (V, E) is connected if, for any vertices u, v ∈ V, there exists a path in G connecting u to v.

A B C D E
Examples of paths: A → B → C, E → B → C → D, D → C → B → A. Since there exists a path between any two vertices, the graph is connected.

Concept: directed graph

A directed graph is said to be strongly connected if, for any vertices u, v ∈ {A, B, C, D, E}, there exists a directed path from u to v and also from v to u.

A B C D E
The graph forms a directed cycle A → B → C → D → E → A, and is therefore strongly connected.
Made with ❤️ by Leandro Rodrigues