Encuentra si un gráfico no dirigido contiene un conjunto independiente de un tamaño dado

Dado un gráfico no dirigido, compruebe si contiene un conjunto independiente de tamaño k . Imprime ‘Sí’ si existe un conjunto independiente de tamaño k . Escriba ‘No’ de lo contrario.

Conjunto independiente: Un conjunto independiente en un gráfico es un conjunto de vértices que no están conectados directamente entre sí.

Ejemplo 1: 

Input : K = 4,
        graph = [[1, 1, 0, 0, 0],
                 [1, 1, 1, 1, 1],
                 [0, 1, 1, 0, 0],
                 [0, 1, 0, 1, 0],
                 [0, 1, 0, 0, 1]]
Output : Yes 

El gráfico anterior contiene un conjunto independiente de tamaño 4 (los vértices 1, 2, 3 y 4 no están conectados directamente entre sí). Por lo tanto, la salida es ‘Sí’.

Ejemplo 2: 

Input : K = 4,
        graph = [[1, 1, 0, 0, 0],
                 [1, 1, 1, 1, 1],
                 [0, 1, 1, 0, 0],
                 [0, 1, 0, 1, 1],
                 [0, 1, 0, 1, 1]]
Output : No

El gráfico anterior no contiene un conjunto independiente de tamaño 4. Por lo tanto, la salida es ‘No’. 

Acercarse:  

• Inicializar una variable sol con valor booleano Falso .
• Encuentre todos los posibles conjuntos de vértices de tamaño K del gráfico dado.
• Si se encuentra un conjunto independiente de tamaño k , cambie el valor de sol a True y regrese.
• De lo contrario, continúe buscando otros conjuntos posibles.
• Al final, si sol es Verdadero, imprime ‘Sí’; de lo contrario, imprime ‘No’.

A continuación se muestra la implementación del enfoque anterior: 

// C++ code to check if a given graph
// contains an independent set of size k
#include <bits/stdc++.h>
using namespace std;
 
// Function prototype
bool check(int[][5], vector<int> &, int);
 
// Function to construct a set of given size k
bool func(int graph[][5], vector<int> &arr,
          int k, int index, bool sol[])
{
    // Check if the selected set is independent or not.
    // Change the value of sol to True and return
    // if it is independent
    if (k == 0)
    {
        if (check(graph, arr, arr.size()))
        {
            sol[0] = true;
            return true;
        }
    }
    else
    {
        // Set of size k can be formed even if we don't
        // include the vertex at current index.
        if (index >= k)
        {
            vector<int> newvec(arr.begin(), arr.end());
            newvec.push_back(index);
            return (func(graph, newvec, k - 1,
                                index - 1, sol) or
                    func(graph, arr, k, index - 1, sol));
        }
 
        // Set of size k cannot be formed if we don't
        // include the vertex at current index.
        else
        {
            arr.push_back(index);
            return func(graph, arr, k - 1,
                          index - 1, sol);
        }
    }
}
 
// Function to check if the given set is
// independent or not
// arr --> set of size k (contains the
// index of included vertex)
bool check(int graph[][5], vector<int> &arr, int n)
{
    // Check if each vertex is connected to any other
    // vertex in the set or not
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (graph[arr[i]][arr[j]] == 1)
                return false;
    return true;
}
 
// Driver Code
int main()
{
    int graph[][5] = {{1, 1, 0, 0, 0},
                      {1, 1, 1, 1, 1},
                      {0, 1, 1, 0, 0},
                      {0, 1, 0, 1, 0},
                      {0, 1, 0, 0, 1}};
    int k = 4;
    vector<int> arr; // Empty set
    bool sol[] = {false};
    int n = sizeof(graph) /
            sizeof(graph[0]);
    func(graph, arr, k, n - 1, sol);
 
    if (sol[0])
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}
 
// This code is contributed by
// sanjeev2552

// Java code to check if a
// given graph contains an
// independent set of size k
import java.util.*;
class GFG{
 
static  Vector<Integer> arr =
        new Vector<>();
 
// Function to cona set of
// given size k
static boolean func(int graph[][],
                    int k, int index,
                    boolean sol[])
{
  // Check if the selected set is
  // independent or not. Change the
  // value of sol to True and return
  // if it is independent
  if (k == 0)
  {
    if (check(graph,
              arr.size()))
    {
      sol[0] = true;
      return true;
    }
  }
  else
  {
    // Set of size k can be
    // formed even if we don't
    // include the vertex at
    // current index.
    if (index >= k)
    {
      Vector<Integer> newvec =
             new Vector<>();
      newvec.add(index);
      return (func(graph, k - 1,
                   index - 1, sol) ||
              func(graph, k,
                   index - 1, sol));
    }
 
    // Set of size k cannot be
    // formed if we don't include
    // the vertex at current index.
    else
    {
      arr.add(index);
      return func(graph, k - 1,
                  index - 1, sol);
    }
  }
  return true;
}
 
// Function to check if the
// given set is independent
// or not arr -. set of size
// k (contains the index of
// included vertex)
static boolean check(int graph[][],
                     int n)
{
  // Check if each vertex is
  // connected to any other
  // vertex in the set or not
  for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
      if (graph[arr.get(i)][arr.get(j)] == 1)
        return false;
  return true;
}
 
// Driver Code
public static void main(String[] args)
{
  int graph[][] = {{1, 1, 0, 0, 0},
                   {1, 1, 1, 1, 1},
                   {0, 1, 1, 0, 0},
                   {0, 1, 0, 1, 0},
                   {0, 1, 0, 0, 1}};
  int k = 4;
  boolean []sol = new boolean[1];
  int n = graph.length;
  func(graph, k, n - 1, sol);
 
  if (sol[0])
    System.out.print("Yes" + "\n");
  else
    System.out.print("No" + "\n");
}
}
 
