Read More
Date: 15-5-2022
1251
Date: 3-4-2022
1351
Date: 28-7-2016
1102
|
A G graph is said to be connected if any two vertices of this graph are linked by a path in G. Otherwise, the graph is a disconnected graph.
The connected components of a graph G are the maximal connected induced subgraphs of G. Maximal means here that the subgraph mentioned is not itself a proper subgraph, that is with strictly fewer vertices, of a connected subgraph of G. Obviously, a graph is connected if and only if it has only one connected component.
We verify that the connected components of a graph are subgraphs pairwise disjoint, that is having pairwise no common vertices and no common edges. It defines the decomposition into connected components of the graph (see Figure 1.1 for an example). This decomposition is unique.
Figure 1.1. A disconnected graph and its three connected components: C1,C2, C3
It is also possible to define in algebraic language the connected components of a graph G =(X,E) as the subgraphs induced by equivalence classes over X, defined by the relation: the vertices x and y are linked by a path. This binary relation is in fact an equivalence relation on the set X (reflexive, symmetric and transitive).
To finish connectedness, let us just mention the following proposition:
If a graph possesses a spanning subgraph which is connected, it is itself connected. This proposition is one of many small propositions which are often not proved or even stated. Nevertheless it is useful for a beginner in graph theory to practice by proving them rigorously at least once. If we can do this easily, then all is well, at least so far into the theory. If we do not succeed, we should go back over the preceding pages or maybe rethink our personal logic.
Graph Theory and Applications ,Jean-Claude Fournier, WILEY, page(35-36)
|
|
تفوقت في الاختبار على الجميع.. فاكهة "خارقة" في عالم التغذية
|
|
|
|
|
أمين عام أوبك: النفط الخام والغاز الطبيعي "هبة من الله"
|
|
|
|
|
قسم شؤون المعارف ينظم دورة عن آليات عمل الفهارس الفنية للموسوعات والكتب لملاكاته
|
|
|