Namespaces
Variants
Actions

Difference between revisions of "Graph, connectivity of a"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
Line 1: Line 1:
One of the topological characteristics of a graph. A graph is said to be connected if for any two of its vertices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g0449101.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g0449102.png" /> there exists a chain connecting these vertices. The vertex connectivity number of a graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g0449103.png" /> (denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g0449104.png" />) is the smallest number of vertices the removal of which results in a disconnected graph or in a graph consisting of one isolated vertex. The edge connectivity number (denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g0449105.png" />) is the smallest number of edges of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g0449106.png" /> the removal of which results in a disconnected graph. A graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g0449107.png" /> is said to be <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g0449109.png" />-connected if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491010.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491012.png" />-edge-connected if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491013.png" />. A maximal <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491014.png" />-connected subgraph of a graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491015.png" /> is said to be a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491017.png" />-connected component of it; a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491018.png" />-connected component is called a connected component. In studying communication networks and logical networks, the connectivity numbers of the corresponding graphs can be interpreted as a degree of reliability of these networks.
+
<!--
 +
g0449101.png
 +
$#A+1 = 97 n = 0
 +
$#C+1 = 97 : ~/encyclopedia/old_files/data/G044/G.0404910 Graph, connectivity of a
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
The theory of graphs studies methods for determining the connectivity of graphs, conditions under which a graph is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491019.png" />-connected or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491020.png" />-edge-connected, the relations between the different types of connectivity, the dependence of the connectivity numbers on other graph parameters, etc. Thus, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491021.png" /> is the minimal degree of the vertices of a graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491022.png" />, the following inequalities are valid: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491023.png" />.
+
{{TEX|auto}}
 +
{{TEX|done}}
  
For any integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491024.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491025.png" />) there exists a graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491026.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491027.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491028.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491029.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491030.png" /> has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491031.png" /> vertices and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491032.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491033.png" />. One says that a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491034.png" /> of vertices, edges, or vertices and edges separates two vertices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491035.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491036.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491037.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491038.png" /> belong to different connected components of the graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491039.png" /> obtained from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491040.png" /> by the removal of the elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491041.png" />. The following statements are valid.
+
One of the topological characteristics of a graph. A graph is said to be connected if for any two of its vertices $  u $
 +
and $  v $
 +
there exists a chain connecting these vertices. The vertex connectivity number of a graph  $  G $(
 +
denoted by  $  \kappa ( G) $)
 +
is the smallest number of vertices the removal of which results in a disconnected graph or in a graph consisting of one isolated vertex. The edge connectivity number (denoted by  $  \lambda ( G) $)
 +
is the smallest number of edges of  $  G $
 +
the removal of which results in a disconnected graph. A graph  $  G $
 +
is said to be  $  k $-
 +
connected if  $  \kappa ( G) \geq  k $,
 +
and $  k $-
 +
edge-connected if $  \lambda ( G) \geq  k $.  
 +
A maximal  $  k $-
 +
connected subgraph of a graph  $  G $
 +
is said to be a  $  k $-
 +
connected component of it; a  $  1 $-
 +
connected component is called a connected component. In studying communication networks and logical networks, the connectivity numbers of the corresponding graphs can be interpreted as a degree of reliability of these networks.
  
The smallest number of vertices separating two non-adjacent vertices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491042.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491043.png" /> is equal to the largest number of simple chains without common vertices connecting <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491044.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491045.png" />. A graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491046.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491047.png" />-connected if and only if any pair of its vertices is connected by at least <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491048.png" /> chains which do not intersect at the vertices. Similar theorems are also valid for edge connectivity. A graph is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491049.png" />-edge-connected if and only if any pair of its vertices is connected by at least <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491050.png" /> chains which do not intersect at the edges. A set of edges whose removal results in the formation of a disconnected graph is known as a cut. In each graph the largest number of cuts which do not intersect at the edges and which separate two vertices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491051.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491052.png" /> is equal to the smallest number of edges of a simple chain connecting <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491053.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491054.png" />, i.e. to the distance <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491055.png" /> between <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491056.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491057.png" />.
+
The theory of graphs studies methods for determining the connectivity of graphs, conditions under which a graph is  $  k $-
 +
