In the 19th and 20th centuries these ideas were made more general and so more abstract as directed graphs: a set of things some of which are connected in pairs.
A digraph always has a set of objects - called vertices or nodes. These are connected or linked in pairs. An Edge is the name given to an undirected link between two nodes, while an arc stands for a directed edge. In the following table V stands for Vertices or Nodes, E for edges, and A for Arc. Also the term finite_sets indicates a finite subset of some given type.
From Name Synopsis,
---------------------------------------------------
Berge
DIGRAPH
Net{Nodes:Set, \Gamma:(@Nodes)^(Nodes|@Nodes)}
Harary & Norman & Cartwrite
NET
Net{X,V::Set, first,second::X->V,
arc::= (first,second), loop::= arc&Id(V)}
'' RELATION
Net{NET, arc in X(0..1)-(1)V}
'' DIGRAPH
Net{RELATION, loop=0}
Birkhoff&Bartee
GRAPH
Net{N,A:Set, phi:A->(N><N)}
Manna GRAPH
Net{V:finite_set, L:set, A:@(V><L><V)}
Harary GRAPH
Net{V:Set, X:@V, for all x:X(|x|=2)}
Berge p-GRAPH
Net{p:Nat1, S:Set, n:S^2->0..p}
Wilson GRAPH
Net{V,E:finite_set, E:(V^2)->Nat0}
'' DIGRAPH
Net{V,E:finite_set, E:@(V^(2bag??))}
'' SIMPLE_GRAPH
Net{V,E, E:@(V^2)}
Carre Graphs_&_Networks
Net{X:finite_set, U:@(X^2)}
Dossey, Otto, Spence, VanDen Eynden
'' directed_graph
Net{V:finite_sets, E:@(V^2)&finite_set}
---------------------------------------------------
Arrows are defined as part of the STANDARD definitions of MATHS [ math_11_STANDARD.html ]
All digraphs are epimorphic to a digraph with strongly connect components as
nodes.
All subgraphs of a digraph are a digraph submorphism and vice-versa:
Connonical expansion
Source: Knuth 69, Donald Knuth, "Art of Computer Programming". (Nodes=>S, arcs=>E, Γ=>parents) ::digraph,
Source: Knuth 69,Vol 1, 2.3.4.3 Theorem K.
Also see [ PART_WHOLE in math_21_Order ]
. . . . . . . . . ( end of section Trees) <<Contents | End>>
. . . . . . . . . ( end of section Digraphs) <<Contents | End>>
Source: Heckerman et al 95, David Heckerman & Abe Mamdami & Michael P WellMan (Guest Eds)Real-World Applications of Bayesian Neworks, Comm ACM V38n3(Mar 95)pp24-57
Each node has a special arc that acts as an identity operation.
A node can have one identity, and this identity is not the same as any other identity on other nodes. A node may or may not have a non-identity self-loop, of course.
The identity labels are interesting because they have no effect on things when composed with them:
... In MATHS we indicate a path a sequence like this: x-a->y-b->z-c->w, wherex,y,z,w are either nodes or node labels, and a,b,c are arc labels.
A set of paths is said to commute if the composition of the labels on the arcs in each path in the set are all the same. The set is usually drawn as a diagram of a graph which contains all the paths.
Example:
The following is a transcription into our notation of the "APPENDIX: Formal Definition of Higraphs", with the exception of the relations inside and is_part_of which we have added to clarify and simplify the presentation.
In what follows we present a formal (non-graphical) syntax and semantics for higraphs with simple bidirectional edges. The reader should have no difficulty in extending the edges to represent, say, hyperedges.
(HG0): For no x:Blobs (x is_part_of x ),
Semantics are decribed by giving a structure preserving maps(μ_a,μ_b,...) from the syntatic terms into expressions in logic and set theory.
.Quote Copyright. The original was copyrighted by the ACM, However they give permission to copy all or part without fee provided that the copies are not made or distributed for direct commercial advantage, and the title and this copywrite notice appear. ( Copyright 1988 ACM 0001-0782 88/0500-0514 $1.50)
. . . . . . . . . ( end of section Harel Higraphs) <<Contents | End>>
. . . . . . . . . ( end of section Graphs) <<Contents | End>>
Proofs follow a natural deduction style that start with assumptions ("Let") and continue to a consequence ("Close Let") and then discard the assumptions and deduce a conclusion. Look here [ Block Structure in logic_25_Proofs ] for more on the structure and rules.
The notation also allows you to create a new network of variables and constraints. A "Net" has a number of variables (including none) and a number of properties (including none) that connect variables. You can give them a name and then reuse them. The schema, formal system, or an elementary piece of documentation starts with "Net" and finishes "End of Net". For more, see [ notn_13_Docn_Syntax.html ] for these ways of defining and reusing pieces of logic and algebra in your documents. A quick example: a circle might be described by Net{radius:Positive Real, center:Point, area:=π*radius^2, ...}.
For a complete listing of pages in this part of my site by topic see [ home.html ]
For a more rigorous description of the standard notations see