What is K-connected Graph?
A k-connected graph is a type of graph where removing k-1 vertices (and edges) from the graph does not disconnect it.
In other words, there are at least k distinct paths between any two vertices in the graph, and the graph remains connected even if k-1 vertices or edges are removed. The parameter k is known as the connectivity of the graph. The higher the connectivity of a graph, the more robust it is against failures or attacks.
Properties of k-connected Graph:
- Robustness: A k-connected graph is more robust against vertex or edge failures than a graph with lower connectivity. Removing k-1 vertices or edges from a k-connected graph does not disconnect it.
- Minimum degree: In a k-connected graph, every vertex has a degree of at least k. This means that the graph is densely connected and has many paths between its vertices.
- Separability: A graph is k-connected if and only if it is not separable into two disconnected subgraphs by removing k-1 vertices.
- Augmentation: Every k-connected graph can be augmented to a (k+1)-connected graph by adding edges between any two sets of k vertices that are not already connected.
- Planarity: In a planar k-connected graph, the number of vertices is at least 2k, and the number of edges is at least 3k – 6.
How to identify a k-connected Graph?
- Brute force approach: One way to identify if a graph is k-connected is to remove all possible subsets of k-1 vertices (or edges) and check if the graph remains connected after each removal. This approach is not efficient for large graphs, but it can be used for small graphs.
- Max-flow min-cut theorem: According to the Max-flow min-cut theorem, the maximum flow in a graph is equal to the minimum cut in the graph. Therefore, we can use a max-flow algorithm to find the minimum cut of a graph, and if the minimum cut is greater than or equal to k, then the graph is k-connected.
- Connectivity algorithm: We can use a connectivity algorithm such as Tarjan’s algorithm or Hopcroft–Karp algorithm to find all the cut-vertices and cut-edges in a graph. If there are no cut-vertices and cut-edges of size less than k-1, then the graph is k-connected.
- DFS Algorithm: First we, check if K is greater than or equal to 2 and less than the total number of vertices in the graph. If K is greater than or equal to the number of vertices in the graph minus one, then the graph cannot be K-connected. Next, for each vertex in the graph, perform a DFS traversal and count the number of vertices that are visited. If the number of visited vertices is less than K, then the graph is not K-connected.
If the above condition is not satisfied for any vertex in the graph, then the graph is K-connected.
Sudo code for dfs algorithm
function isKConnected(Graph G, int K):
visited = {False} * |V(G)|
if K < 2 or K >= |V(G)|:
return False
for each vertex u in G:
count = 0
DFS(u, visited, count)
if count < K:
return False
return True
function DFS(vertex v, visited, count):
visited[v] = True
count += 1
for each adjacent vertex w of v:
if not visited[w]:
DFS(w, visited, count)
Implementation:
C++
#include <bits/stdc++.h> using namespace std; const int N = 100005; vector< int > adj[N]; bool visited[N]; void DFS( int u, int & count) { visited[u] = true ; count++; for ( int v : adj[u]) { if (!visited[v]) { DFS(v, count); } } } bool isKConnected( int n, int K) { if (K < 2 || K >= n) { return false ; } for ( int u = 0; u < n; u++) { memset (visited, false , sizeof (visited)); int count = 0; DFS(u, count); if (count < K) { return false ; } } return true ; } int main() { int n, m, K; n = 5, m = 4, K = 2; // modify these values as needed adj[0] = {1, 2}; adj[1] = {2, 3}; adj[2] = {3, 4}; adj[3] = {4, 5}; /* cin >> n >> m >> K; for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); }*/ if (isKConnected(n, K)) { cout << "Graph is K-connected." << endl; } else { cout << "Graph is not K-connected." << endl; } return 0; } |
Java
import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class KConnectedGraph { static final int N = 100005 ; static List<Integer>[] adj = new ArrayList[N]; static boolean [] visited = new boolean [N]; static void DFS( int u, int [] count) { visited[u] = true ; count[ 0 ]++; for ( int v : adj[u]) { if (!visited[v]) { DFS(v, count); } } } static boolean isKConnected( int n, int K) { if (K < 2 || K >= n) { return false ; } for ( int u = 0 ; u < n; u++) { Arrays.fill(visited, false ); int [] count = { 0 }; DFS(u, count); if (count[ 0 ] < K) { return false ; } } return true ; } public static void main(String[] args) { int n = 5 , m = 4 , K = 2 ; // modify these values as needed for ( int i = 0 ; i < N; i++) { adj[i] = new ArrayList<>(); } adj[ 0 ].add( 1 ); adj[ 0 ].add( 2 ); adj[ 1 ].add( 2 ); adj[ 1 ].add( 3 ); adj[ 2 ].add( 3 ); adj[ 2 ].add( 4 ); adj[ 3 ].add( 4 ); adj[ 3 ].add( 5 ); /* Uncomment the following section to take input from the user Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); m = scanner.nextInt(); K = scanner.nextInt(); for (int i = 0; i < m; i++) { int u = scanner.nextInt(); int v = scanner.nextInt(); adj[u].add(v); adj[v].add(u); }*/ if (isKConnected(n, K)) { System.out.println( "Graph is K-connected." ); } else { System.out.println( "Graph is not K-connected." ); } } } |
Python3
# Set recursion limit to prevent RecursionError for large graphs import sys sys.setrecursionlimit( 10 * * 6 ) # Maximum number of nodes in the graph N = 100005 # Create an adjacency list to store the graph adj = [[] for _ in range (N)] # Boolean array to keep track of visited nodes visited = [ False ] * N # Depth-first search function to visit all nodes in a connected component def DFS(u, count): visited[u] = True count[ 0 ] + = 1 for v in adj[u]: if not visited[v]: DFS(v, count) # Function to check if the graph is K-connected def isKConnected(n, K): # If K is less than 2 or greater than or equal to n, then the graph is not K-connected if K < 2 or K > = n: return False # For each node u in the graph, perform a DFS to count the number of nodes reachable from u for u in range (n): global visited visited = [ False ] * n count = [ 0 ] DFS(u, count) # If the number of reachable nodes is less than K, then the graph is not K-connected if count[ 0 ] < K: return False # If all nodes satisfy the condition, then the graph is K-connected return True # Example input values n = 5 m = 4 K = 2 edges = [( 1 , 2 ), ( 2 , 3 ), ( 3 , 4 ), ( 4 , 5 )] # Add input edges to the adjacency list for u, v in edges: adj[u].append(v) adj[v].append(u) # Check if the graph is K-connected and print the result if isKConnected(n, K): print ( "Graph is K-connected." ) else : print ( "Graph is not K-connected." ) #Contributed by siddharth aher |
C#
using System; using System.Collections.Generic; class Program { const int N = 100005; static List< int >[] adj = new List< int >[ N ]; static bool [] visited = new bool [N]; static void DFS( int u, ref int count) { visited[u] = true ; count++; foreach ( int v in adj[u]) { if (!visited[v]) { DFS(v, ref count); } } } static bool IsKConnected( int n, int K) { if (K < 2 || K >= n) { return false ; } for ( int u = 0; u < n; u++) { Array.Fill(visited, false ); int count = 0; DFS(u, ref count); if (count < K) { return false ; } } return true ; } static void Main() { int n, K; n = 5; K = 2; // modify these values as needed // Initialize adjacency list for ( int i = 0; i < N; i++) { adj[i] = new List< int >(); } adj[0].AddRange( new [] { 1, 2 }); adj[1].AddRange( new [] { 2, 3 }); adj[2].AddRange( new [] { 3, 4 }); adj[3].AddRange( new [] { 4, 5 }); /* Uncomment the following block to take input from the user Console.WriteLine("Enter the number of vertices, edges, and K:"); string[] input = Console.ReadLine().Split(); n = int.Parse(input[0]); K = int.Parse(input[1]); Console.WriteLine("Enter the edges:"); for (int i = 0; i < m; i++) { int u, v; input = Console.ReadLine().Split(); u = int.Parse(input[0]); v = int.Parse(input[1]); adj[u].Add(v); adj[v].Add(u); } */ if (IsKConnected(n, K)) { Console.WriteLine( "Graph is K-connected." ); } else { Console.WriteLine( "Graph is not K-connected." ); } } } |
Javascript
const N = 100005; const adj = Array.from({ length: N }, () => []); const visited = Array(N).fill( false ); function DFS(u, count) { visited[u] = true ; count[0]++; for (const v of adj[u]) { if (!visited[v]) { DFS(v, count); } } } function isKConnected(n, K) { if (K < 2 || K >= n) { return false ; } for (let u = 0; u < n; u++) { visited.fill( false ); const count = [0]; DFS(u, count); if (count[0] < K) { return false ; } } return true ; } // Example usage: const n = 5, m = 4, K = 2; // Modify these values as needed adj[0] = [1, 2]; adj[1] = [2, 3]; adj[2] = [3, 4]; adj[3] = [4, 5]; if (isKConnected(n, K)) { console.log( "Graph is K-connected." ); } else { console.log( "Graph is not K-connected." ); } |
Output
Graph is not K-connected.