connected or  $  k $-
 +
edge-connected, the relations between the different types of connectivity, the dependence of the connectivity numbers on other graph parameters, etc. Thus, if  $  \delta ( G) $
 +
is the minimal degree of the vertices of a graph  $  G $,
 +
the following inequalities are valid:  $  \kappa ( G) \leq  \lambda ( G) \leq  \delta ( G) $.
 +
 
 +
For any integers  $  a, b, c $(
 +
$  0 < a \leq  b \leq  c $)
 +
there exists a graph  $  G $
 +
for which  $  \kappa ( G) = a $,
 +
$  \lambda ( G) = b $,
 +
$  \delta ( G) = c $.  
 +
If  $  G $
 +
has  $  n $
 +
vertices and  $  \delta ( G) \geq  [ n/2] $,
 +
then  $  \lambda ( G) = \delta ( G) $.  
 +
One says that a set  $  S $
 +
of vertices, edges, or vertices and edges separates two vertices  $  u $
 +
and  $  v $
 +
if  $  u $
 +
and $  v $
 +
belong to different connected components of the graph  $  G- S $
 +
obtained from  $  G $
 +
by the removal of the elements of  $  S $.  
 +
The following statements are valid.
 +
 
 +
The smallest number of vertices separating two non-adjacent vertices  $  u $
 +
and  $  v $
 +
is equal to the largest number of simple chains without common vertices connecting $  u $
 +
and $  v $.  
 +
A graph $  G $
 +
is $  k $-
 +
connected if and only if any pair of its vertices is connected by at least $  k $
 +
chains which do not intersect at the vertices. Similar theorems are also valid for edge connectivity. A graph is $  k $-
 +
edge-connected if and only if any pair of its vertices is connected by at least $  k $
 +
chains which do not intersect at the edges. A set of edges whose removal results in the formation of a disconnected graph is known as a cut. In each graph the largest number of cuts which do not intersect at the edges and which separate two vertices $  u $
 +
and $  v $
 +
is equal to the smallest number of edges of a simple chain connecting $  u $
 +
and $  v $,  
 +
i.e. to the distance $  d ( u , v) $
 +
between $  u $
 +
and $  v $.
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  F. Harary,  "Graph theory" , Addison-Wesley  (1969)  pp. Chapt. 9</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  L.R. Ford,  D.R. Fulkerson,  "Flows in networks" , Princeton Univ. Press  (1962)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  F. Harary,  "Graph theory" , Addison-Wesley  (1969)  pp. Chapt. 9</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  L.R. Ford,  D.R. Fulkerson,  "Flows in networks" , Princeton Univ. Press  (1962)</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====
 
