Fork me on GitHub
Math for the people, by the people.

User login

connected graph

Defines: 
strongly connected graph, connected components, strongly connected components
Synonym: 
connected, strongly connected, component
Type of Math Object: 
Definition
Major Section: 
Reference
Groups audience: 

Mathematics Subject Classification

05C40 no label found

Comments

In my correction (about not every subset that's connected being a connected *component*) i suggested added something along the lines of

> Let $X\sim Y$ denote there exists a path joining vertices X and Y;
> it is not hard to see $\sim$ is an equivalence relation. Each of
> its equivalence classes, together with the edges connected to the
> vertices in that class, is known as a (\emph{connected})
> \emph{component} of the graph.
>
> A \emph{connected graph} is one that consists of a single connected
> component.

I'm glad you didn't take this suggestion up (yet) because my use of the $\sim$ symbol is unfortunate. That notation is already in use for "are linked directly by an edge", not a transitive concept. For the (transitive) relation on vertices of being connected by a path, any other ad hoc symbol would do in the course of the argument, such as $\approx$.

--regards, marijke
http://web.mat.bham.ac.uk/marijke/

Subscribe to Comments for "connected graph"