K-vertex-connected graph

K- connection of a graph is an important concept in the graph theory and a generalization of the link. Clearly, the k-connectedness is a measure of how hard it is to decompose a graph by deleting nodes into two components. Is the k- related size, as many nodes have to be deleted.

  • 4.1 Determination of the context node number
  • 4.2 Test on k-connectedness

Definition

Undirected graphs

An undirected graph ( which can also be a multigraph ) is called k -fold node connected ( or simply k -fold connected or k-connected ) if there is in a is no separator maximum -element node set and an empty set of edges. Equivalent to this is that, for all sets of nodes with cardinality of the induced subgraph is connected.

Is a subset of the set of nodes with the property that the induced subgraph of is -connected and for each set of nodes is non- contiguous, it is called a k- connected component of. A 2- connected component is also called a block.

As node connectivity number ( often short connection speed or connection called ) of a graph is defined as the largest, is so - contiguous. An equivalent thereto definition is that the context node number is the least cardinality of a separator with an empty edge set. Graphs, which are k-connected, have related numbers that are greater than or equal.

Directed graphs

A directed graph ( which also may contain multiple edges ) is called k -fold strongly connected if for every vertex set of cardinality of the induced subgraph is strongly connected.

The largest k such that k -fold is strongly connected is called and designated strong connection number

Example

Consider as an example the house shown on the right of Nicholas. It is 2-connected, there are no separator, consisting of only one node. Equivalent to this is that no articulation exists. But if we consider, for example, now nodes 3 and 4, these separate the house into the sets of nodes 5 and 1 and 2, since each path from 5 to 1 or 2 by one of the nodes has to go 3 or 4. The house is therefore 1-way and 2-way nodes connected node and its associated number.

Consider as an example graph of the tournament graph shown on the right. The graph is Strongly connected, so definitely one -way strong Contiguous. Starting with the delete of singleton vertex sets, the strong relationship is, however, soon destroyed. Removes one example the corner 3, node 2 from node 4 from is no longer accessible. Thus, the digraph is 1-fold strongly Contiguous and

Properties

  • Every -connected graph is -connected ( since there is no -element node set that separates, there is of course no -element ).
  • A simple graph is 2-connected if it has no articulation.
  • A 1- connected component is exactly the classical connected component.
  • If so applies, any edge-connectivity number and the minimum degree of the graph. So High context requires large minimum degree. The converse, however does not apply.
  • Is exactly then - connected if contains disjoint paths between any two vertices. This statement is also known as the global version of Menger's theorem.

Algorithms

Determination of the context node number

To calculate the number of node connection, there are polynomial-time algorithms. For this you can for example use flow algorithms. For this, we calculate a minimum for all node pairs - River. The smallest value assumed by the river, then by Menger's theorem, the context node number. So is the effort required, one - to determine flow in a graph with n vertices and m edges, this naive approach will at least provide an expense of. However, there are more efficient algorithms.

A very good, but more complicated algorithm for computing the edge-connectivity of a directed (and therefore undirected ) graph with rational weights was developed by H. Gabow (based on the matroid theory, ie a set of subtrees ).

A light and also for real weights suitable algorithm exists, discovered by Stoer / Wagner and at the same time Nagamotchi / Ibaraki. This works by node contraction and only for undirected graphs.

A flow -based algorithms algorithm for directed graphs was introduced by Hao / Orlin.

Test for k- related

If you are not interested in the connection node number, but you only want to know whether a graph is k- Related for given k, then there are fast algorithms. As the 2- context can be determined in linear time. For undirected graphs, there are linear algorithms, check that 3- related. For 4- context in undirected graph algorithms exist with effort

Related Tendings

The edge-connectivity for k-connectedness is a similar term, merely that only separators are considered with an empty set of nodes and an arbitrary set of edges. Connection of the edges there is a measure of how many edges have to be removed from a graph, so that this is divided into different components. One to the edge-connectivity analog notion for directed graphs related forms of arc, which is considered instead of directed edges undirected edges.

Number of simple non- isomorphic graphs unnamed

Of the various non- isomorphic simple unnamed - connected graph to nodes of 1-9, including the reference OEIS ( simple graphs include both coherent and non- coherent ):

Number of different non- isomorphic simple unnamed graph with nodes and the node connectivity number:

Glossary of graph theory#Subgraphs Biconnected component Tournament (graph theory) Menger's theorem Flow network Graph (mathematics)#Simple graph Alexander Schrijver
132720
de