Connectivity-Edge connectivity
المؤلف:
Jean-Claude Fournier
المصدر:
Graph Theory and Applications
الجزء والصفحة:
63-64
28-7-2016
1580
We are going to define for edges, concepts equivalent to the one mentioned above. The edge connectivity 
of a graph G, with more than one vertex, is the smallest number of edges by which removal disconnects the graph. In particular, it is 0 if the graph is disconnected. The edge connectivity is considered equal to 0 if the graph has only one vertex.
We can formalize the definition in this way. If the graph G has at least two vertices, it has a set of edges B, possibly empty, suchthat G − B is disconnected, and we put in that case:
The set of edges B is what we call an (edge) cut of G. If G has only one vertex, we put:
There is an inequality relation between connectivity and edge connectivity, given in the following proposition.
Proposition 1.1.
For any simple graph G, we have:
The second inequality is easy, the first can be shown directly but also results easily from Menger’s theorem (see later). These inequalities may be strict .
_________________________________________________________________________________
Graph Theory and Applications ,Jean-Claude Fournier, WILEY, page(63-64)
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
