You get a bonus - 1 coin for daily activity. Now you have 1 coin

Connected graph

Lecture



A connected graph is a graph containing exactly one connected component. This means that there is at least one path between any pair of vertices of this graph.

Application examples

A direct application of graph theory is the theory of networks — and its application — the theory of electronic networks. For example, all computers connected to the Internet form a connected graph, and although a single pair of computers may not be connected directly (in the wording for graphs, not be connected by an edge), you can transfer information to any other computer from any computer vertices of the graph in any other).

Connectivity for directed graphs

In oriented graphs, several concepts of connectedness are distinguished.

An oriented graph is said to be strongly connected if there exists a (oriented) path from any vertex to any other, or, equivalently, the graph contains exactly one strongly connected component.

A directed graph is said to be weakly connected if the unoriented graph obtained from it is replaced by a replacement of oriented edges with an undirected one.

Some connectivity criteria

Here are some criterion (equivalent) definitions of a connected graph:
A graph is said to be simply connected (connected) if:

  1. It has one connected component.
  2. There is a path from any vertex to any other vertex.
  3. There is a path from a given vertex to any other vertex.
  4. Contains a connected subgraph that includes all vertices of the original graph
  5. Contains as a subgraph a tree that includes all the vertices of the original graph (such a tree is called a spanner)
  6. When arbitrarily dividing its vertices into 2 groups, there is always at least 1 edge connecting a pair of vertices from different groups.
created: 2015-01-06
updated: 2021-03-13
132620



Rating 9 of 10. count vote: 2
Are you satisfied?:



Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Discrete Math. Set theory. Graph theory. Combinatorics.

Terms: Discrete Math. Set theory. Graph theory. Combinatorics.