GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : GraphTheory/EdgeConnectivity

GraphTheory

  

EdgeConnectivity

  

VertexConnectivity

 

Calling Sequence

Parameters

Description

Examples

Calling Sequence

EdgeConnectivity(G)

VertexConnectivity(G)

Parameters

G

-

graph

Description

• 

EdgeConnectivity returns the edge connectivity of a graph, that is the minimum number of edges whose removal disconnects the graph. A set of such edges is called an edge-cut.  You can use the IsCutSet command to test whether a set of edges is an edge-cut.

• 

VertexConnectivity returns the vertex connectivity of a graph, that is the minimum number of vertices whose removal disconnects the graph.

• 

By an elementary theorem of graph theory, the vertex connectivity of a graph is less than or equal to the edge connectivity, which is less than or equal to the minimum degree.

Examples

withGraphTheory:

GGraph1,2,1,3,1,4,2,3,3,4,4,5,4,6,5,6

GGraph 1: an undirected unweighted graph with 6 vertices and 8 edge(s)

(1)

DrawGraphG

EdgeConnectivityG

2

(2)

VertexConnectivityG

1

(3)

MinimumDegreeG

2

(4)

withSpecialGraphs:

PPetersenGraph

PGraph 2: an undirected unweighted graph with 10 vertices and 15 edge(s)

(5)

VertexConnectivityP

3

(6)

EdgeConnectivityP

3

(7)

MinimumDegreeP

3

(8)

See Also

ArticulationPoints

DeleteEdge

DeleteVertex

IsConnected

IsCutSet

MinimumDegree