Tag: graph theory

NetworkX Resources

 

This page provides some useful resources about NetworkX — a very useful python libary for manipulating and analyzing graphs.

Brief intro to NetworkX:

NetworkX is a well maintained Python library for the creation, manipulation, and study of graphs and complex networks. NetworkX provides data structures for networks along with graph algorithms, generators, and drawing tools. In particular NetworkX complements Python’s scientific computing suite of SciPy/NumPy, Matplotlib, and Graphviz and can handle graphs in very large memory. NetworkX is recommended to be part of every data scientist’s toolkit.

The core algorithms that are included are implemented on very fast legacy code. Graphs are hugely flexible (nodes can be any hashable type), and there is an extensive set of native IO formats.

Algorithms and Functions in NetworkX:

 

 

 

https://stackoverflow.com/questions/28966239/python-networkx-bridge-detection

 

node_connectivity

edge_connectivity

  • Python Networkx detecting loops/circles

https://stackoverflow.com/questions/35683302/python-networkx-detecting-loops-circles

  • TBA
  • TBA

Graph Generators in NetworkX (Reference » Graph generators):

 

Notes

Graph, node, and edge data are not propagated to the new graph. For undirected graphs, the nodes in G must be sortable, otherwise the constructed line graph may not be correct.

Self-loops in undirected graphs

For an undirected graph G without multiple edges, each edge can be written as a set {u, v}. Its line graph L has the edges of G as its nodes. If x and y are two nodes in L, then {x, y} is an edge in L if and only if the intersection of x and y is nonempty. Thus, the set of all edges is determined by the set of all pairwise intersections of edges in G.

Trivially, every edge in G would have a nonzero intersection with itself, and so every node in L should have a self-loop. This is not so interesting, and the original context of line graphs was with simple graphs, which had no self-loops or multiple edges. The line graph was also meant to be a simple graph and thus, self-loops in L are not part of the standard definition of a line graph. In a pairwise intersection matrix, this is analogous to excluding the diagonal entries from the line graph definition.

Self-loops and multiple edges in G add nodes to L in a natural way, and do not require any fundamental changes to the definition. It might be argued that the self-loops we excluded before should now be included. However, the self-loops are still “trivial” in some sense and thus, are usually excluded.

Self-loops in directed graphs

For a directed graph G without multiple edges, each edge can be written as a tuple (u, v). Its line graph L has the edges of G as its nodes. If x and y are two nodes in L, then (x, y) is an edge in L if and only if the tail of x matches the head of y, for example, if x
= (a, b) and y = (b, c) for some vertices a, b, and c in G.

Due to the directed nature of the edges, it is no longer the case that every edge in G should have a self-loop in L. Now, the only time self-loops arise is if a node in G itself has a self-loop. So such self-loops are no longer “trivial” but instead, represent essential features of the topology of G. For this reason, the historical development of line digraphs is such that self-loops are included. When the graph G has multiple edges, once again only superficial changes are required to the definition.

 

References

      • Harary, Frank, and Norman, Robert Z., “Some properties of line digraphs”, Rend. Circ. Mat. Palermo, II. Ser. 9 (1960), 161–168.
      • Hemminger, R. L.; Beineke, L. W. (1978), “Line graphs and line digraphs”, in Beineke, L. W.; Wilson, R. J., Selected Topics in Graph Theory, Academic Press Inc., pp. 271–305.

NetworkX Tutorials:

Galil, Z. (1986). “Efficient algorithms for finding maximum matching in graphs“. ACM Computing Surveys. Vol. 18, No. 1: 23-38.

Packages built on NetworkX

multiNetX is a python package for the manipulation and visualization of multilayer networks. It is build on NetworkX . The core of this package is a MultilayerGraph, a class that inherits all properties from networkx.Graph().

This allows for:

      • Creating networks with weighted or unweighted links (only undirected networks are supported in this version)
      • Analysing the spectral properties of adjacency or Laplacian matrices
      • Visualizing dynamical processes by coloring the nodes and links accordingly

06 Network Graphs

  • TBA

 

 

References:

To cite NetworkX please use the following publication:

Aric A. Hagberg, Daniel A. Schult and Pieter J. Swart, “Exploring network structure, dynamics, and function using NetworkX”, in Proceedings of the 7th Python in Science Conference (SciPy2008), Gäel Varoquaux, Travis Vaught, and Jarrod Millman (Eds), (Pasadena, CA USA), pp. 11–15, Aug 2008

 

 

Graph Theory Resources

 

This page provides some Graph Theory (GT) resources.

Good website about intro to GT.

GT – Basics

 

G properties

  •      A disconnected graph has infinite diameter (West 2000, p. 71).
      • A topological space decomposes into its connected components. The connectedness relation between two pairs of points satisfies transitivity, i.e., if a∼b and b∼c then a∼c. Hence, being in the same component is an equivalence relation, and the equivalence classes are the connected components.Using pathwise-connectedness, the pathwise-connected component containing x in X is the set of all y pathwise-connected to x. That is, it is the set of y such that there is a continuous path from x to y.Technically speaking, in some topological spaces, pathwise-connected is not the same as connected. A subset Y of X is connected if there is no way to write Y=U union V with U and V disjoint open sets. Every topological space decomposes into a disjoint union X= union Y_i where the Y_i are connected. The Y_i are called the connected components of X.The connected components of a graph G are the set of largest subgraphs of G that are each connected.
      • An edge in an undirected connected graph is a bridge iff removing it disconnects the graph.For a disconnected undirected graph, definition is similar, a bridge is an edge removing which increases number of disconnected components.

      •  Graph Bridge
    • A bridge of a connected graph is a graph edge whose removal disconnects the graph (Chartrand 1985, p. 45; Skiena 1990, p. 177). More generally, a bridge is an edge of a not-necessarily-connected graph G whose removal increases the number of components of G (Harary 1994, p. 26). An edge of a connected graph is a bridge iff it does not lie on any cycle.A bridge is also known as an isthmus, cut-edge, or cut arc.Every edge of a tree is a bridge. A connected cubic graph contains a bridge iff it contains an articulation vertex (Skiena 1990, p. 177), i.e., if it is not a biconnected graph.A graph containing one or more bridges is said to be a bridged graph, while a graph containing no bridges is called a bridgeless graph.

      • The center of a graph G is the set of vertices of graph eccentricity equal to the graph radius (i.e., the set of central points). In the illustration below, center nodes are shown in red.
      • The radius of a graph is the minimum eccentricity among all vertices in the graph, and a center
        of a graph is a vertex with eccentricity equal to the radius. For a general graph, there may be several
        centers and a center is not necessarily on a diameter.

      • The periphery of a graph G is the subgraph of G induced by vertices that have graph eccentricities equal to the graph diameter.
      • for example, for the following graph, its periphery is: [0, 1, 2, 9] 
        radius: 4
diameter: 7
eccentricity: {0: 7, 1: 7, 2: 7, 3: 6, 4: 5, 5: 4, 6: 4, 7: 5, 8: 6, 9: 7}
center: [5, 6]

      • The distance d(u,v) between two vertices u and v of a finite graph is the minimum length of the paths connecting them (i.e., the length of a graph geodesic). If no such path exists (i.e., if the vertices lie in different connected components), then the distance is set equal to infty. In a grid graph the distance between two vertices is the sum of the “vertical” and the “horizontal” distances (right figure below).The matrix (d_(ij)) consisting of all distances from vertex v_i to vertex v_j is known as the all-pairs shortest path matrix, or more simply, the graph distance matrix.

        • TBA
  • GT Basic Properties at tutorialspoint.com
  • The concept of “strongly connected” and “weakly connected” graphs are defined for directed graphs.

A digraph is strongly connected if every vertex is reachable from every other following the directions of the arcs (i.e., for every pair of distinct vertices u and v there exists a directed path from u to v).

A digraph is weakly connected if when considering it as an undirected graph it is connected (i.e., for every pair of distinct vertices u and v there exists an undirected path (potentially running opposite the direction on an edge) from u to v).

In both cases, it requires that the undirected graph be connected, however strongly connected requires a stronger condition.  If a digraph is strongly connected, it is also weakly connected.

For example, the following graph is not a directed graph and so ought not get the label of “strongly” or “weakly” connected, but it is an example of a connected graph. As soon as you make your example into a directed graph, however, regardless of orientation on the edges, it will be weakly connected (and possibly strongly connected based on choices made).