The assertions in the last section can be derived from the maximum-flow-minimum-cut theorem of L. Ford and D. Fulkerson (see [[#References|[2]]]). The first two are different versions of the vertex form of Menger's theorem (see [[#References|[1]]]).
 
The assertions in the last section can be derived from the maximum-flow-minimum-cut theorem of L. Ford and D. Fulkerson (see [[#References|[2]]]). The first two are different versions of the vertex form of Menger's theorem (see [[#References|[1]]]).
  
The maximum-flow-minimum-cut theorem, or the Ford–Fulkerson theorem, deals with a directed graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491058.png" /> for which for each arc <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491059.png" /> a capacity <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491060.png" /> is specified. In addition, two special vertices, labeled <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491061.png" />, are specified, called source and sink respectively, and there are no arcs leaving <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491062.png" /> or entering <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491063.png" />. A flow on the graph is given by specifying for every arc (i.e. directed edge) a number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491064.png" /> such that for every vertex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491065.png" />,
+
The maximum-flow-minimum-cut theorem, or the Ford–Fulkerson theorem, deals with a directed graph $  G $
 +
for which for each arc $  e $
 +
a capacity $  0 \leq  c _ {e} < \infty $
 +
is specified. In addition, two special vertices, labeled $  Q, S $,  
 +
are specified, called source and sink respectively, and there are no arcs leaving $  S $
 +
or entering $  Q $.  
 +
A flow on the graph is given by specifying for every arc (i.e. directed edge) a number 0 \leq  f _ {e} \leq  c _ {e} $
 +
such that for every vertex $  P \neq Q, S $,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491066.png" /></td> <td valign="top" style="width:5%;text-align:right;">(*)</td></tr></table>
+
$$ \tag{* }
 +
\sum _ {a ( e) = P } f _ {e}  = \
 +
\sum _ {b ( e) = P } f _ {e}  $$
  
where for an arc <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491067.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491068.png" /> denotes its source vertex and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491069.png" /> its target vertex. The maximum flow problem asks for a flow such that
+
where for an arc $  e $,  
 +
$  a ( e) $
 +
denotes its source vertex and $  b ( e) $
 +
its target vertex. The maximum flow problem asks for a flow such that
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491070.png" /></td> </tr></table>
+
$$
 +
\sum _ {a ( e) = Q } f _ {e}  $$
  
is maximized. In this setting a cut is a set of arcs whose removal results in a disconnected graph with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491071.png" /> in one component and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491072.png" /> in another. The capacity of a cut is the sum of the capacities <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491073.png" /> of the elements of the cut. The maximum-flow-minimum-cut theorem now says that the maximum flow attainable is equal to the minimal attainable capacity of a cut. The maximum flow problem can be formulated as a linear programming problem, and then the maximum-flow-minimum-cut theorem is an instance of the duality theorem of linear programming.
+
is maximized. In this setting a cut is a set of arcs whose removal results in a disconnected graph with $  Q $
 +
in one component and $  S $
 +
in another. The capacity of a cut is the sum of the capacities $  c _ {e} $
 +
of the elements of the cut. The maximum-flow-minimum-cut theorem now says that the maximum flow attainable is equal to the minimal attainable capacity of a cut. The maximum flow problem can be formulated as a linear programming problem, and then the maximum-flow-minimum-cut theorem is an instance of the duality theorem of linear programming.
  
Recall that a chain in a non-oriented graph from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491074.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491075.png" /> is a sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491076.png" /> of alternating vertices and edges such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491077.png" /> is an edge between <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491078.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491079.png" /> and such that all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491080.png" /> and all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491081.png" />, except possibly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491082.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491083.png" />, are distinct. A <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491085.png" />-disconnecting set or cut, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491086.png" /> are two vertices, is a set of edges whose removal results in a disconnected graph with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491087.png" /> in one component and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491088.png" /> in another. The edge form of Menger's theorem now says that for a connected graph the maximum number of edge-disjoint chains from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491089.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491090.png" /> is equal to the minimum number of edges in a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491091.png" />-disconnecting set. The theorem was in fact first proved by Ford and Fulkerson (1955). A <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491093.png" />-separating set is a set of vertices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491094.png" /> (not including <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491095.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491096.png" />) such that any chain from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491097.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491098.png" /> passes through <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g04491099.png" />. The vertex form of Menger's theorem (Menger, 1928) now says that the maximum number of vertex-disjoint chains connecting distinct non-adjacent vertices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g044910100.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g044910101.png" /> is equal to the minimal number of vertices in a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044910/g044910102.png" />-separating set. Menger's theorem is closely related to the P. Hall marriage theorem; cf. [[Combinatorial analysis|Combinatorial analysis]] for that theorem.
+
Recall that a chain in a non-oriented graph from $  v _ {0} $
 +
to $  v _ {n} $
 +
is a sequence $  v _ {0} e _ {0} v _ {1} \dots e _ {n - 1 }  v _ {n} $
 +
of alternating vertices and edges such that $  e _ {i} $
 +
is an edge between $  v _ {i} $
 +
and $  v _ {i + 1 }  $
 +
and such that all $  e _ {j} $
 +
and all $  v _ {k} $,  
 +
except possibly $  v _ {0} $
 +
and $  v _ {n} $,  
 +
are distinct. A $  vw $-
 +
disconnecting set or cut, where $  v, w $
 +
are two vertices, is a set of edges whose removal results in a disconnected graph with $  v $
 +
in one component and $  w $
 +
in another. The edge form of Menger's theorem now says that for a connected graph the maximum number of edge-disjoint chains from $  v $
 +
to $  w $
 +
is equal to the minimum number of edges in a $  vw $-
 +
disconnecting set. The theorem was in fact first proved by Ford and Fulkerson (1955). A $  vw $-
 +
separating set is a set of vertices $  S $(
 +
not including $  v $
 +
or $  w $)  
 +
such that any chain from $  v $
 +
to $  w $
 +
passes through $  S $.  
 +
The vertex form of Menger's theorem (Menger, 1928) now says that the maximum number of vertex-disjoint chains connecting distinct non-adjacent vertices $  v $
 +
and $  w $
 +
is equal to the minimal number of vertices in a $  vw $-
 +
separating set. Menger's theorem is closely related to the P. Hall marriage theorem; cf. [[Combinatorial analysis|Combinatorial analysis]] for that theorem.
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  W.T. Tutte,  "Connectivity in graphs" , Oxford Univ. Press  (1966)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  R.J. Wilson,  "Introduction to graph theory" , Longman  (1985)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  H.-J. Walther,  "Ten applications of graph theory" , Reidel  (1984)  pp. Sect. 6.1</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  W.T. Tutte,  "Connectivity in graphs" , Oxford Univ. Press  (1966)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  R.J. Wilson,  "Introduction to graph theory" , Longman  (1985)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  H.-J. Walther,  "Ten applications of graph theory" , Reidel  (1984)  pp. Sect. 6.1</TD></TR></table>

Revision as of 19:42, 5 June 2020


One of the topological characteristics of a graph. A graph is said to be connected if for any two of its vertices $ u $ and $ v $ there exists a chain connecting these vertices. The vertex connectivity number of a graph $ G $( denoted by $ \kappa ( G) $) is the smallest number of vertices the removal of which results in a disconnected graph or in a graph consisting of one isolated vertex. The edge connectivity number (denoted by $ \lambda ( G) $) is the smallest number of edges of $ G $ the removal of which results in a disconnected graph. A graph $ G $ is said to be $ k $- connected if $ \kappa ( G) \geq k $, and $ k $- edge-connected if $ \lambda ( G) \geq k $. A maximal $ k $- connected subgraph of a graph $ G $ is said to be a $ k $- connected component of it; a $ 1 $- connected component is called a connected component. In studying communication networks and logical networks, the connectivity numbers of the corresponding graphs can be interpreted as a degree of reliability of these networks.

The theory of graphs studies methods for determining the connectivity of graphs, conditions under which a graph is $ k $- connected or $ k $- edge-connected, the relations between the different types of connectivity, the dependence of the connectivity numbers on other graph parameters, etc. Thus, if $ \delta ( G) $ is the minimal degree of the vertices of a graph $ G $, the following inequalities are valid: $ \kappa ( G) \leq \lambda ( G) \leq \delta ( G) $.

For any integers $ a, b, c $( $ 0 < a \leq b \leq c $) there exists a graph $ G $ for which $ \kappa ( G) = a $, $ \lambda ( G) = b $, $ \delta ( G) = c $. If $ G $ has $ n $ vertices and $ \delta ( G) \geq [ n/2] $, then $ \lambda ( G) = \delta ( G) $. One says that a set $ S $ of vertices, edges, or vertices and edges separates two vertices $ u $ and $ v $ if $ u $ and $ v $ belong to different connected components of the graph $ G- S $ obtained from $ G $ by the removal of the elements of $ S $. The following statements are valid.

The smallest number of vertices separating two non-adjacent vertices $ u $ and $ v $ is equal to the largest number of simple chains without common vertices connecting $ u $ and $ v $. A graph $ G $ is $ k $- connected if and only if any pair of its vertices is connected by at least $ k $ chains which do not intersect at the vertices. Similar theorems are also valid for edge connectivity. A graph is $ k $- edge-connected if and only if any pair of its vertices is connected by at least $ k $ chains which do not intersect at the edges. A set of edges whose removal results in the formation of a disconnected graph is known as a cut. In each graph the largest number of cuts which do not intersect at the edges and which separate two vertices $ u $ and $ v $ is equal to the smallest number of edges of a simple chain connecting $ u $ and $ v $, i.e. to the distance $ d ( u , v) $ between $ u $ and $ v $.

References

[1] F. Harary, "Graph theory" , Addison-Wesley (1969) pp. Chapt. 9
[2] L.R. Ford, D.R. Fulkerson, "Flows in networks" , Princeton Univ. Press (1962)

Comments

The assertions in the last section can be derived from the maximum-flow-minimum-cut theorem of L. Ford and D. Fulkerson (see [2]). The first two are different versions of the vertex form of Menger's theorem (see [1]).

The maximum-flow-minimum-cut theorem, or the Ford–Fulkerson theorem, deals with a directed graph $ G $ for which for each arc $ e $ a capacity $ 0 \leq c _ {e} < \infty $ is specified. In addition, two special vertices, labeled $ Q, S $, are specified, called source and sink respectively, and there are no arcs leaving $ S $ or entering $ Q $. A flow on the graph is given by specifying for every arc (i.e. directed edge) a number $ 0 \leq f _ {e} \leq c _ {e} $ such that for every vertex $ P \neq Q, S $,

$$ \tag{* } \sum _ {a ( e) = P } f _ {e} = \ \sum _ {b ( e) = P } f _ {e} $$

where for an arc $ e $, $ a ( e) $ denotes its source vertex and $ b ( e) $ its target vertex. The maximum flow problem asks for a flow such that

$$ \sum _ {a ( e) = Q } f _ {e} $$

is maximized. In this setting a cut is a set of arcs whose removal results in a disconnected graph with $ Q $ in one component and $ S $ in another. The capacity of a cut is the sum of the capacities $ c _ {e} $ of the elements of the cut. The maximum-flow-minimum-cut theorem now says that the maximum flow attainable is equal to the minimal attainable capacity of a cut. The maximum flow problem can be formulated as a linear programming problem, and then the maximum-flow-minimum-cut theorem is an instance of the duality theorem of linear programming.

Recall that a chain in a non-oriented graph from $ v _ {0} $ to $ v _ {n} $ is a sequence $ v _ {0} e _ {0} v _ {1} \dots e _ {n - 1 } v _ {n} $ of alternating vertices and edges such that $ e _ {i} $ is an edge between $ v _ {i} $ and $ v _ {i + 1 } $ and such that all $ e _ {j} $ and all $ v _ {k} $, except possibly $ v _ {0} $ and $ v _ {n} $, are distinct. A $ vw $- disconnecting set or cut, where $ v, w $ are two vertices, is a set of edges whose removal results in a disconnected graph with $ v $ in one component and $ w $ in another. The edge form of Menger's theorem now says that for a connected graph the maximum number of edge-disjoint chains from $ v $ to $ w $ is equal to the minimum number of edges in a $ vw $- disconnecting set. The theorem was in fact first proved by Ford and Fulkerson (1955). A $ vw $- separating set is a set of vertices $ S $( not including $ v $ or $ w $) such that any chain from $ v $ to $ w $ passes through $ S $. The vertex form of Menger's theorem (Menger, 1928) now says that the maximum number of vertex-disjoint chains connecting distinct non-adjacent vertices $ v $ and $ w $ is equal to the minimal number of vertices in a $ vw $- separating set. Menger's theorem is closely related to the P. Hall marriage theorem; cf. Combinatorial analysis for that theorem.

References

[a1] W.T. Tutte, "Connectivity in graphs" , Oxford Univ. Press (1966)
[a2] R.J. Wilson, "Introduction to graph theory" , Longman (1985)
[a3] H.-J. Walther, "Ten applications of graph theory" , Reidel (1984) pp. Sect. 6.1
How to Cite This Entry:
Graph, connectivity of a. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Graph,_connectivity_of_a&oldid=12662
This article was adapted from an original article by A.A. Sapozhenko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article