Math 2.0

definition

Connected component

Definition

Let GG be a graph. A connected component of GG is an equivalence class of the vertices of GG under reachability. The subgraph induced by a connected component is also called a connected component.

Remarks

The connected components partition the vertex set. Each component, as an induced subgraph, is connected. A graph with nn vertices and mm edges has at least n−mn - m components. A graph with no edges on nn vertices has nn components.

Explanations

L1 human

The connected components are the separate pieces of a graph. Two vertices are in the same piece exactly when a walk joins them.

What this node needs for W1
  • an inventory row: the row of the inventory that the node accounts for (0 of 1)

The writing levels say how complete the text of a node is. They do not measure its truth.

What this needs

To read this node, read these 4 nodes in this order. The foundations come first, and the list ends with this node.

Graph, definition, no evidence levelGraphdefinitionWalk, definition, no evidence levelWalkdefinitionReachability, definition, no evidence levelReachabilitydefinitionConnected component, definition, no evidence levelConnected componentdefinition
Each node uses the nodes above it. The colour of the bar on a box shows the evidence level, and the box also gives it as text. The list below has the same nodes.
  • no evidence level
  1. Graph definition
  2. Walk definition
  3. Reachability definition
  4. Connected component definition

What depends on this

3 nodes use this node, directly or through other nodes.

Sources

  1. Web https://en.wikipedia.org/wiki/Component_(graph_theory), Definitions and examples

What links here

Used by