-
Notifications
You must be signed in to change notification settings - Fork 1
/
NewCombinatorica.m
7383 lines (6520 loc) · 331 KB
/
NewCombinatorica.m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
(* :Title: Combinatorica *)
(* :Authors: Sriram V. Pemmaraju and Steven S. Skiena*)
(* :Summary:
This package contains all the programs from the book, "Computational
Discrete Mathematics: Combinatorics and Graph Theory in Mathematica",
by Sriram V. Pemmaraju and Steven S. Skiena, Cambridge University Press,
2003.
*)
(* :Discussion:
The programs from the book "Computational Discrete Mathematics: Combinatorics
and Graph Theory with Mathematica" are available at www.combinatorica.com.
Any comments or bug reports should be forwarded to one of the following:
Sriram Pemmaraju
Department of Computer Science
University of Iowa
Iowa City, IA 52242
(319)-353-2956
Steven Skiena
Department of Computer Science
State University of New York
Stony Brook, NY 11794-4400
(631)-632-9026
*)
(* :Context: DiscreteMath`Combinatorica`
*)
(* :Package Version: 2.0.0
*)
(* :Copyright: Copyright 2000-2003 by Sriram V. Pemmaraju and Steven S. Skiena
*)
(*
This package may be copied in its entirety for nonprofit purposes only.
Sale, other than for the direct cost of the media, is prohibited. This
copyright notice must accompany all copies.
The authors, Wolfram Research, and Cambridge University Press
make no representations, express or implied, with respect to this
documentation, or the software it describes and contains, including
without limitations, any implied warranties of mechantability or fitness
for a particular purpose, all of which are expressly disclaimed. The
authors, Wolfram Research, or Cambridge University Press, their licensees,
distributors and dealers shall in no event be liable for any indirect,
incidental, or consequential damages.
*)
(* :History:
Version 2.0 most code rewritten Sriram V. Pemmaraju, 2000-2002
Too many changes to describe here. Read the book!
Version 1.1 modification by ECM, March 1996.
Replaced K with CompleteGraph because K is now the
default generic name for the summation index in
symbolic sum.
Added CombinatorialFunctions.m and Permutations.m to
BeginPackage, and commented out CatalanNumber,
PermutationQ, ToCycles, FromCycles, and
RandomPermutation so there would be no shadowing of
symbols among the DiscreteMath packages.
Replaced old BinarySearch with new code by Paul Abbott
correctly implementing binary search.
Version 1.0 by Steven S. Skiena, April 1995.
Version .9 by Steven S. Skiena, February 1992.
Version .8 by Steven S. Skiena, July 1991.
Version .7 by Steven S. Skiena, January 1991.
Version .6 by Steven S. Skiena, June 1990.
*)
(*
Acknowledgements:
WRI people who helped: John Novak, Eric Weisstein, Arnoud Buzing,
Shiral Devmal, Anna Pakin, Andy Shiekh, Darren Glosemeyer, Ranjani
Krishnan, Daniel Lichtblau,
Robby Villegas, Stephen Wolfram
Others who helped: Eugene Curtin, Levon LLoyd, Joan Trias, Kaushal
Kurapati, students at Iowa, students at IIT Bombay
*)
(* :Keywords:
adjacency, automorphism, chromatic, clique, coloring,
combination, composition, connected components, connectivity, cycle,
de Bruijn, degree, derangement, Dijkstra, Durfee,
embedding, equivalence, Eulerian, Ferrers,
geodesic, graph, Gray code, group, Hamiltonian cycle, Harary, Hasse,
heap, hypercube, interval, inversion, involution, isomorphism,
Josephus, network,
partition, perfect, permutation, planar graph, pseudograph,
self-loop, sequence, signature, simple, spanning tree,
stable marriage, star, Stirling,
transitive closure, traveling salesman tour, tree, Turan,
vertex cover, wheel, Young tableau
*)
(* :Source:
Sriram V. Pemmaraju and Steven S. Skiena
Computational Discrete Mathematics: Combinatorics
and Graph Theory in Mathematica,
*)
(* :Mathematica Version: 4.0
*)
BeginPackage["DiscreteMath`Combinatorica`",
"DiscreteMath`CombinatorialFunctions`",
(* needed for CatalanNumber *)
"Graphics`Colors`",
(* needed for the enhanced graphics routines such as ShowGraph *)
"Graphics`Arrow`",
(* needed for drawing directed edges *)
"Statistics`DiscreteDistributions`"
(* needed for generating random graph*)
]
Unprotect[
AcyclicQ,
AddEdge,
AddEdges,
AddVertex,
AddVertices,
Algorithm,
AllPairsShortestPath,
AlternatingGroup,
AlternatingGroupIndex,
AlternatingPaths,
AnimateGraph,
AntiSymmetricQ,
Approximate,
ApproximateVertexCover,
ArticulationVertices,
Automorphisms,
Backtrack,
BellB,
BellmanFord,
BiconnectedComponents,
BiconnectedQ,
BinarySearch,
BinarySubsets,
BipartiteMatching,
BipartiteMatchingAndCover,
BipartiteQ,
BooleanAlgebra,
Box,
BreadthFirstTraversal,
Brelaz,
BrelazColoring,
Bridges,
ButterflyGraph,
ToCanonicalSetPartition,
CageGraph,
CartesianProduct,
Center,
ChangeEdges,
ChangeVertices,
ChromaticNumber,
ChromaticPolynomial,
ChvatalGraph,
CirculantGraph,
CircularEmbedding,
CircularVertices,
CliqueQ,
CoarserSetPartitionQ,
CodeToLabeledTree,
Cofactor,
CompleteBinaryTree,
CompleteKaryTree,
CompleteKPartiteGraph,
CompleteGraph,
CompleteQ,
Compositions,
ConnectedComponents,
ConnectedQ,
ConstructTableau,
Contract,
CostOfPath,
CoxeterGraph,
CubeConnectedCycle,
CubicalGraph,
Cut,
Cycle,
Cycles,
CycleIndex,
CycleStructure,
Cyclic,
CyclicGroup,
CyclicGroupIndex,
DeBruijnGraph,
DeBruijnSequence,
Degrees,
DegreesOf2Neighborhood,
DegreeSequence,
DeleteCycle,
DeleteEdge,
DeleteEdges,
DeleteFromTableau,
DeleteVertex,
DeleteVertices,
DepthFirstTraversal,
DerangementQ,
Derangements,
Diameter,
Dihedral,
DihedralGroup,
DihedralGroupIndex,
Dijkstra,
DilateVertices,
Directed,
Distances,
DistinctPermutations,
Distribution,
DodecahedralGraph,
DominatingIntegerPartitionQ,
DominationLattice,
DurfeeSquare,
Eccentricity,
Edge,
EdgeChromaticNumber,
EdgeColor,
EdgeColoring,
EdgeConnectivity,
EdgeDirection,
EdgeLabel,
EdgeLabelColor,
EdgeLabelPosition,
Edges,
EdgeStyle,
EdgeWeight,
Element,
EmptyGraph,
EmptyQ,
EncroachingListSet,
EquivalenceClasses,
EquivalenceRelationQ,
Equivalences,
Euclidean,
Eulerian,
EulerianCycle,
EulerianQ,
ExactRandomGraph,
ExpandGraph,
ExtractCycles,
FerrersDiagram,
FindCycle,
FindSet,
FiniteGraphs,
FirstLexicographicTableau,
FolkmanGraph,
FranklinGraph,
FruchtGraph,
FromAdjacencyLists,
FromAdjacencyMatrix,
FromCycles,
FromInversionVector,
FromOrderedPairs,
FromUnorderedPairs,
FunctionalGraph,
GeneralizedPetersenGraph,
GetEdgeLabels,
GetEdgeWeights,
GetVertexLabels,
GetVertexWeights,
Girth,
GraphCenter,
GraphComplement,
GraphDifference,
GraphicQ,
GraphIntersection,
GraphJoin,
GraphOptions,
GraphPolynomial,
GraphPower,
GraphProduct,
GraphSum,
GraphUnion,
GrayCode,
GrayCodeSubsets,
GrayCodeKSubsets,
GrayGraph,
Greedy,
GreedyVertexCover,
GridGraph,
GrotztschGraph,
HamiltonianCycle,
HamiltonianPath,
HamiltonianQ,
Harary,
HasseDiagram,
Heapify,
HeapSort,
HeawoodGraph,
HerschelGraph,
HideCycles,
HighlightedEdgeColors,
HighlightedEdgeStyle,
HighlightedVertexColors,
HighlightedVertexStyle,
Highlight,
Hypercube,
IcosahedralGraph,
IdenticalQ,
IdentityPermutation,
IncidenceMatrix,
InDegree,
IndependentSetQ,
Index,
InduceSubgraph,
InitializeUnionFind,
InsertIntoTableau,
IntervalGraph,
Invariants,
InversePermutation,
InversionPoset,
Inversions,
InvolutionQ,
Involutions,
IsomorphicQ,
Isomorphism,
IsomorphismQ,
Josephus,
KnightsTourGraph,
KSetPartitions,
KSubsetGroup,
KSubsetGroupIndex,
KSubsets,
LNorm,
LabeledTreeToCode,
Large,
LastLexicographicTableau,
LexicographicPermutations,
LexicographicSubsets,
LeviGraph,
LineGraph,
ListGraphs,
ListNecklaces,
LongestIncreasingSubsequence,
LoopPosition,
LowerLeft,
LowerRight,
M,
MakeDirected,
MakeGraph,
MakeSimple,
MakeUndirected,
MaximalMatching,
MaximumAntichain,
MaximumClique,
MaximumIndependentSet,
MaximumSpanningTree,
McGeeGraph,
MeredithGraph,
MinimumChainPartition,
MinimumChangePermutations,
MinimumSpanningTree,
MinimumVertexColoring,
MinimumVertexCover,
MultipleEdgesQ,
MultiplicationTable,
MycielskiGraph,
NecklacePolynomial,
Neighborhood,
NetworkFlow,
NetworkFlowEdges,
NextBinarySubset,
NextComposition,
NextGrayCodeSubset,
NextKSubset,
NextLexicographicSubset,
NextPartition,
NextPermutation,
NextSubset,
NextTableau,
NoMultipleEdges,
NonLineGraphs,
NoPerfectMatchingGraph,
Normal,
NormalDashed,
NormalizeVertices,
NoSelfLoops,
NthPair,
NthPermutation,
NthSubset,
NumberOfCompositions,
NumberOfDerangements,
NumberOfDirectedGraphs,
NumberOfGraphs,
NumberOfInvolutions,
NumberOf2Paths,
NumberOfKPaths,
NumberOfNecklaces,
NumberOfPartitions,
NumberOfPermutationsByCycles,
NumberOfPermutationsByInversions,
NumberOfPermutationsByType,
NumberOfSpanningTrees,
NumberOfTableaux,
OctahedralGraph,
OddGraph,
One,
Optimum,
OrbitInventory,
OrbitRepresentatives,
Orbits,
Ordered,
OrientGraph,
OutDegree,
PairGroup,
PairGroupIndex,
Parent,
ParentsToPaths,
PartialOrderQ,
PartitionLattice,
PartitionQ,
Partitions,
Path,
PerfectQ,
PermutationGraph,
PermutationGroupQ,
PermutationQ,
PermutationToTableaux,
PermutationType,
PermutationWithCycle,
Permute,
PermuteSubgraph,
PetersenGraph,
PlanarQ,
PlotRange,
Polya,
PseudographQ,
RadialEmbedding,
Radius,
RandomComposition,
RandomGraph,
RandomHeap,
RandomInteger,
RandomKSetPartition,
RandomKSubset,
RandomPartition,
RandomPermutation,
RandomRGF,
RandomSetPartition,
RandomSubset,
RandomTableau,
RandomTree,
RandomVertices,
RankBinarySubset,
RankedEmbedding,
RankGraph,
RankGrayCodeSubset,
RankKSetPartition,
RankKSubset,
RankPermutation,
RankRGF,
RankSetPartition,
RankSubset,
ReadGraph,
RealizeDegreeSequence,
ReflexiveQ,
RegularGraph,
RegularQ,
RemoveMultipleEdges,
RemoveSelfLoops,
ResidualFlowGraph,
RevealCycles,
ReverseEdges,
RGFQ,
RGFs,
RGFToSetPartition,
RobertsonGraph,
RootedEmbedding,
RotateVertices,
Runs,
SamenessRelation,
SelectionSort,
SelfComplementaryQ,
SelfLoopsQ,
SetEdgeWeights,
SetGraphOptions,
SetPartitions,
SetPartitionListViaRGF,
SetPartitionQ,
SetPartitionToRGF,
SetEdgeLabels,
SetVertexLabels,
SetVertexWeights,
ShakeGraph,
ShortestPath,
ShortestPathSpanningTree,
ShowLabeledGraph,
ShowGraph,
ShowGraphArray,
ShuffleExchangeGraph,
SignaturePermutation,
Simple,
SimpleQ,
Small,
SmallestCyclicGroupGraph,
Spectrum,
SpringEmbedding,
StableMarriage,
Star,
StirlingFirst,
StirlingSecond,
Strings,
Strong,
StronglyConnectedComponents,
Subsets,
SymmetricGroup,
SymmetricGroupIndex,
SymmetricQ,
TableauClasses,
TableauQ,
Tableaux,
TableauxToPermutation,
TetrahedralGraph,
Thick,
ThickDashed,
Thin,
ThinDashed,
ThomassenGraph,
ToAdjacencyLists,
ToAdjacencyMatrix,
ToCycles,
ToInversionVector,
ToOrderedPairs,
TopologicalSort,
ToUnorderedPairs,
TransitiveClosure,
TransitiveQ,
TransitiveReduction,
TranslateVertices,
TransposePartition,
TransposeTableau,
TravelingSalesmanBounds,
TravelingSalesman,
TreeIsomorphismQ,
TreeQ,
TreeToCertificate,
TriangleInequalityQ,
Turan,
TutteGraph,
TwoColoring,
Type,
Undirected,
UndirectedQ,
UnionSet,
Uniquely3ColorableGraph,
UnitransitiveGraph,
UnrankBinarySubset,
UnrankGrayCodeSubset,
UnrankKSetPartition,
UnrankKSubset,
UnrankPermutation,
UnrankRGF,
UnrankSetPartition,
UnrankSubset,
UnweightedQ,
UpperLeft,
UpperRight,
V,
VertexColor,
VertexColoring,
VertexConnectivity,
VertexConnectivityGraph,
VertexCover,
VertexCoverQ,
VertexLabel,
VertexLabelColor,
VertexNumber,
VertexNumberColor,
VertexStyle,
VertexWeight,
Vertices,
WaltherGraph,
Weak,
WeaklyConnectedComponents,
WeightingFunction,
WeightRange,
Wheel,
WriteGraph,
Zoom
]
AcyclicQ::usage = "AcyclicQ[g] yields True if graph g is acyclic."
AddEdge::usage = "AddEdge[g, e] returns a graph g with the new edge e added. e can have the form {a, b} or the form {{a, b}, options}."
AddEdges::usage = "AddEdges[g, edgeList] gives graph g with the new edges in edgeList added. edgeList can have the form {a, b} to add a single edge {a, b} or the form {{a, b}, {c, d}, ...}, to add edges {a, b}, {c, d}, ... or the form { {{a, b}, x}, {{c, d}, y}, ...}, where x and y can specify graphics information associated with {a, b} and {c, d}, respectively."
AddVertex::usage = "AddVertex[g] adds one disconnected vertex to graph g. AddVertex[g, v] adds to g a vertex with coordinates specified by v."
AddVertices::usage = "AddVertices[g, n] adds n disconnected vertices to graph g. AddVertices[g, vList] adds vertices in vList to g. vList contains embedding and graphics information and can have the form {x, y} or {{x1, y1}, {x2, y2}...} or the form {{{x1, y1}, g1}, {{x2, y2}, g2},...}, where {x, y}, {x1, y1}, and {x2, y2} are point coordinates and g1 and g2 are graphics information associated with vertices."
Algorithm::usage = "Algorithm is an option that informs functions such as ShortestPath, VertexColoring, and VertexCover about which algorithm to use."
AllPairsShortestPath::usage = "AllPairsShortestPath[g] gives a matrix, where the (i, j)th entry is the length of a shortest path in g between vertices i and j. AllPairsShortestPath[g, Parent] returns a three-dimensional matrix with dimensions 2 * V[g] * V[g], in which the (1, i, j)th entry is the length of a shortest path from i to j and the (2, i, j)th entry is the predecessor of j in a shortest path from i to j."
$NewMessage[ All, "usage"] (* reset the usage of All to the System usage *)
If[StringQ[All::usage], All::usage = StringJoin[ All::usage, " All is also an option to certain Combinatorica functions specifying that all solutions should be returned, instead of just the first one."]]
AlternatingGroup::usage = "AlternatingGroup[n] generates the set of even-size n permutations, the alternating group on n symbols. AlternatingGroup[l] generates the set of even permutations of the list l."
AlternatingGroupIndex::usage = "AlternatingGroupIndex[n, x] gives the cycle index of the alternating group of size n permutations as a polynomial in the symbols x[1], x[2], ..., x[n]."
AlternatingPaths::usage = "AlternatingPaths[g, start, ME] returns the alternating paths in graph g with respect to the matching ME, starting at the vertices in the list start. The paths are returned in the form of a forest containing trees rooted at vertices in start."
AnimateGraph::usage = "AnimateGraph[g, l] displays graph g with each element in the list l successively highlighted. Here l is a list containing vertices and edges of g. An optional flag, which takes on the values All and One, can be used to inform the function about whether objects highlighted earlier will continue to be highlighted or not. The default value of flag is All. All the options allowed by the function Highlight are permitted by AnimateGraph, as well. See the usage message of Highlight for more details."
AntiSymmetricQ::usage = "AntiSymmetricQ[g] yields True if the adjacency matrix of g represents an anti-symmetric binary relation."
Approximate::usage = "Approximate is a value that the option Algorithm can take in calls to functions such as VertexCover, telling it to use an approximation algorithm."
ApproximateVertexCover::usage = "ApproximateVertexCover[g] produces a vertex cover of graph g whose size is guaranteed to be within twice the optimal size."
ArticulationVertices::usage = "ArticulationVertices[g] gives a list of all articulation vertices in graph g. These are vertices whose removal will disconnect the graph."
Automorphisms::usage = "Automorphisms[g] gives the automorphism group of the graph g."
Backtrack::usage = "Backtrack[s, partialQ, solutionQ] performs a backtrack search of the state space s, expanding a partial solution so long as partialQ is True and returning the first complete solution, as identified by solutionQ."
BellB::usage = "BellB[n] returns the nth Bell number."
BellmanFord::usage = "BellmanFord[g, v] gives a shortest-path spanning tree and associated distances from vertex v of graph g. The shortest-path spanning tree is given by a list in which element i is the predecessor of vertex i in the shortest-path spanning tree. BellmanFord works correctly even when the edge weights are negative, provided there are no negative cycles."
BiconnectedComponents::usage = "BiconnectedComponents[g] gives a list of the biconnected components of graph g. If g is directed, the underlying undirected graph is used."
BiconnectedQ::usage = "BiconnectedQ[g] yields True if graph g is biconnected. If g is directed, the underlying undirected graph is used."
BinarySearch::usage = "BinarySearch[l, k] searches sorted list l for key k and gives the position of l containing k, if k is present in l. Otherwise, if k is absent in l, the function returns (p + 1/2) where k falls between the elements of l in positions p and p+1. BinarySearch[l, k, f] gives the position of k in the list obtained from l by applying f to each element in l."
BinarySubsets::usage = "BinarySubsets[l] gives all subsets of l ordered according to the binary string defining each subset. For any positive integer n, BinarySubsets[n] gives all subsets of {1, 2,.., n} ordered according to the binary string defining each subset."
BipartiteMatching::usage = "BipartiteMatching[g] gives the list of edges associated with a maximum matching in bipartite graph g. If the graph is edge weighted, then the function returns a matching with maximum total weight."
BipartiteMatchingAndCover::usage = "BipartiteMatchingAndCover[g] takes a bipartite graph g and returns a matching with maximum weight along with the dual vertex cover. If the graph is not weighted, it is assumed that all edge weights are 1."
BipartiteQ::usage = "BipartiteQ[g] yields True if graph g is bipartite."
BooleanAlgebra::usage = "BooleanAlgebra[n] gives a Hasse diagram for the Boolean algebra on n elements. The function takes two options: Type and VertexLabel, with default values Undirected and False, respectively. When Type is set to Directed, the function produces the underlying directed acyclic graph. When VertexLabel is set to True, labels are produced for the vertices."
Box::usage = "Box is a value that the option VertexStyle, used in ShowGraph, can be set to."
BreadthFirstTraversal::usage = "BreadthFirstTraversal[g, v] performs a breadth-first traversal of graph g starting from vertex v, and gives the breadth-first numbers of the vertices. BreadthFirstTraversal[g, v, Edge] returns the edges of the graph that are traversed by breadth-first traversal. BreadthFirstTraversal[g, v, Tree] returns the breadth-first search tree. BreadthFirstTraversal[g, v, Level] returns the level number of the vertices."
Brelaz::usage = "Brelaz is a value that the option Algorithm can take when used in the function VertexColoring."
BrelazColoring::usage = "BrelazColoring[g] returns a vertex coloring in which vertices are greedily colored with the smallest available color in decreasing order of vertex degree."
Bridges::usage = "Bridges[g] gives a list of the bridges of graph g, where each bridge is an edge whose removal disconnects the graph."
ButterflyGraph::usage = "ButterflyGraph[n] returns the n-dimensional butterfly graph, a directed graph whose vertices are pairs (w, i), where w is a binary string of length n and i is an integer in the range 0 through n and whose edges go from vertex (w, i) to (w', i+1), if w' is identical to w in all bits with the possible exception of the (i+1)th bit. Here bits are counted left to right. An option VertexLabel, with default setting False, is allowed. When this option is set to True, vertices are labeled with strings (w, i)."
CageGraph::usage = "CageGraph[k, r] gives a smallest k-regular graph of girth r for certain small values of k and r. CageGraph[r] gives CageGraph[3, r]. For k = 3, r can be 3, 4, 5, 6, 7, 8, or 10. For k = 4 or 5, r can be 3, 4, 5, or 6."
CartesianProduct::usage = "CartesianProduct[l1, l2] gives the Cartesian product of lists l1 and l2."
Center::usage = "Center is a value that options VertexNumberPosition, VertexLabelPosition, and EdgeLabelPosition can take on in ShowGraph."
ChangeEdges::usage = "ChangeEdges[g, e] replaces the edges of graph g with the edges in e. e can have the form {{s1, t1}, {s2, t2}, ...} or the form { {{s1, t1}, gr1}, {{s2, t2}, gr2}, ...}, where {s1, t1}, {s2, t2}, ... are endpoints of edges and gr1, gr2, ... are graphics information associated with edges."
ChangeVertices::usage = "ChangeVertices[g, v] replaces the vertices of graph g with the vertices in the given list v. v can have the form {{x1, y1}, {x2, y2}, ...} or the form {{{x1, y1}, gr1}, {{x2, y2}, gr2}, ...}, where {x1, y1}, {x2, y2}, ... are coordinates of points and gr1, gr2, ... are graphics information associated with vertices."
ChromaticNumber::usage = "ChromaticNumber[g] gives the chromatic number of the graph, which is the fewest number of colors necessary to color the graph."
ChromaticPolynomial::usage = "ChromaticPolynomial[g, z] gives the chromatic polynomial P(z) of graph g, which counts the number of ways to color g with, at most, z colors."
ChvatalGraph::usage = "ChvatalGraph returns a smallest triangle-free, 4-regular, 4-chromatic graph."
CirculantGraph::usage = "CirculantGraph[n, l] constructs a circulant graph on n vertices, meaning the ith vertex is adjacent to the (i+j)th and (i-j)th vertices, for each j in list l. CirculantGraph[n, l], where l is an integer, returns the graph with n vertices in which each i is adjacent to (i+l) and (i-l)."
CircularEmbedding::usage = "CircularEmbedding[n] constructs a list of n points equally spaced on a circle. CircularEmbedding[g] embeds the vertices of g equally spaced on a circle."
CircularVertices::usage = "CircularVertices[n] constructs a list of n points equally spaced on a circle. CircularVertices[g] embeds the vertices of g equally spaced on a circle. This function is obsolete; use CircularEmbedding instead."
CliqueQ::usage = "CliqueQ[g, c] yields True if the list of vertices c defines a clique in graph g."
CoarserSetPartitionQ::usage = "CoarserSetPartitionQ[a, b] yields True if set partition b is coarser than set partition a, that is, every block in a is contained in some block in b."
CodeToLabeledTree::usage = "CodeToLabeledTree[l] constructs the unique labeled tree on n vertices from the Prufer code l, which consists of a list of n-2 integers between 1 and n."
Cofactor::usage = "Cofactor[m, {i, j}] calculates the (i, j)th cofactor of matrix m."
CompleteBinaryTree::usage = "CompleteBinaryTree[n] returns a complete binary tree on n vertices."
CompleteGraph::usage = "CompleteGraph[n] creates a complete graph on n vertices. An option Type that takes on the values Directed or Undirected is allowed. The default setting for this option is Type -> Undirected. CompleteGraph[a, b, c,...] creates a complete k-partite graph of the prescribed shape. The use of CompleteGraph to create a complete k-partite graph is obsolete; use CompleteKPartiteGraph instead."
CompleteKaryTree::usage = "CompleteKaryTree[n, k] returns a complete k-ary tree on n vertices."
CompleteKPartiteGraph::usage = "CompleteKPartiteGraph[a, b, c, ...] creates a complete k-partite graph of the prescribed shape, provided the k arguments a, b, c, ... are positive integers. An option Type that takes on the values Directed or Undirected is allowed. The default setting for this option is Type -> Undirected."
CompleteQ::usage = "CompleteQ[g] yields True if graph g is complete. This means that between any pair of vertices there is an undirected edge or two directed edges going in opposite directions."
Compositions::usage = "Compositions[n, k] gives a list of all compositions of integer n into k parts."
ConnectedComponents::usage = "ConnectedComponents[g] gives the vertices of graph g partitioned into connected components."
ConnectedQ::usage = "ConnectedQ[g] yields True if undirected graph g is connected. If g is directed, the function returns True if the underlying undirected graph is connected. ConnectedQ[g, Strong] and ConnectedQ[g, Weak] yield True if the directed graph g is strongly or weakly connected, respectively."
ConstructTableau::usage = "ConstructTableau[p] performs the bumping algorithm repeatedly on each element of permutation p, resulting in a distinct Young tableau."
Contract::usage = "Contract[g, {x, y}] gives the graph resulting from contracting the pair of vertices {x, y} of graph g."
CostOfPath::usage = "CostOfPath[g, p] sums up the weights of the edges in graph g defined by the path p."
CoxeterGraph::usage = "CoxeterGraph gives a non-Hamiltonian graph with a high degree of symmetry such that there is a graph automorphism taking any path of length 3 to any other."
CubeConnectedCycle::usage = "CubeConnectedCycle[d] returns the graph obtained by replacing each vertex in a d-dimensional hypercube by a cycle of length d. Cube-connected cycles share many properties with hypercubes but have the additional desirable property that for d > 1 every vertex has degree 3."
CubicalGraph::usage = "CubicalGraph returns the graph corresponding to the cube, a Platonic solid."
Cut::usage = "Cut is a tag that can be used in a call to NetworkFlow to tell it to return the minimum cut."
CycleIndex::usage = "CycleIndex[pg, x] returns the polynomial in x[1], x[2], ..., x[index[g]] that is the cycle index of the permutation group pg. Here index[pg] refers to the length of each permutation in pg."
Cycle::usage = "Cycle[n] constructs the cycle on n vertices, the 2-regular connected graph. An option Type that takes on values Directed or Undirected is allowed. The default setting is Type -> Undirected."
Cycles::usage = "Cycles is an optional argument for the function Involutions."
CycleStructure::usage = "CycleStructure[p, x] returns the monomial in x[1], x[2], ..., x[Length[p]] that is the cycle structure of the permutation p."
Cyclic::usage = "Cyclic is an argument to the Polya-theoretic functions ListNecklaces, NumberOfNecklace, and NecklacePolynomial, which count or enumerate distinct necklaces. Cyclic refers to the cyclic group acting on necklaces to make equivalent necklaces that can be obtained from each other by rotation."
CyclicGroup::usage = "CyclicGroup[n] returns the cyclic group of permutations on n symbols."
CyclicGroupIndex::usage = "CyclicGroupIndex[n, x] returns the cycle index of the cyclic group on n symbols, expressed as a polynomial in x[1], x[2], ..., x[n]."
DeBruijnGraph::usage = "DeBruijnGraph[m, n] constructs the n-dimensional De Bruijn graph with m symbols for integers m > 0 and n > 1. DeBruijnGraph[alph, n] constructs the n-dimensional De Bruijn graph with symbols from alph. Here alph is nonempty and n > 1 is an integer. In the latter form, the function accepts an option VertexLabel, with default value False, which can be set to True, if users want to associate strings on alph to the vertices as labels."
DeBruijnSequence::usage = "DeBruijnSequence[a, n] returns a De Bruijn sequence on the alphabet a, a shortest sequence in which every string of length n on alphabet a occurs as a contiguous subsequence."
DegreeSequence::usage = "DegreeSequence[g] gives the sorted degree sequence of graph g."
Degrees::usage = "Degrees[g] returns the degrees of vertex 1, 2, 3, ... in that order."
DegreesOf2Neighborhood::usage = "DegreesOf2Neighborhood[g, v] returns the sorted list of degrees of vertices of graph g within a distance of 2 from v."
DeleteCycle::usage = "DeleteCycle[g, c] deletes a simple cycle c from graph g. c is specified as a sequence of vertices in which the first and last vertices are identical. g can be directed or undirected. If g does not contain c, it is returned unchanged; otherwise g is returned with c deleted."
DeleteEdge::usage = "DeleteEdge[g, e] gives graph g minus e. If g is undirected, then e is treated as an undirected edge, otherwise it is treated as a directed edge. If there are multiple edges between the specified vertices, only one edge is deleted. DeleteEdge[g, e, All] will delete all edges between the specified pair of vertices. Using the tag Directed as a third argument in DeleteEdge is now obsolete."
DeleteEdges::usage = "DeleteEdges[g, edgeList] gives graph g minus the list of edges edgeList. If g is undirected, then the edges in edgeList are treated as undirected edges, or otherwise they are treated as directed edges. If there are multiple edges that qualify, then only one edge is deleted. DeleteEdges[g, edgeList, All] will delete all edges that qualify. If only one edge is to be deleted, then edgeList can have the form {s, t}, or otherwise it has the form {{s1, t1}, {s2, t2}, ...}."
DeleteFromTableau::usage = "DeleteFromTableau[t, r] deletes the last element of row r from Young tableaux t."
DeleteVertex::usage = "DeleteVertex[g, v] deletes a single vertex v from graph g. Here v is a vertex number."
DeleteVertices::usage = "DeleteVertices[g, vList] deletes vertices in vList from graph g. vList has the form {i, j, ...}, where i, j, ... are vertex numbers."
DepthFirstTraversal::usage = "DepthFirstTraversal[g, v] performs a depth-first traversal of graph g starting from vertex v, and gives a list of vertices in the order in which they were encountered. DepthFirstTraversal[g, v, Edge] returns the edges of the graph that are traversed by the depth-first traversal in the order in which they are traversed. DepthFirstTraversal[g, v, Tree] returns the depth-first tree of the graph."
DerangementQ::usage = "DerangementQ[p] tests whether permutation p is a derangement, that is, a permutation without a fixed point."
Derangements::usage = "Derangements[p] constructs all derangements of permutation p."
Diameter::usage = "Diameter[g] gives the diameter of graph g, the maximum length, among all pairs of vertices in g, of a shortest path between each pair."
Dihedral::usage = "Dihedral is an argument to the Polya-theoretic functions ListNecklaces, NumberOfNecklace, and NecklacePolynomial, which count or enumerate distinct necklaces. Dihedral refers to the dihedral group acting on necklaces to make equivalent necklaces that can be obtained from each other by a rotation or a flip."
DihedralGroup::usage = "DihedralGroup[n] returns the dihedral group on n symbols. Note that the order of this group is 2n."
DihedralGroupIndex::usage = "DihedralGroupIndex[n, x] returns the cycle index of the dihedral group on n symbols, expressed as a polynomial in x[1], x[2], ..., x[n]."
Dijkstra::usage = "Dijkstra[g, v] gives a shortest-path spanning tree and associated distances from vertex v of graph g. The shortest-path spanning tree is given by a list in which element i is the predecessor of vertex i in the shortest-path spanning tree. Dijkstra does not work correctly when the edge weights are negative; BellmanFord should be used in this case."
DilateVertices::usage = "DilateVertices[v, d] multiplies each coordinate of each vertex position in list v by d, thus dilating the embedding. DilateVertices[g, d] dilates the embedding of graph g by the factor d."
Directed::usage = "Directed is an option value for Type."
$NewMessage[Disk, "usage"] (* reset the usage of Disk to the system usage *)
If[StringQ[Disk::usage], Disk::usage = StringJoin[Disk::usage, " Disk is also a value taken by the VertexStyle option in ShowGraph."]]
Distances::usage = "Distances[g, v] returns the distances in nondecreasing order from vertex v to all vertices in g, treating g as an unweighted graph."
DistinctPermutations::usage = "DistinctPermutations[l] gives all permutations of the multiset described by list l."
Distribution::usage = "Distribution[l, set] lists the frequency of each element of set in list l."
DodecahedralGraph::usage = "DodecahedralGraph returns the graph corresponding to the dodecahedron, a Platonic solid."
DominatingIntegerPartitionQ::usage = "DominatingIntegerPartitionQ[a, b] yields True if integer partition a dominates integer partition b, that is, the sum of a size-t prefix of a is no smaller than the sum of a size-t prefix of b for every t."
DominationLattice::usage = "DominationLattice[n] returns a Hasse diagram of the partially ordered set on integer partitions of n in which p < q if q dominates p. The function takes two options: Type and VertexLabel, with default values Undirected and False, respectively. When Type is set to Directed, the function produces the underlying directed acyclic graph. When VertexLabel is set to True, labels are produced for the vertices."
DurfeeSquare::usage = "DurfeeSquare[p] gives the number of rows involved in the Durfee square of partition p, the side of the largest-sized square contained within the Ferrers diagram of p."
Eccentricity::usage = "Eccentricity[g] gives the eccentricity of each vertex v of graph g, the maximum length among all shortest paths from v."
Edge::usage = "Edge is an optional argument to inform certain functions to work with edges instead of vertices."
EdgeChromaticNumber::usage = "EdgeChromaticNumber[g] gives the fewest number of colors necessary to color each edge of graph g, so that no two edges incident on the same vertex have the same color."
EdgeColor::usage = "EdgeColor is an option that allows the user to associate colors with edges. Black is the default color. EdgeColor can be set as part of the graph data structure or in ShowGraph."
EdgeColoring::usage = "EdgeColoring[g] uses Brelaz's heuristic to find a good, but not necessarily minimal, edge coloring of graph g."
EdgeConnectivity::usage = "EdgeConnectivity[g] gives the minimum number of edges whose deletion from graph g disconnects it. EdgeConnectivity[g, Cut] gives a set of edges of minimum size whose deletion disconnects the graph."
EdgeDirection::usage = "EdgeDirection is an option that takes on values True or False allowing the user to specify whether the graph is directed or not. EdgeDirection can be set as part of the graph data structure or in ShowGraph."
EdgeLabel::usage = "EdgeLabel is an option that can take on values True or False, allowing the user to associate labels to edges. By default, there are no edge labels. The EdgeLabel option can be set as part of the graph data structure or in ShowGraph."
EdgeLabelColor::usage = "EdgeLabelColor is an option that allows the user to associate different colors to edge labels. Black is the default color. EdgeLabelColor can be set as part of the graph data structure or in ShowGraph."
EdgeLabelPosition::usage = "EdgeLabelPosition is an option that allows the user to place an edge label in a certain position relative to the midpoint of the edge. LowerLeft is the default value of this option. EdgeLabelPosition can be set as part of the graph data structure or in ShowGraph."
Edges::usage = "Edges[g] gives the list of edges in g. Edges[g, All] gives the edges of g along with the graphics options associated with each edge. Edges[g, EdgeWeight] returns the list of edges in g along with their edge weights."
EdgeStyle::usage = "EdgeStyle is an option that allows the user to associate different sizes and shapes to edges. A line segment is the default edge. EdgeStyle can be set as part of the graph data structure or in ShowGraph."
EdgeWeight::usage = "EdgeWeight is an option that allows the user to associate weights with edges. 1 is the default weight. EdgeWeight can be set as part of the graph data structure."
$NewMessage[ Element, "usage"] (* reset the usage of Element to the System usage *)
If[StringQ[Element::usage], Element::usage = StringJoin[ Element::usage, " The use of the function Element in Combinatorica is now obsolete, though the function call Element[a, p] still gives the pth element of nested list a, where p is a list of indices."]]
EmptyGraph::usage = "EmptyGraph[n] generates an empty graph on n vertices. An option Type that can take on values Directed or Undirected is provided. The default setting is Type -> Undirected."
EmptyQ::usage = "EmptyQ[g] yields True if graph g contains no edges."
EncroachingListSet::usage = "EncroachingListSet[p] constructs the encroaching list set associated with permutation p."
EquivalenceClasses::usage = "EquivalenceClasses[r] identifies the equivalence classes among the elements of matrix r."
EquivalenceRelationQ::usage = "EquivalenceRelationQ[r] yields True if the matrix r defines an equivalence relation. EquivalenceRelationQ[g] tests whether the adjacency matrix of graph g defines an equivalence relation."
Equivalences::usage = "Equivalences[g, h] lists the vertex equivalence classes between graphs g and h defined by their vertex degrees. Equivalences[g] lists the vertex equivalences for graph g defined by the vertex degrees. Equivalences[g, h, f1, f2, ...] and Equivalences[g, f1, f2, ...] can also be used, where f1, f2, ... are functions that compute other vertex invariants. It is expected that for each function fi, the call fi[g, v] returns the corresponding invariant at vertex v in graph g. The functions f1, f2, ... are evaluated in order, and the evaluation stops either when all functions have been evaluated or when an empty equivalence class is found. Three vertex invariants, DegreesOf2Neighborhood, NumberOf2Paths, and Distances are Combinatorica functions and can be used to refine the equivalences."
Euclidean::usage = "Euclidean is an option for SetEdgeWeights."
Eulerian::usage = "Eulerian[n, k] gives the number of permutations of length n with k runs."
EulerianCycle::usage = "EulerianCycle[g] finds an Eulerian cycle of g if one exists."
EulerianQ::usage = "EulerianQ[g] yields True if graph g is Eulerian, meaning there exists a tour that includes each edge exactly once."
ExactRandomGraph::usage = "ExactRandomGraph[n, e] constructs a random labeled graph of exactly e edges and n vertices."
ExpandGraph::usage = "ExpandGraph[g, n] expands graph g to n vertices by adding disconnected vertices. This is obsolete; use AddVertices[g, n] instead."
ExtractCycles::usage = "ExtractCycles[g] gives a maximal list of edge-disjoint cycles in graph g."
FerrersDiagram::usage = "FerrersDiagram[p] draws a Ferrers diagram of integer partition p."
FindCycle::usage = "FindCycle[g] finds a list of vertices that define a cycle in graph g."
FindSet::usage = "FindSet[n, s] gives the root of the set containing n in union-find data structure s."
FiniteGraphs::usage = "FiniteGraphs produces a convenient list of all the interesting, finite, parameterless graphs built into Combinatorica."
FirstLexicographicTableau::usage = "FirstLexicographicTableau[p] constructs the first Young tableau with shape described by partition p."
FolkmanGraph::usage = "FolkmanGraph returns a smallest graph that is edge-transitive but not vertex-transitive."
FranklinGraph::usage = "FranklinGraph returns a 12-vertex graph that represents a 6-chromatic map on the Klein bottle. It is the sole counterexample to Heawood's map coloring conjecture."
FromAdjacencyLists::usage = "FromAdjacencyLists[l] constructs an edge list representation for a graph from the given adjacency lists l, using a circular embedding. FromAdjacencyLists[l, v] uses v as the embedding for the resulting graph. An option called Type that takes on the values Directed or Undirected can be used to affect the type of graph produced. The default value of Type is Undirected."
FromAdjacencyMatrix::usage = "FromAdjacencyMatrix[m] constructs a graph from a given adjacency matrix m, using a circular embedding. FromAdjacencyMatrix[m, v] uses v as the embedding for the resulting graph. An option Type that takes on the values Directed or Undirected can be used to affect the type of graph produced. The default value of Type is Undirected. FromAdjacencyMatrix[m, EdgeWeight] interprets the entries in m as edge weights, with infinity representing missing edges, and from this constructs a weighted graph using a circular embedding. FromAdjacencyMatrix[m, v, EdgeWeight] uses v as the embedding for the resulting graph. The option Type can be used along with the EdgeWeight tag."
FromCycles::usage = "FromCycles[{c1, c2, ...}] gives the permutation that has the given cycle structure."
FromInversionVector::usage = "FromInversionVector[v] reconstructs the unique permutation with inversion vector v."
FromOrderedPairs::usage = "FromOrderedPairs[l] constructs an edge list representation from a list of ordered pairs l, using a circular embedding. FromOrderedPairs[l, v] uses v as the embedding for the resulting graph. The option Type that takes on values Undirected or Directed can be used to affect the kind of graph produced. The default value of Type is Directed. Type -> Undirected results in the underlying undirected graph."
FromUnorderedPairs::usage = "FromUnorderedPairs[l] constructs an edge list representation from a list of unordered pairs l, using a circular embedding. FromUnorderedPairs[l, v] uses v as the embedding for the resulting graph. The option Type that takes on values Undirected or Directed can be used to affect the kind of graph produced."
FruchtGraph::usage = "FruchtGraph returns the smallest 3-regular graph whose automorphism group consists of only the identity."
FunctionalGraph::usage = "FunctionalGraph[f, v] takes a set v and a function f from v to v and constructs a directed graph with vertex set v and edges (x, f(x)) for each x in v. FunctionalGraph[f, v], where f is a list of functions, constructs a graph with vertex set v and edge set (x, fi(x)) for every fi in f. An option called Type that takes on the values Directed and Undirected is allowed. Type -> Directed is the default, while Type -> Undirected returns the corresponding underlying undirected graph. FunctionalGraph[f, n] takes a nonnegative integer nand a function f from {0,1,..., n-1} onto itself and produces the directed graphwith vertex set {0, 1,..., n-1} and edge set {x, f(x)} for each vertex x."
GeneralizedPetersenGraph::usage = "GeneralizedPetersenGraph[n, k] returns the generalized Petersen graph, for integers n > 1 and k > 0, which is the graph with vertices {u1, u2, ..., un} and {v1, v2, ..., vn} and edges {ui, u(i+1)}, {vi, v(i+k)}, and {ui, vi}. The Petersen graph is identical to the generalized Petersen graph with n = 5 and k = 2."
GetEdgeLabels::usage = "GetEdgeLabels[g] returns the list of labels of the edges of g. GetEdgeLabels[g, es] returns the list of labels in graph g of the edges in es."
GetEdgeWeights::usage = "GetEdgeWeights[g] returns the list of weights of the edges of g. GetEdgeWeights[g, es] returns the list of weights in graph g of the edges in es."
GetVertexLabels::usage = "GetVertexLabels[g] returns the list of labels of vertices of g. GetVertexLabels[g, vs] returns the list of labels in graph g of the vertices specified in list vs."
GetVertexWeights::usage = "GetVertexWeights[g] returns the list of weights of vertices of g. GetVertexWeights[g, vs] returns the list of weights in graph g of the vertices in vs."
Girth::usage = "Girth[g] gives the length of a shortest cycle in a simple graph g."
Graph::usage = "Graph[e, v, opts] represents a graph object where e is the list of edges annotated with graphics options, v is a list of vertices annotated with graphics options, and opts is a set of global graph options. e has the form {{{i1, j1}, opts1}, {{i2, j2}, opts2},...}, where {i1, j1}, {i2, j2},... are edges of the graph and opts1, opts2,... are options that respectively apply to these edges. v has the form {{{x1, y1}, opts1}, {{x2, y2}, opts2},...}, where {x1, y1}, {x2, y2},... respectively denote the coordinates in the plane of vertex 1, vertex 2,... and opts1, opts2,... are options that respectively apply to these vertices. Permitted edge options are EdgeWeight, EdgeColor, EdgeStyle, EdgeLabel, EdgeLabelColor, and EdgeLabelPosition. Permitted vertex options are VertexWeight, VertexColor, VertexStyle, VertexNumber, VertexNumberColor, VertexNumberPosition, VertexLabel, VertexLabelColor, and VertexLabelPosition. The third item in a Graph object is opts, a sequence of zero or more global options that apply to all vertices or all edges or to the graph as a whole. All of the edge options and vertex options can be used as global options also. If a global option and a local edge option or vertex option differ, then the local edge or vertex option is used for that particular edge or vertex. In addition to these options, the following two options can also be specified as part of the global options: LoopPosition and EdgeDirection. Furthermore, all the options of the Mathematica function Plot can be used as global options in a Graph object. These can be used to specify how the graph looks when it is drawn. Also, all options of the graphics primitive Arrow can also be specified as part of global graph options. These can be used to affect the look of arrows that represent directed edges. See the usage message of individual options to find out more about values these options can take on. Whether a graph is undirected or directed is given by the option EdgeDirection. This has default value False. For undirected graphs, the edges {i1, j1}, {i2, j2},... have to satisfy i1 <= j1, i2 <= j2,... and for directed graphs the edges {i1, j1}, {i2, j2},... are treated as ordered pairs, each specifying the direction of the edge as well."
GraphCenter::usage = "GraphCenter[g] gives a list of the vertices of graph g with minimum eccentricity."
GraphComplement::usage = "GraphComplement[g] gives the complement of graph g."
GraphDifference::usage = "GraphDifference[g, h] constructs the graph resulting from subtracting the edges of graph h from the edges of graph g."
GraphicQ::usage = "GraphicQ[s] yields True if the list of integers s is a graphic sequence, and thus represents a degree sequence of some graph."
GraphIntersection::usage = "GraphIntersection[g1, g2, ...] constructs the graph defined by the edges that are in all the graphs g1, g2, ...."
GraphJoin::usage = "GraphJoin[g1, g2, ...] constructs the join of graphs g1, g2, and so on. This is the graph obtained by adding all possible edges between different graphs to the graph union of g1, g2, ...."
GraphOptions::usage = "GraphOptions[g] returns the display options associated with g. GraphOptions[g, v] returns the display options associated with vertex v in g. GraphOptions[g, {u, v}] returns the display options associated with edge {u, v} in g."
GraphPolynomial::usage = "GraphPolynomial[n, x] returns a polynomial in x in which the coefficient of x^m is the number of nonisomorphic graphs with n vertices and m edges. GraphPolynomial[n, x, Directed] returns a polynomial in x in which the coefficient of x^m is the number of nonisomorphic directed graphs with n vertices and m edges."
GraphPower::usage = "GraphPower[g, k] gives the kth power of graph g. This is the graph whose vertex set is identical to the vertex set of g and that contains an edge between vertices i and j if g contains a path between i and j of length, at most, k."
GraphProduct::usage = "GraphProduct[g1, g2, ...] constructs the product of graphs g1, g2, and so forth."
GraphSum::usage = "GraphSum[g1, g2, ...] constructs the graph resulting from joining the edge lists of graphs g1, g2, and so forth."
GraphUnion::usage = "GraphUnion[g1, g2, ...] constructs the union of graphs g1, g2, and so forth. GraphUnion[n, g] constructs n copies of graph g, for any nonnegative integer n."
GrayCode::usage = "GrayCode[l] constructs a binary reflected Gray code on set l. GrayCode is obsolete, so use GrayCodeSubsets instead."
GrayCodeKSubsets::usage = "GrayCodeKSubsets[l, k] generates k-subsets of l in Gray code order."
GrayCodeSubsets::usage = "GrayCodeSubsets[l] constructs a binary reflected Gray code on set l."
GrayGraph::usage = "GrayGraph returns a 3-regular, 54-vertex graph that is edge-transitive but not vertex-transitive; the smallest known such example."
Greedy::usage = "Greedy is a value that the option Algorithm can take in calls to functions such as VertexCover, telling the function to use a greedy algorithm."
GreedyVertexCover::usage = "GreedyVertexCover[g] returns a vertex cover of graph g constructed using the greedy algorithm. This is a natural heuristic for constructing a vertex cover, but it can produce poor vertex covers."
GridGraph::usage = "GridGraph[n, m] constructs an n*m grid graph, the product of paths on n and m vertices. GridGraph[p, q, r] constructs a p*q*r grid graph, the product of GridGraph[p, q] and a path of length r."
GrotztschGraph::usage = "GrotztschGraph returns the smallest triangle-free graph with chromatic number 4. This is identical to MycielskiGraph[4]."
HamiltonianCycle::usage = "HamiltonianCycle[g] finds a Hamiltonian cycle in graph g if one exists. HamiltonianCycle[g, All] gives all Hamiltonian cycles of graph g."
HamiltonianPath::usage = "HamiltonianPath[g] finds a Hamiltonian path in graph g if one exists. HamiltonianPath[g, All] gives all Hamiltonian paths of graph g."
HamiltonianQ::usage = "HamiltonianQ[g] yields True if there exists a Hamiltonian cycle in graph g, or in other words, if there exists a cycle that visits each vertex exactly once."
Harary::usage = "Harary[k, n] constructs the minimal k-connected graph on n vertices."
HasseDiagram::usage = "HasseDiagram[g] constructs a Hasse diagram of the relation defined by directed acyclic graph g."
Heapify::usage = "Heapify[p] builds a heap from permutation p."
HeapSort::usage = "HeapSort[l] performs a heap sort on the items of list l."
HeawoodGraph::usage = "HeawoodGraph returns a smallest (6, 3)-cage, a 3-regular graph with girth 6."
HerschelGraph::usage = "HerschelGraph returns a graph object that represents a Herschel graph."
HideCycles::usage = "HideCycles[c] canonically encodes the cycle structure c into a unique permutation."
Highlight::usage = "Highlight[g, p] displays g with elements in p highlighted. The second argument p has the form {s1, s2,...}, where the sis are disjoint subsets of vertices and edges of g. The options, HighlightedVertexStyle, HighlightedEdgeStyle, HighlightedVertexColors, and HighlightedEdgeColors are used to determine the appearance of the highlighted elements of the graph. The default settings of the style options are HighlightedVertexStyle->Disk[Large] and HighlightedEdgeStyle->Thick. The options HighlightedVertexColors and HighlightedEdgeColors are both set to {Black, Red, Blue, Green, Yellow, Purple, Brown, Orange, Olive, Pink, DeepPink, DarkGreen, Maroon, Navy}. The colors are chosen from the palette of colors with color 1 used for s1, color 2 used for s2, and so on. If there are more parts than colors, then the colors are used cyclically. The function permits all the options that SetGraphOptions permits, for example, VertexColor, VertexStyle, EdgeColor, and EdgeStyle. These options can be used to control the appearance of the non-highlighted vertices and edges."
HighlightedEdgeColors::usage = "HighlightedEdgeColors is an option to Highlight that determines which colors are used for the highlighted edges."
HighlightedEdgeStyle::usage = "HighlightedEdgeStyle is an option to Highlight that determines how the highlighted edges are drawn."
HighlightedVertexColors::usage = "HighlightedVertexColors is an option to Highlight that determines which colors are used for the highlighted vertices."
HighlightedVertexStyle::usage = "HighlightedVertexStyle is an option to Highlight that determines how the highlighted vertices are drawn."
Hypercube::usage = "Hypercube[n] constructs an n-dimensional hypercube."
IcosahedralGraph::usage = "IcosahedralGraph returns the graph corresponding to the icosahedron, a Platonic solid."
IdenticalQ::usage = "IdenticalQ[g, h] yields True if graphs g and h have identical edge lists, even though the associated graphics information need not be the same."
IdentityPermutation::usage = "IdentityPermutation[n] gives the size-n identity permutation."
IncidenceMatrix::usage = "IncidenceMatrix[g] returns the (0, 1)-matrix of graph g, which has a row for each vertex and a column for each edge and (v, e) = 1 if and only if vertex v is incident upon edge e. For a directed graph, (v, e) = 1 if edge e is outgoing from v."
InDegree::usage = "InDegree[g, n] returns the in-degree of vertex n in directed graph g. InDegree[g] returns the sequence of in-degrees of the vertices in directed graph g."
IndependentSetQ::usage = "IndependentSetQ[g, i] yields True if the vertices in list i define an independent set in graph g."
Index::usage = "Index[p] gives the index of permutation p, the sum of all subscripts j such that p[j] is greater than p[j+1]."
InduceSubgraph::usage = "InduceSubgraph[g, s] constructs the subgraph of graph g induced by the list of vertices s."
InitializeUnionFind::usage = "InitializeUnionFind[n] initializes a union-find data structure for n elements."
InsertIntoTableau::usage = "InsertIntoTableau[e, t] inserts integer e into Young tableau t using the bumping algorithm. InsertIntoTableau[e, t, All] inserts e into Young tableau t and returns the new tableau as well as the row whose size is expanded as a result of the insertion."
IntervalGraph::usage = "IntervalGraph[l] constructs the interval graph defined by the list of intervals l."
Invariants::usage = "Invariants is an option to the functions Isomorphism and IsomorphicQ that informs these functions about which vertex invariants to use in computing equivalences between vertices."
InversePermutation::usage = "InversePermutation[p] yields the multiplicative inverse of permutation p."
InversionPoset::usage = "InversionPoset[n] returns a Hasse diagram of the partially ordered set on size-n permutations in which p < q if q can be obtained from p by an adjacent transposition that places the larger element before the smaller. The function takes two options: Type and VertexLabel, with default values Undirected and False, respectively. When Type is set to Directed, the function produces the underlying directed acyclic graph. When VertexLabel is set to True, labels are produced for the vertices."
Inversions::usage = "Inversions[p] counts the number of inversions in permutation p."
InvolutionQ::usage = "InvolutionQ[p] yields True if permutation p is its own inverse."
Involutions::usage = "Involutions[l] gives the list of involutions of the elements in the list l. Involutions[l, Cycles] gives the involutions in their cycle representation. Involution[n] gives size-n involutions. Involutions[n, Cycles] gives size-n involutions in their cycle representation."
IsomorphicQ::usage = "IsomorphicQ[g, h] yields True if graphs g and h are isomorphic. This function takes an option Invariants -> {f1, f2, ...}, where f1, f2, ... are functions that are used to compute vertex invariants. These functions are used in the order in which they are specified. The default value of Invariants is {DegreesOf2Neighborhood, NumberOf2Paths, Distances}."
Isomorphism::usage = "Isomorphism[g, h] gives an isomorphism between graphs g and h if one exists. Isomorphism[g, h, All] gives all isomorphisms between graphs g and h. Isomorphism[g] gives the automorphism group of g. This function takes an option Invariants -> {f1, f2, ...}, where f1, f2, ... are functions that are used to compute vertex invariants. These functions are used in the order in which they are specified. The default value of Invariants is {DegreesOf2Neighborhood, NumberOf2Paths, Distances}."