Introduction

 
Construction of Multigraphs

      Construction of a General Multigraph
            MultiGraph<n | edges > : RngIntElt, List -> GrphMultUnd, GrphVertSet, GrphEdgeSet
            Example MultiGraph_GrphMultUnd_Constr (H163E1)

      Construction of a General Multidigraph
            MultiDigraph<n | edges > : RngIntElt, List -> GrphMultDir, GrphVertSet, GrphEdgeSet
            Example MultiGraph_GrphMultDir_Constr (H163E2)

      Printing of a Multi(di)graph

      Operations on the Support
            Support(G) : GrphMult -> SetIndx
            ChangeSupport(G, S) : GrphMult, SetIndx -> GrphMult, GrphVertSet, GrphEdgeSet
            ChangeSupport(~G, S) : GrphMult, SetIndx ->
            StandardGraph(G) : GrphMult -> GrphMult
            Example MultiGraph_GrphMult_Support (H163E3)

 
The Vertex--Set and Edge--Set of Multigraphs
      EdgeIndices(u, v) : GrphVert, GrphVert -> SeqEnum
      EdgeMultiplicity(u, v) : GrphVert, GrphVert -> RngIntElt
      Edges(u, v) : GrphVert, GrphVert -> SeqEnum
      IncidentEdges(u) : GrphVert -> SetEnum
      E ! < { u, v }, i > : GrphEdgeSet, < . > -> GrphEdge
      E ! < [ u, v ], i > : GrphEdgeSet, < . > -> GrphEdge
      pE.i {E . i} : GrphEdgeSet, RngIntElt -> GrphEdge
      EndVertices(e) : GrphEdge ->{ GrphVert, GrphVert }
      InitialVertex(e) : GrphEdge -> GrphVert
      TerminalVertex(e) : GrphEdge -> GrphVert
      Index(e) : GrphEdge -> RngIntElt
      s eq t : GrphEdge, GrphEdge -> BoolElt
      Example MultiGraph_GrphMult_Edges (H163E4)

 
Vertex and Edge Decorations

      Vertex Decorations: Labels
            AssignLabel(~G, u, l) : GrphMult, GrphVert, . ->
            AssignLabels(~G, S, L) : GrphMult, [GrphVert], SeqEnum ->
            AssignVertexLabels(~G, L) : GrphMult, SeqEnum ->
            IsLabelled(u) : GrphVert -> BoolElt
            IsLabelled(V) : GrphVertSet -> BoolElt
            IsVertexLabelled(G) : GrphMult -> BoolElt
            Label(u) : GrphVert -> .
            Labels(S) : [GrphVert] -> SeqEnum
            Labels(V) : GrphVertSet -> SeqEnum
            VertexLabels(G) : GrphMult -> SeqEnum
            DeleteLabel(~G, u) : GrphMult, GrphVert ->
            DeleteLabels(~G, S) : GrphMult, [GrphVert] ->
            DeleteVertexLabels(~G) : GrphMult ->

      Edge Decorations

            Assigning Edge Decorations
                  AssignLabel(~G, e, l) : GrphMult, GrphEdge, . ->
                  AssignLabels(~G, S, D) : GrphMult, [GrphEdge], SeqEnum ->
                  AssignEdgeLabels(~G, D) : GrphMult, SeqEnum ->

            Testing for Edge Decorations
                  IsLabelled(e) : GrphEdge -> BoolElt
                  IsLabelled(E) : GrphEdgeSet -> BoolElt
                  IsEdgeLabelled(G) : GrphMult -> BoolElt
                  IsCapacitated(E) : GrphEdgeSet -> BoolElt
                  IsEdgeCapacitated(G) : GrphMult -> BoolElt
                  IsWeighted(E) : GrphEdgeSet -> BoolElt
                  IsEdgeWeighted(G) : GrphMult -> BoolElt

            Reading Edge Decorations
                  Label(e) : GrphEdge -> .
                  Capacity(e) : GrphEdge -> RngIntElt
                  Weight(e) : GrphEdge -> RngElt
                  Labels(S) : [GrphEdge] -> SeqEnum
                  Labels(E) : GrphEdgeSet -> SeqEnum
                  EdgeLabels(G) : GrphMult -> SeqEnum

            Deleting Edge Decorations
                  DeleteLabel(~G, e) : GrphMult, GrphEdge ->
                  DeleteLabels(~G, S) : GrphMult, [GrphEdge] ->
                  DeleteEdgeLabels(~G) : GrphMult ->

      Unlabelled, or Uncapacitated, or Unweighted Graphs
            UnlabelledGraph(G) : GrphMult -> GrphMult
            UncapacitatedGraph(G) : GrphMult -> GrphMult
            UnweightedGraph(G) : GrphMult -> GrphMult
            Example MultiGraph_GrphMult_Labels (H163E5)
            Example MultiGraph_CayleyGraph (H163E6)
            Example MultiGraph_GrphMult_EdgesDecs (H163E7)

 
