HaskellForMaths-0.4.8: Combinatorics, group theory, commutative algebra, non-commutative algebra

Safe Haskell | None
Language | Haskell98

Math.Combinatorics.GraphAuts

Synopsis

- isVertexTransitive :: Ord t => Graph t -> Bool
- isEdgeTransitive :: Ord t => Graph t -> Bool
- isArcTransitive :: Ord t => Graph t -> Bool
- is2ArcTransitive :: Ord t => Graph t -> Bool
- is3ArcTransitive :: Ord t => Graph t -> Bool
- is4ArcTransitive :: Ord t => Graph t -> Bool
- isnArcTransitive :: Ord t => Int -> Graph t -> Bool
- isDistanceTransitive :: Ord t => Graph t -> Bool
- graphAuts :: Ord a => Graph a -> [Permutation a]
- incidenceAuts :: (Ord p, Ord b) => Graph (Either p b) -> [Permutation p]
- graphAuts7 :: Ord a => Graph a -> ([a], [Permutation a])
- graphAuts8 :: Ord a => Graph a -> ([a], [Permutation a])
- incidenceAuts2 :: (Ord a, Ord b) => Graph (Either a b) -> ([Either a b], [Permutation (Either a b)])
- isGraphAut :: Ord t => Graph t -> Permutation t -> Bool
- isIncidenceAut :: (Ord p, Ord b) => Graph (Either p b) -> Permutation (Either p b) -> Bool
- graphIsos :: (Ord t, Ord t1) => Graph t1 -> Graph t -> [[(t1, t)]]
- incidenceIsos :: (Ord t, Ord t1, Ord t2, Ord t3) => Graph (Either t2 t) -> Graph (Either t3 t1) -> [[(t2, t3)]]
- isGraphIso :: (Ord a, Ord b) => Graph a -> Graph b -> Bool
- isIncidenceIso :: (Ord p1, Ord b1, Ord p2, Ord b2) => Graph (Either p1 b1) -> Graph (Either p2 b2) -> Bool

# Documentation

isVertexTransitive :: Ord t => Graph t -> Bool Source

A graph is vertex-transitive if its automorphism group acts transitively on the vertices. Thus, given any two distinct vertices, there is an automorphism mapping one to the other.

isEdgeTransitive :: Ord t => Graph t -> Bool Source

A graph is edge-transitive if its automorphism group acts transitively on the edges. Thus, given any two distinct edges, there is an automorphism mapping one to the other.

isArcTransitive :: Ord t => Graph t -> Bool Source

A graph is arc-transitive (or flag-transitive) if its automorphism group acts transitively on arcs. (An arc is an ordered pair of adjacent vertices.)

is2ArcTransitive :: Ord t => Graph t -> Bool Source

is3ArcTransitive :: Ord t => Graph t -> Bool Source

is4ArcTransitive :: Ord t => Graph t -> Bool Source

isnArcTransitive :: Ord t => Int -> Graph t -> Bool Source

A graph is n-arc-transitive if its automorphism group is transitive on n-arcs. (An n-arc is an ordered sequence (v0,...,vn) of adjacent vertices, with crossings allowed but not doubling back.)

isDistanceTransitive :: Ord t => Graph t -> Bool Source

A graph is distance transitive if given any two ordered pairs of vertices (u,u') and (v,v') with d(u,u') == d(v,v'), there is an automorphism of the graph that takes (u,u') to (v,v')

graphAuts :: Ord a => Graph a -> [Permutation a] Source

Given a graph g, `graphAuts g` returns a strong generating set for the automorphism group of g.

incidenceAuts :: (Ord p, Ord b) => Graph (Either p b) -> [Permutation p] Source

Given the incidence graph of an incidence structure between points and blocks (for example, a set system), `incidenceAuts g` returns a strong generating set for the automorphism group of the incidence structure. The generators are represented as permutations of the points. The incidence graph should be represented with the points on the left and the blocks on the right.

graphAuts7 :: Ord a => Graph a -> ([a], [Permutation a]) Source

graphAuts8 :: Ord a => Graph a -> ([a], [Permutation a]) Source

incidenceAuts2 :: (Ord a, Ord b) => Graph (Either a b) -> ([Either a b], [Permutation (Either a b)]) Source

isGraphAut :: Ord t => Graph t -> Permutation t -> Bool Source

Is the permutation an automorphism of the graph?

isIncidenceAut :: (Ord p, Ord b) => Graph (Either p b) -> Permutation (Either p b) -> Bool Source

Is the permutation an automorphism of the incidence structure represented by the graph? (Note that an incidence graph colours points as Left, blocks as Right, and a permutation that swaps points and blocks, even if it is an automorphism of the graph, does not represent an automorphism of the incidence structure. Instead, a point-block crossover is called a duality.)

graphIsos :: (Ord t, Ord t1) => Graph t1 -> Graph t -> [[(t1, t)]] Source

incidenceIsos :: (Ord t, Ord t1, Ord t2, Ord t3) => Graph (Either t2 t) -> Graph (Either t3 t1) -> [[(t2, t3)]] Source

isGraphIso :: (Ord a, Ord b) => Graph a -> Graph b -> Bool Source

Are the two graphs isomorphic?

isIncidenceIso :: (Ord p1, Ord b1, Ord p2, Ord b2) => Graph (Either p1 b1) -> Graph (Either p2 b2) -> Bool Source

Are the two incidence structures represented by these incidence graphs isomorphic?