Discrete Mathsfor Engineers

Structures, proofs, and intuition
EN | PT

Graph Theory → Foundations

Part 11 of 11 — Connected Component

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

Concept

Connected component: Let G = (V, E) be an undirected graph and let G′ ⊆ G be a subgraph. We say that G′ is a connected component of G if, for all u, v ∈ VG′, there exists a path in G connecting u to v.

A B C D E
In this example, taking G′ ⊆ G with VG′ = {A, B, C, D, E}, there exists a path between any two vertices in VG′. Therefore, G′ is a connected component of G.
Made with ❤️ by Leandro Rodrigues