Standard Construction for Multigraphs

      Subgraphs
            sub< G | list > : GrphMult, List -> GrphMult, GrphVertSet, GrphEdgeSet
            Example MultiGraph_GrphMult_Sub (H163E8)

      Incremental Construction of Multigraphs

            Adding Vertices
                  G + n : GrphMult, RngIntElt -> GrphMult
                  G +:= n : GrphMult, RngIntElt ->
                  AddVertex(~G, l) : GrphMult, . ->
                  AddVertices(~G, n, L) : GrphMult, RngIntElt, SeqEnum ->

            Removing Vertices
                  G - v : GrphMult, GrphVert -> GrphMult
                  G -:= v : GrphMult, GrphVert ->

            Adding Edges
                  G + { u, v } : GrphMultUnd, { { GrphVert, GrphVert } } -> GrphMultUnd, GrphEdge
                  G + { { u, v } } : GrphMultUnd, { { GrphVert, GrphVert } } -> GrphMultUnd
                  G +:= { u, v } : GrphMultUnd, { GrphVert, GrphVert } ->
                  AddEdge(G, u, v) : GrphMult, GrphVert, GrphVert -> GrphMult, GrphEdge
                  AddEdge(G, u, v, l) : GrphMultUnd, GrphVert, GrphVert, . -> GrphMult, GrphEdge
                  AddEdge(G, u, v, c) : GrphNet, GrphVert, RngIntElt, . -> GrphNet, GrphEdge
                  AddEdge(G, u, v, c, l) : GrphNet, GrphVert, GrphVert, RngIntElt, . -> GrphNet, GrphEdge
                  AddEdge(~G, u, v) : GrphMult, GrphVert, GrphVert ->
                  AddEdges(G, S) : GrphMultUnd, { { GrphVert, GrphVert } } -> GrphMultUnd
                  AddEdges(G, S, L) : GrphMult, SeqEnum, SeqEnum -> GrphMult
                  AddEdges(~G, S) : GrphMultUnd, { { GrphVert, GrphVert } } ->

            Removing Edges
                  G - e : GrphMult, GrphEdge -> GrphMult
                  G - { { u, v } } : GrphMultUnd, { { GrphVert, GrphVert rbrace } -> GrphMultUnd
                  G -:= e : GrphMult, GrphEdge ->

      Vertex Insertion, Contraction
            InsertVertex(e) : GrphEdge -> GrphMult
            InsertVertex(T) : { GrphEdge } -> GrphMult
            Contract(e) : GrphEdge -> GrphMult
            Contract(u, v) : GrphVert, GrphVert -> GrphMult
            Contract(S) : { GrphVert } -> GrphMult

      Unions of Multigraphs
            Union(G, H) : GrphMultUnd, GrphMultUnd -> GrphMultUnd
            Union(N, H) : GrphNet, GrphNet -> GrphNet
            & join S : [ MultiUnd ] -> GrphMultUnd
            EdgeUnion(G, H) : GrphMultUnd, GrphMultUnd -> GrphMultUnd
            EdgeUnion(N, H) : GrphNet, GrphNet -> GrphNet

 
Conversion Functions

      Orientated Graphs
            OrientatedGraph(G) : GrphMultUnd -> GrphMultDir

      Converse
            Converse(G) : GrphMultDir -> GrphMultDir

      Converting between Simple Graphs and Multigraphs
            UnderlyingGraph(G) : GrphMult -> GrphUnd, GrphVertSet, GrphEdgeSet
            UnderlyingDigraph(G) : GrphMult-> GrphDir, GrphVertSet, GrphEdgeSet
            UnderlyingMultiGraph(G) : Grph -> GrphMultUnd, GrphVertSet, GrphEdgeSet
            UnderlyingMultiDigraph(G) : Grph -> GrphMultDir, GrphVertSet, GrphEdgeSet
            UnderlyingNetwork(G) : Grph -> GrphNet, GrphVertSet, GrphEdgeSet

 
Elementary Invariants and Predicates for Multigraphs
      Order(G) : GrphMult -> RngIntElt
      Size(G) : GrphMult -> RngIntElt
      u adj v : GrphVert, GrphVert -> BoolElt
      e adj f : GrphEdge, GrphEdge -> BoolElt
      u notadj v : GrphVert, GrphVert -> BoolElt
      e notadj f : GrphEdge, GrphEdge -> BoolElt
      u in e : GrphVert, GrphEdge -> BoolElt
      u notin e : GrphVert, GrphEdge -> BoolElt
      G eq H : GrphMultUnd, GrphMultUnd -> BoolElt
      IsSubgraph(G, H) : GrphMultUnd, GrphMultUnd -> BoolElt
      IsBipartite(G) : GrphMultUnd -> BoolElt
      Bipartition(G) : GrphMultUnd -> [ { GrphVert } ]
      IsRegular(G) : GrphMult -> BoolElt
      IsComplete(G) : GrphMult -> BoolElt
      IsEmpty(G) : GrphMult -> BoolElt
      IsNull(G) : GrphMult -> BoolElt
      IsSimple(G) : GrphMult -> BoolElt
      IsUndirected(G) : GrphMult -> BoolElt
      IsDirected(G) : GrphMult -> BoolElt

 
Adjacency and Degree

      Adjacency and Degree Functions for Mul-tigraphs
            Degree(u) : GrphVert -> RngIntElt
            Alldeg(G, n) : GrphMultUnd, RngIntElt -> { GrphVert }
            MaximumDegree(G) : GrphMultUnd -> RngIntElt, GrphVert
            MinimumDegree(G) : GrphMultUnd -> RngIntElt, GrphVert
            DegreeSequence(G) : GrphMultUnd -> [ { GrphVert } ]
            Neighbours(u) : GrphVert -> { GrphVert }
            IncidentEdges(u) : GrphVert -> { GrphEdge }

      Adjacency and Degree Functions for Multidigraphs
            InDegree(u) : GrphVert -> RngIntElt
            OutDegree(u) : GrphVert -> RngIntElt
            MaximumInDegree(G) : GrphMultDir -> RngIntElt, GrphVert
            MinimumInDegree(G) : GrphMultDir -> RngIntElt, GrphVert
            MaximumOutDegree(G) : GrphMultDir -> RngIntElt, GrphVert
            MinimumOutDegree(G) : GrphMultDir -> RngIntElt, GrphVert
            Degree(u) : GrphVert -> RngIntElt
            MaximumDegree(G) : GrphMultDir -> RngIntElt, GrphVert
            MinimumDegree(G) : GrphMultDir -> RngIntElt, GrphVert
            Alldeg(G, n) : GrphMultDir, RngIntElt -> { GrphVert }
            DegreeSequence(G) : GrphMultDir -> [ GrphVert ]
            InNeighbours(u) : GrphVert -> { GrphVert }
            OutNeighbours(u) : GrphVert -> { GrphVert }
            IncidentEdges(u) : GrphVert -> { GrphEdge }

 
Connectedness

      Connectedness in a Multigraph
            IsConnected(G) : GrphMultUnd -> BoolElt
            Components(G) : GrphMultUnd -> [ { GrphVert } ]
            Component(u) : GrphVert -> GrphMult
            IsSeparable(G) : GrphMultUnd -> BoolElt
            IsBiconnected(G) : GrphMultUnd -> BoolElt
            CutVertices(G) : GrphMultUnd -> { GrphVert }
            Bicomponents(G) : GrphMultUnd -> [ { GrphVert } ]

      Connectedness in a Multidigraph
            IsStronglyConnected(G) : GrphMultDir -> BoolElt
            IsWeaklyConnected(G) : GrphMultDir -> BoolElt
            StronglyConnectedComponents(G) : GrphMultDir -> [ { GrphVert } ]
            Component(u) : GrphVert -> GrphMult

      Triconnectivity for Multigraphs
            IsTriconnected(G) : GrphMultUnd -> BoolElt
            Splitcomponents(G) : GrphMultUnd -> [ { GrphVert } ], [ [ GrphVert ]]
            SeparationVertices(G) : GrphMultUnd -> [ [ GrphVert ]], [ { GrphVert } ]

      Maximum Matching in Bipartite Multigraphs
            MaximumMatching(G : parameters) : GrphMultUnd -> [ { GrphEdge rbrace ]

      General Vertex and Edge Connectivity in Multigraphs and Multidigraphs
            VertexSeparator(G : parameters) : GrphMult -> [ GrphVert ]
            VertexConnectivity(G : parameters) : GrphMult -> RngIntElt, [ GrphVert ]
            IsKVertexConnected(G, k : parameters) : GrphMult, RngIntElt -> BoolElt
            EdgeSeparator(G : parameters) : GrphMult -> [ GrphEdge ]
            EdgeConnectivity(G : parameters) : GrphMult -> RngIntElt, [ GrphEdge ]
            IsKEdgeConnected(G, k : parameters) : GrphMult, RngIntElt -> BoolElt
            Example MultiGraph_GrphMult_Conn (H163E9)

 
Spanning Trees
      SpanningTree(G) : GrphMultUnd -> GrphMultUnd, GrphVertSet, GrphEdgeSet
      SpanningForest(G) : GrphMult -> GrphMult, GrphVertSet, GrphEdgeSet
      BreadthFirstSearchTree(u) : GrphVert -> GrphMult, GrphVertSet, GrphEdgeSet
      DepthFirstSearchTree(u) : GrphVert -> GrphMult, GrphVertSet, GrphEdgeSet, SeqEnum

 
Planar Graphs
      IsPlanar(G) : GrphMultUnd -> BoolElt, GrphMultUnd
      Obstruction(G) : GrphMultUnd -> GrphMultUnd
      IsHomeomorphic(G: parameters) : GrphMultUnd -> BoolElt
      Faces(G) : GrphMultUnd -> SeqEnum[GrphVert]
      Face(u, v) : GrphVert, GrphVert -> SeqEnum
      Face(e) : GrphEdge -> SeqEnum
      NFaces(G) : GrphMultUnd -> RngIntElt
      Embedding(G) : GrphMultUnd -> SeqEnum
      Embedding(v) : GrphVert -> SeqEnum
      Example MultiGraph_GrphMult_Planar (H163E10)
      Example MultiGraph_GrphMult_Planar_Dual (H163E11)

 
Distances, Shortest Paths and Minimum Weight Trees
      Reachable(u, v : parameters) : GrphVert, GrphVert -> BoolElt, RngElt
      Distance(u, v : parameters) : GrphVert, GrphVert -> RngElt
      Distances(u : parameters) : GrphVert -> Eseq
      PathExists(u, v : parameters) : GrphVert, GrphVert -> BoolElt, Eseq
      Path(u, v : parameters) : GrphVert, GrphVert -> Eseq
      Paths(u : parameters) : GrphVert -> Eseq
      GeodesicExists(u, v : parameters) : GrphVert, GrphVert -> BoolElt, Eseq
      Geodesic(u, v : parameters) : GrphVert, GrphVert -> Eseq
      Geodesics(u : parameters) : GrphVert -> Eseq
      HasNegativeWeightCycle(u : parameters) : GrphVert -> BoolElt
      HasNegativeWeightCycle(G) : Grph -> BoolElt
      AllPairsShortestPaths(G : parameters) : Grph -> SeqEnum, SeqEnum
      MinimumWeightTree(u : parameters) : GrphVert -> SeqEnum
      Example MultiGraph_GrphMult_ShortP (H163E12)
      Example MultiGraph_GrphMult_MinW (H163E13)

 
Bibliography

[Next][Prev] [Right] [____] [Up] [Index] [Root]