// This code is contributed by Amit Katiyar

# Python3 code to check if a given graph
# contains an independent set of size k
 
# Function to construct a set of given size k
def func(graph, arr, k, index, sol):
     
    # Check if the selected set is independent or not.
    # Change the value of sol to True and return
    # if it is independent
    if k == 0:
        if check(graph, arr) == True:
            sol[0] = True
            return
         
    else:
        # Set of size k can be formed even if we don't
        # include the vertex at current index.
        if index >= k:
            return (func(graph, arr[:] + [index], k-1, index-1, sol) or
                    func(graph, arr[:], k, index-1, sol))
         
        # Set of size k cannot be formed if we don't
        # include the vertex at current index.
        else:
            return func(graph, arr[:] + [index], k-1, index-1, sol)
 
# Function to check if the given set is
# independent or not
# arr --> set of size k (contains the
# index of included vertex)
def check(graph, arr):
     
    # Check if each vertex is connected to any other
    # vertex in the set or not
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
             
            if graph[arr[i]][arr[j]] == 1:
                return False
                 
    return True
 
# Driver Code   
graph = [[1, 1, 0, 0, 0],
         [1, 1, 1, 1, 1],
         [0, 1, 1, 0, 0],
         [0, 1, 0, 1, 0],
         [0, 1, 0, 0, 1]]
         
k = 4
arr = []     # Empty set
sol = [False]
 
func(graph, arr[:], k, len(graph)-1, sol)
 
if sol[0] == True:
    print("Yes")
else:
    print("No")

// C# code to check if a
// given graph contains an
// independent set of size k
using System;
using System.Collections.Generic;
 
class GFG{
 
static List<int> arr = new List<int>();
 
// Function to cona set of
// given size k
static bool func(int [,]graph,
                 int k, int index,
                 bool []sol)
{
   
  // Check if the selected set is
  // independent or not. Change the
  // value of sol to True and return
  // if it is independent
  if (k == 0)
  {
    if (check(graph,
              arr.Count))
    {
      sol[0] = true;
      return true;
    }
  }
  else
  {
     
    // Set of size k can be
    // formed even if we don't
    // include the vertex at
    // current index.
    if (index >= k)
    {
      List<int> newvec = new List<int>();
      newvec.Add(index);
       
      return (func(graph, k - 1,
                       index - 1, sol) ||
              func(graph, k,
                   index - 1, sol));
    }
     
    // Set of size k cannot be
    // formed if we don't include
    // the vertex at current index.
    else
    {
      arr.Add(index);
       
      return func(graph, k - 1,
                     index - 1, sol);
    }
  }
  return true;
}
 
// Function to check if the
// given set is independent
// or not arr -. set of size
// k (contains the index of
// included vertex)
static bool check(int [,]graph, int n)
{
   
  // Check if each vertex is
  // connected to any other
  // vertex in the set or not
  for(int i = 0; i < n; i++)
    for(int j = i + 1; j < n; j++)
      if (graph[arr[i],arr[j]] == 1)
        return false;
   
  return true;
}
 
// Driver Code
public static void Main(String[] args)
{
  int [,]graph = { { 1, 1, 0, 0, 0 },
                   { 1, 1, 1, 1, 1 },
                   { 0, 1, 1, 0, 0 },
                   { 0, 1, 0, 1, 0 },
                   { 0, 1, 0, 0, 1 } };
  int k = 4;
  bool []sol = new bool[1];
  int n = graph.GetLength(0);
   
  func(graph, k, n - 1, sol);
 
  if (sol[0])
    Console.Write("Yes" + "\n");
  else
    Console.Write("No" + "\n");
}
}
 
// This code is contributed by Amit Katiyar

<script>
 
// JavaScript implementation of the above approach
 
// Function to construct a set of given size k
function func(graph, arr,k, index, sol)
{
    // Check if the selected set is independent or not.
    // Change the value of sol to True and return
    // if it is independent
    if (k == 0)
    {
        if (check(graph, arr, arr.length))
        {
            sol[0] = true;
            return true;
        }
    }
    else
    {
        // Set of size k can be formed even if we don't
        // include the vertex at current index.
        if (index >= k)
        {
            let newvec = new Array();
            for(let x of arr){
                newvec.push(x);
            }
            newvec.push(index);
            return (func(graph, newvec, k - 1,index - 1, sol) || func(graph, arr, k, index - 1, sol));
        }
 
        // Set of size k cannot be formed if we don't
        // include the vertex at current index.
        else
        {
            arr.push(index);
            return func(graph, arr, k - 1,index - 1, sol);
        }
    }
}
 
// Function to check if the given set is
// independent or not
// arr --> set of size k (contains the
// index of included vertex)
function check(graph,arr,n)
{
    // Check if each vertex is connected to any other
    // vertex in the set or not
    for (let i = 0; i < n; i++)
        for (let j = i + 1; j < n; j++)
            if (graph[arr[i]][arr[j]] == 1)
                return false;
    return true;
}
 
// Driver Code
let graph = [[1, 1, 0, 0, 0],
                    [1, 1, 1, 1, 1],
                    [0, 1, 1, 0, 0],
                    [0, 1, 0, 1, 0],
                    [0, 1, 0, 0, 1]];
let k = 4;
let arr = []; // Empty set
let sol = [false];
let n = graph.length;
func(graph, arr, k, n - 1, sol);
 
if (sol[0])
     document.write("Yes");
else
     document.write("No");
 
// This code is written by Shinjanpatra
 
</script>

Yes

Complejidad temporal:  donde V es el número de vértices en el gráfico y k es el tamaño dado del conjunto. 
Espacio Auxiliar: O(V)