The voter model is a simple mathematical model of opinion formation in which voters are located at the nodes of a network, each voter has an opinion (in the simplest case, 0 or 1, but in the general case, ), and a randomly chosen voter assumes the opinion of one of its neighbors.This model can be used to describe the phase transition behavior of idealized physical systems and can result in a rather remarkable amount of structure starting from a given "random" input." It can be modeled very easily using cellular automata.It turns out that in finite networks (i.e., any real model), fluctuations always cause the system to reach an "absorbing" (i.e., constant) state.
A lattice is said to be oriented if there exists a rule which assigns a specified direction to any edge connecting arbitrary lattice points . In that way, an oriented lattice is intimately connected to an oriented graph.Given a point lattice , one common such rule is the so-called north-east rule which orients each edge of in the direction of increasing coordinate-value. This type of ordered lattice is central in a number of fields, e.g.,in oriented percolation models within the field of discrete percolation theory.
A directed graph in which it is possible to reach any node starting from any other node by traversing edges in some direction (i.e., not necessarily in the direction they point). The nodes in a weakly connected digraph therefore must all have either outdegree or indegree of at least 1. The numbers of nonisomorphic simple weakly connected digraphs on , 2, ... nodes are 1, 2, 13, 199, 9364, ... (OEIS A003085).
The score sequence of a tournament is a monotonic nondecreasing sequence of the outdegrees of the graph vertices of the corresponding tournament graph. Elements of a score sequence of length therefore lie between 0 and , inclusively. Score sequences are so named because they correspond to the set of possible scores obtainable by the members of a group of players in a tournament where each player plays all other players and each game results in a win for one player and a loss for the other. (The score sequence for a given tournament is obtained from the set of outdegrees sorted in nondecreasing order, and so must sum to , where is a binomial coefficient.)For example, the unique possible score sequences for is . For , the two possible sequences are and . And for , the four possible sequences are , , , and (OEIS A068029).Landau (1953) has shown that a sequence of integers () is a score sequence ifffor , ..., , where is a binomial coefficient, and equality for(Harary..
A weakly connected component is a maximal subgraph of a directed graph such that for every pair of vertices , in the subgraph, there is an undirected path from to and a directed path from to . Weakly connected components can be found in the Wolfram Language using WeaklyConnectedGraphComponents[g].
A directed strongly regular graph is a simple directed graph with adjacency matrix such that the span of , the identity matrix , and the unit matrix is closed under matrix multiplication.
In the directed graph above, pick any vertex and follow the arrows in sequence blue-red-red three times. You will finish at the green vertex. Similarly, follow the sequence blue-blue-red three times and you will always end on the yellow vertex, no matter where you started. This is called a synchronized coloring.The road coloring problem is the problem of synchronizing coloring of a directed finite strongly connected graph with the same outdegree and where the greatest common divisor of all cycles lengths is 1. Trahtman (2007) provided a positive solution to this problem.
A graph in which each graph edge is replaced by a directed graph edge, also called a digraph. A directed graph having no multiple edges or loops (corresponding to a binary adjacency matrix with 0s on the diagonal) is called a simple directed graph. A complete graph in which each edge is bidirected is called a complete directed graph. A directed graph having no symmetric pair of directed edges (i.e., no bidirected edges) is called an oriented graph. A complete oriented graph (i.e., a directed graph in which each pair of nodes is joined by a single edge having a unique direction) is called a tournament.If is an undirected connected graph, then one can always direct the circuit graph edges of and leave the separating edges undirected so that there is a directed path from any node to another. Such a graph is said to be transitive if the adjacency relation is transitive.A graph may be tested in the Wolfram Languageto see if it is a directed graph using DirectedGraphQ[g]...
A graph is transitive if any three vertices such that edges imply . Unlabeled transitive digraphs are called digraph topologies.
A matrix for a round-robin tournament involving players competing in matches (no ties allowed) having entries(1)This scoring system differs from that used to compute a score sequence of a tournament, in which a win gives one point and a loss zero points. The matrix satisfies(2)where is the transpose of (McCarthy and Benjamin 1996).The tournament matrix for players has zero determinant iff is odd (McCarthy and Benjamin 1996). Furthermore, the dimension of the null space of an -player tournament matrix is(3)(McCarthy and Benjamin 1996).
An oriented graph is a directed graph having no symmetric pair of directed edges. A complete oriented graph is called a tournament.The numbers of oriented graphs on , 2, ... nodes are 1, 2, 7, 42, 582, ... (OEIS A001174).The numbers of connected oriented graphs on , 2, ... nodes are 1, 1, 5, 34, 535 ... (OEIS A086345).
A complete oriented graph (Skiena 1990, p. 175), i.e., a graph in which every pair of nodes is connected by a single uniquely directed edge. The first and second 3-node tournaments shown above are called a transitive triple and cyclic triple, respectively (Harary 1994, p. 204).Tournaments (also called tournament graphs) are so named because an -node tournament graph correspond to a tournament in which each member of a group of players plays all other players, and each game results in a win for one player and a loss for the other. A so-called score sequence can be associated with every tournament giving the set of scores that would be obtained by the players in the tournament, with each win counting as one point and each loss counting as no points. (A different scoring system is used to compute a tournament's so-called tournament matrix, with 1 point awarded for a win and points for a loss.) The score sequence for a given tournament is obtained..
A strongly connected digraph is a directed graph in which it is possible to reach any node starting from any other node by traversing edges in the direction(s) in which they point. The nodes in a strongly connected digraph therefore must all have indegree of at least 1. The numbers of nonisomorphic simple strongly connected digraphs on , 2, ... nodes are 1, 1, 5, 83, 5048, 1047008, ... (OEIS A035512).A directed graph can be tested to see if it isstrongly connected using ConnectedGraphQ[g].
There are two distinct notions of connectivity in a directed graph. A directed graph is weakly connected if there is an undirected path between any pair of vertices, and strongly connected if there is a directed path between every pair of vertices (Skiena 1990, p. 173). The following tables summarized the number of weakly and strongly connected digraphs on , 2, ... nodes. The 8 weakly but not strongly connected digraphs on three nodes are illustrated above.connectivityOEIScountsweakly connectedA0030851, 2, 13, 199, 9364, ...strongly connectedA0355121, 1, 5, 83, 5048, 1047008, ...weakly but not stronglyA0569880, 1, 8, 116, 4316, 483835, ...
A strongly connected component is maximal subgraph of a directed graph such that for every pair of vertices , in the subgraph, there is a directed path from to and a directed path from to . Tarjan (1972) has devised an algorithm for determining strongly connected components, which is implemented in the Wolfram Language as ConnectedGraphComponents[g].
The network flow problem considers a graph with a set of sources and sinks and for which each edge has an assigned capacity (weight), and then asks to find the maximum flow that can be routed from to while respecting the given edge capacities. The network flow problem can be solved in time (Edmonds and Karp 1972; Skiena 1990, p. 237). It is implemented in the Wolfram Language as FindMaximumFlow[g, source, sink].
A state diagram is a labeled directed graph together with state information that can be used to indicate that certain paths on in a system may be traversed only in a certain way. State diagrams are also known as problem space models (Atallah 1998, p. 36-2). For example, in the left figure above (due to R. Abbott), a car must traverse a town while obeying all traffic laws, and making no U-turns. Initially, the car is at position 4, travelling east, and has a choice of moving to position 1, travelling east, or position 5, travelling east. The State diagram corresponding to the maze is illustrated in the above right figure.Another example created by R. Abbott is illustrated above. While the maze is very similar to the first one, the state diagram is not. This maze therefore illustrates that a minor change to the rules of a system can have a large impact on its state diagram.Other puzzles, problems, and programs use state diagrams as an analysis..
The maximum flow between vertices and in a graph is exactly the weight of the smallest set of edges to disconnect with and in different components (Ford and Fulkerson 1962; Skiena 1990, p. 178).
An orientation of an undirected graph is an assignment of exactly one direction to each of the edges of . Only connected, bridgeless graphs can have a strong orientation (Robbins 1939; Skiena 1990, p. 174). An oriented complete graph is called a tournament.
A simple directed graph is a directed graph having no multiple edges or graph loops (corresponding to a binary adjacency matrix with 0s on the diagonal). The number of simple directed graphs of nodes for , 2, ... are 1, 3, 16, 218, 9608, ... (OEIS A000273), which is given by NumberOfDirectedGraphs[n] in the Wolfram Language package Combinatorica` . The directed graphs on nodes can be enumerated as ListGraphs[n, Directed] in the Wolfram Language package Combinatorica` .A simple directed graph on nodes may have between 0 and edges. The number of simple directed graphs on nodes with edges can be given by NumberOfDirectedGraphs[n, m] in the Wolfram Language package Combinatorica` . The triangles of graphs counts on nodes (rows) with edges (columns) is given below (OEIS A052283)., 1, 2, ...1121, 1, 131, 1, 4, 4, 4, 1, 141, 1, 5, 13, 27, 38, 48, 38, 27, 13, 5, 1, 1A complete graph in which each edge is bidirected is called a complete directed graph. A directed..
An acyclic digraph is a directed graph containing no directed cycles, also known as a directed acyclic graph or a "DAG." Every finite acyclic digraph has at least one node of outdegree 0. The numbers of acyclic digraphs on , 2, ... vertices are 1, 2, 6, 31, 302, 5984, ... (OEIS A003087).The numbers of labeled acyclic digraphs on , 2, ... nodes are 1, 3, 25, 543, 29281, ... (OEIS A003024). Weisstein's conjecture proposed that positive eigenvalued -matrices were in one-to-one correspondence with labeled acyclic digraphs on nodes, and this was subsequently proved by McKay et al. (2004). Counts for both are therefore given by the beautiful recurrence equationwith (Harary and Palmer 1973, p. 19; Robinson 1973, pp. 239-273).
A functional graph is a directed graph in which each vertex has outdegree one, and can therefore be specified by a function mapping onto itself. Functional graphs for a function applied to a vertex list are implemented in the Wolfram Language as Graph[(# <-> f[#]) & /@ v].
Taking a connected graph or network with a high graph diameter and adding a very small number of edges randomly, the diameter tends to drop drastically. This is known as the small world phenomenon. It is sometimes also known as "six degrees of separation" since, in the social network of the world, any person turns out to be linked to any other person by roughly six connections.Short-term memory uses small world networks between neurons to remember this sentence.In modern mathematics, the center of the network of coauthorship is considered to be P. Erdős, resulting in the so-called Erdős number. In movies, Kevin Bacon is often mentioned as the center of the movie universe, but a recent study (Reynolds) has shown Christopher Lee to be the actual center. Both actors have co-starred with Julius LeFlore, so the Lee-Bacon distance is two...
Let be a group, and let be a set of group elements such that the identity element . The Cayley graph associated with is then defined as the directed graph having one vertex associated with each group element and directed edges whenever . The Cayley graph may depend on the choice of a generating set, and is connected iff generates (i.e., the set are group generators of ).Care is needed since the term "Cayley graph" is also used when is implicitly understood to be a set of generators for the group, in which case the graph is always connected (but in general, still dependent on the choice of generators). This sort of Cayley graph of a group may be computed in the Wolfram Language using CayleyGraph[G], where the generators used are those returned by GroupGenerators[G].To complicate matters further, undirected versions of proper directed Cayley graphs are also known as Cayley graphs.An undirected Cayley graph of a particular generating set of..
Connecting the centers of touching spheres in a three-dimensional Apollonian gasket by edges given a graph known as the Apollonian network. This process is illustrated above for the case of the planar Apollonian gasket. This network turns out to have some very special properties. In addition to being either deterministic or random, they are simultaneously scale-free, display small-world effects, can be embedded in an Euclidean lattice, and show space filling as well as matching graph properties. These networks describe force chains in granular packings, fragmented porous media, hierarchical road systems, and area-covering electrical supply networks (Andrade et al. 2005). Apollonian networks share many features of neuronal systems, and have been used to study the brain (Pellegrini et al. 2007).The first few two-dimensional Apollonian networks are illustrated above. The order-twonetwork has the connectivity of the Fano plane.Apollonian..
Newton's method for finding roots of a complex polynomial entails iterating the function , which can be viewed as applying the Euler backward method with step size unity to the so-called Newtonian vector field . The rescaled and desingularized vector field then has sinks at roots of and has saddle points at roots of that are not also roots of . The union of the closures of the unstable manifolds of the saddles of defines a directed graph whose vertices are the roots of and of , and whose edges are the unstable curves oriented by the flow direction. This graph, along with the labelling of each vertex with the multiplicity of as a root of , is defined to be the Newtonian graph of (Smale 1985, Shub et al. 1988, Kozen and Stefánsson 1997).
Gossiping and broadcasting are two problems of information dissemination described for a group of individuals connected by a communication network. In gossiping, every person in the network knows a unique item of information and needs to communicate it to everyone else. In broadcasting, one individual has an item of information which needs to be communicated to everyone else (Hedetniemi et al. 1988).A popular formulation assumes there are people, each one of whom knows a scandal which is not known to any of the others. They communicate by telephone, and whenever two people place a call, they pass on to each other as many scandals as they know. How many calls are needed before everyone knows about all the scandals? Denoting the scandal-spreaders as , , , and , a solution for is given by , , , . The solution can then be generalized to by adding the pair to the beginning and end of the previous solution, i.e., , , , , , .Gossiping (which is also called total exchange..