FindVertexIndependentPaths

FindVertexIndependentPaths[g,s,t,k]

finds at most k vertex-independent paths from vertex s to vertex t in the graph g.

FindVertexIndependentPaths[{vw,},]

uses rules vw to specify the graph g.

Details

  • Vertex-independent paths are also known as independent paths or vertex disjoint paths.
  • FindVertexIndependentPaths returns a list of vertex-independent paths from s to t.
  • Each path is given as a list of vertices.
  • FindVertexIndependentPaths works with undirected graphs, directed graphs, multigraphs, and mixed graphs.

Examples

open allclose all

Basic Examples  (1)

Find a vertex-independent path between two individual vertices in a graph:

Show the path:

Scope  (6)

FindVertexIndependentPaths works with undirected graphs:

Directed graphs:

Multigraphs:

Mixed graphs:

Use rules to specify the graph:

FindVertexIndependentPaths works with large graphs:

Properties & Relations  (2)

FindVertexIndependentPaths only returns simple paths:

VertexConnectivity gives the maximum number of vertex-independent paths:

Possible Issues  (1)

Find a largest set of vertex-independent paths between two vertices:

Another vertex-independent path:

Introduced in 2014
 (10.0)
 |
Updated in 2015
 (10.3)