In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges. The opposite, a graph with only a few edges, is a sparse graph. The distinction between sparse and dense graphs is rather vague, and depends on the context.

where E is the number of edges and V is the number of vertices in the graph. The maximum number of edges for an undirected graph is  |V|(|V|-1)/2, so the maximal density is 1 (for complete graphs) and the minimal density is 0 (Coleman & Moré 1983).

The density is 0 for a graph without edges and 1 for a complete graph. The density of multigraphs can be higher than 1.

Self loops are counted in the total number of edges so graphs with self loops can have density higher than 1.

Coleman, Thomas F.; Moré, Jorge J. (1983), “Estimation of sparse Jacobian matrices and graph coloring Problems”, SIAM Journal on Numerical Analysis, 20 (1): 187–209, doi:10.1137/0720013.

 

In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a cut-set, the set of edges that have one endpoint in each subset of the partition. These edges are said to cross the cut. In a connected graph, each cut-set determines a unique cut, and in some cases cuts are identified with their cut-sets rather than with their vertex partitions.

The adjacency matrix, sometimes also called the connection matrix, of a simple labeled graph is a matrix with rows and columns labeled by graph vertices, with a 1 or 0 in position (v_i,v_j) according to whether v_i and v_j are adjacent or not. For a simple graph with no self-loops, the adjacency matrix must have 0s on the diagonal. For an undirected graph, the adjacency matrix is symmetric.

The illustration below  shows adjacency matrices for particular labelings of the claw graph, cycle graph C_4, and complete graph K_4.

Since the labels of a graph may be permuted without changing the underlying graph being represented, there are in general multiple possible adjacency matrices for a given graph.

The eigenvalues of a graph are defined as the eigenvalues of its adjacency matrix. The set of eigenvalues of a graph is called a graph spectrum.

The largest eigenvalue absolute value in a graph is called the spectral radius of the graph, and the second smallest eigenvalue of the Laplacian matrix of a graph is called its algebraic connectivity.

The numerically second smallest eigenvalue (counting multiple eigenvalues separately) of the Laplacian matrix of a graph G is known as the algebraic connectivity of the graph. This eigenvalue is greater than 0 iff G is a connected graph.

The spectral radius of a finite graph is defined as the largest absolute value of its graph spectrum, i.e., the largest absolute value of the graph eigenvalues (eigenvalues of the adjacency matrix).

The set of graph eigenvalues of the adjacency matrix is called the spectrum of the graph. (But note that in physics, the eigenvalues of the Laplacian matrix of a graph are sometimes known as the graph’s spectrum.) The spectrum of a graph G with n_i-fold degenerate

http://mathworld.wolfram.com/topics/GraphTheory.html

The vertex connectivity kappa(G) of a graph G is the minimum number of nodes whose deletion disconnects it. Vertex connectivity is sometimes called “point connectivity” or simply “connectivity.”

A graph with kappa>0 is said to be connected, a graph with kappa>1 is said to be biconnected (Skiena 1990, p. 177), and in general, a graph with vertex connectivity k is said to be k-connected.

A block is a maximal biconnected subgraph of a given graph G. In the illustration below, the blocks are {2,5,6}, {3,4,6,7}, and {1,7}.

If a graph G is biconnected, then G itself is called a block (Harary 1994, p. 26) or a biconnected graph (Skiena 1990, p. 175).

 

Skiena, S. “Biconnected Components.” §5.1.4 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 175-177, 1990.

The coarseness xi(G) of a graph G is the maximum number of edge-disjoint nonplanar subgraphs contained in a given graph G. The coarseness of a planar graph G is therefore xi(G)=0.

The number of nodes in a graph is called its order.

A graph is planar if it can be drawn in a plane without graph edges crossing (i.e., it has graph crossing number 0). The number of planar graphs with n=1, 2, … nodes are 1, 2, 4, 11, 33, 142, 822, 6966, 79853, … (OEIS A005470; Wilson 1975, p. 162), the first few of which are illustrated above.

  • TBA

GT – Matchings

Given a graph G = (V,E), a matching M in G is a set of pairwise non-adjacent edges; that is, no two edges share a common vertex.

        • Matching
        • Maximal Matching
        • Maximum Matching
        • Perfect Matching

  • TBA at mathworld

 

References and further reading list: