Dado un gráfico, la tarea es encontrar si tiene un ciclo de longitud impar o no.
La idea se basa en un hecho importante de que un gráfico no contiene un ciclo de longitud impar si y sólo si es bipartito , es decir, puede colorearse con dos colores.
Es obvio que si un gráfico tiene un ciclo de longitud impar, entonces no puede ser bipartito. En el gráfico bipartito hay dos conjuntos de vértices tales que ningún vértice de un conjunto está conectado con ningún otro vértice del mismo conjunto). Para un ciclo de longitud impar, dos vértices del mismo conjunto deben estar conectados, lo que contradice la definición bipartita.
Entendamos a la inversa, si un gráfico no tiene un ciclo impar, entonces debe ser bipartito. A continuación se muestra una prueba basada en inducción de esto tomada de http://infohost.nmt.edu/~math/faculty/barefoot/Math321Spring98/BipartiteGraphsAndEvenCycles.html
Suponga que (X, Y) es una bipartición de G y sea C = u 1 , u 2 , . . . , u k sea un ciclo de G , donde u 1 está en el conjunto de vértices X (abreviado u 1 ∈ X). Si u 1 ∈ X entonces u 2 ∈ Y, . . . y, en general, u 2j+1 ∈ X y u 2i ∈ Y. Como C es un ciclo, u k ∈ Y, de modo que k = 2 s para algún entero positivo s. Por lo tanto ciclo Cincluso.
Suponga que el gráfico G no tiene ciclos impares. Se demostrará que tal gráfico es bipartito. La demostración es por inducción sobre el número de aristas. La afirmación es claramente cierta para un gráfico con a lo sumo un borde. Suponga que todo grafo sin ciclos impares y como máximo q aristas es bipartito y sea G un grafo con q + 1 aristas y sin ciclos impares. Sea e = uv una arista de G y considere el gráfico H = G – uv. Por inducción, H tiene una bipartición (X, Y). Si e tiene un extremo en X y el otro en Y entonces ( X , Y) es una bipartición de G . Por lo tanto , suponga que u y v están en X. Si hubiera un camino, P , entre u y v en H , entonces la longitud de P sería par. Así, P + uv sería un ciclo impar de G. Por lo tanto, u y v deben estar en diferentes «piezas» o componentes de H . Así, tenemos:
donde X = X1 & X2 y Y = Y1 ∪ Y2 . En este caso es claro que ( X1 ∪ Y2, X2 ∪ Y1) es una bipartición de G.
Por lo tanto, concluimos que todo gráfico sin ciclos impares es bipartito. Se puede construir una bipartición de la siguiente manera:
- Elija un vértice arbitrario x 0 y establezca X 0 = { x 0 }.
- Sea Y 0 el conjunto de todos los vértices adyacentes a x 0 e itere los pasos 3-4.
- Sea X k el conjunto de vértices no elegidos que son adyacentes a un vértice de Y k-1 .
- Sea Y k el conjunto de vértices no elegidos que son adyacentes a un vértice de X k-1 .
- Si se han elegido todos los vértices de G , entonces
X = X 0 ∪ X 1 ∪ X 2 ∪. . . y Y = Y 0 ∪ Y 1 ∪ Y 2 ∪ . . .
A continuación se muestra el código para verificar si un gráfico tiene un ciclo impar o no. El código básicamente verifica si el gráfico es bipartito.
C++
// C++ program to find out whether a given graph is
// Bipartite or not
#include <bits/stdc++.h>
#define V 4
using namespace std;
// This function returns true if graph G[V][V] contains
// odd cycle, else false
bool containsOdd(int G[][V], int src)
{
// Create a color array to store colors assigned
// to all vertices. Vertex number is used as index
// in this array. The value '-1' of colorArr[i]
// is used to indicate that no color is assigned to
// vertex 'i'. The value 1 is used to indicate first
// color is assigned and value 0 indicates second
// color is assigned.
int colorArr[V];
for (int i = 0; i < V; ++i)
colorArr[i] = -1;
// Assign first color to source
colorArr[src] = 1;
// Create a queue (FIFO) of vertex numbers and
// enqueue source vertex for BFS traversal
queue <int> q;
q.push(src);
// Run while there are vertices in queue (Similar to BFS)
while (!q.empty())
{
// Dequeue a vertex from queue
int u = q.front();
q.pop();
// Return true if there is a self-loop
if (G[u][u] == 1)
return true;
// Find all non-colored adjacent vertices
for (int v = 0; v < V; ++v)
{
// An edge from u to v exists and destination
// v is not colored
if (G[u][v] && colorArr[v] == -1)
{
// Assign alternate color to this adjacent
// v of u
colorArr[v] = 1 - colorArr[u];
q.push(v);
}
// An edge from u to v exists and destination
// v is colored with same color as u
else if (G[u][v] && colorArr[v] == colorArr[u])
return true;
}
}
// If we reach here, then all adjacent
// vertices can be colored with alternate
// color
return false;
}
// Driver program to test above function
int main()
{
int G[][V] = {{0, 1, 0, 1},
{1, 0, 1, 0},
{0, 1, 0, 1},
{1, 0, 1, 0}
};
containsOdd(G, 0) ? cout << "Yes" : cout << "No";
return 0;
}
Java
// JAVA Code For Check if a graphs has a cycle
// of odd length
import java.util.*;
class GFG {
public static int V =4;
// This function returns true if graph G[V][V]
// contains odd cycle, else false
public static boolean containsOdd(int G[][], int src)
{
// Create a color array to store colors assigned
// to all vertices. Vertex number is used as
// index in this array. The value '-1' of
// colorArr[i] is used to indicate that no color
// is assigned to vertex 'i'. The value 1 is
// used to indicate first color is assigned and
// value 0 indicates second color is assigned.
int colorArr[] = new int[V];
for (int i = 0; i < V; ++i)
colorArr[i] = -1;
// Assign first color to source
colorArr[src] = 1;
// Create a queue (FIFO) of vertex numbers and
// enqueue source vertex for BFS traversal
LinkedList<Integer> q = new LinkedList<Integer>();
q.add(src);
// Run while there are vertices in queue
// (Similar to BFS)
while (!q.isEmpty())
{
// Dequeue a vertex from queue
int u = q.peek();
q.pop();
// Return true if there is a self-loop
if (G[u][u] == 1)
return true;
// Find all non-colored adjacent vertices
for (int v = 0; v < V; ++v)
{
// An edge from u to v exists and
// destination v is not colored
if (G[u][v] == 1 && colorArr[v] == -1)
{
// Assign alternate color to this
// adjacent v of u
colorArr[v] = 1 - colorArr[u];
q.push(v);
}
// An edge from u to v exists and
// destination v is colored with same
// color as u
else if (G[u][v] == 1 && colorArr[v] ==
colorArr[u])
return true;
}
}
// If we reach here, then all adjacent
// vertices can be colored with alternate
// color
return false;
}
/* Driver program to test above function */
public static void main(String[] args)
{
int G[][] = {{0, 1, 0, 1},
{1, 0, 1, 0},
{0, 1, 0, 1},
{1, 0, 1, 0}};
if (containsOdd(G, 0))
System.out.println("Yes") ;
else
System.out.println("No");
}
}
// This code is contributed by Arnav Kr. Mandal.
Python3
# Python3 program to find out whether
# a given graph is Bipartite or not
import queue
# This function returns true if graph
# G[V][V] contains odd cycle, else false
def containsOdd(G, src):
global V
# Create a color array to store
# colors assigned to all vertices.
# Vertex number is used as index
# in this array. The value '-1' of
# colorArr[i] is used to indicate
# that no color is assigned to vertex
# 'i'. The value 1 is used to indicate
# first color is assigned and value 0
# indicates second color is assigned.
colorArr = [-1] * V
# Assign first color to source
colorArr[src] = 1
# Create a queue (FIFO) of vertex
# numbers and enqueue source vertex
# for BFS traversal
q = queue.Queue()
q.put(src)
# Run while there are vertices in
# queue (Similar to BFS)
while (not q.empty()):
# Dequeue a vertex from queue
u = q.get()
# Return true if there is a self-loop
if (G[u][u] == 1):
return True
# Find all non-colored adjacent vertices
for v in range(V):
# An edge from u to v exists and
# destination v is not colored
if (G[u][v] and colorArr[v] == -1):
# Assign alternate color to this
# adjacent v of u
colorArr[v] = 1 - colorArr[u]
q.put(v)
# An edge from u to v exists and
# destination v is colored with
# same color as u
elif (G[u][v] and
colorArr[v] == colorArr[u]):
return True
# If we reach here, then all
# adjacent vertices can be
# colored with alternate color
return False
# Driver Code
V = 4
G = [[0, 1, 0, 1],
[1, 0, 1, 0],
[0, 1, 0, 1],
[1, 0, 1, 0]]
if containsOdd(G, 0):
print("Yes")
else:
print("No")
# This code is contributed by PranchalK
C#
// C# Code For Check if a graphs has a cycle
// of odd length
using System;
using System.Collections.Generic;
class GFG
{
public static int V = 4;
// This function returns true if graph G[V,V]
// contains odd cycle, else false
public static bool containsOdd(int [,]G, int src)
{
// Create a color array to store colors assigned
// to all vertices. Vertex number is used as
// index in this array. The value '-1' of
// colorArr[i] is used to indicate that no color
// is assigned to vertex 'i'. The value 1 is
// used to indicate first color is assigned and
// value 0 indicates second color is assigned.
int []colorArr = new int[V];
for (int i = 0; i < V; ++i)
colorArr[i] = -1;
// Assign first color to source
colorArr[src] = 1;
// Create a queue (FIFO) of vertex numbers and
// enqueue source vertex for BFS traversal
Queue<int> q = new Queue<int>();
q.Enqueue(src);
// Run while there are vertices in queue
// (Similar to BFS)
while (q.Count != 0)
{
// Dequeue a vertex from queue
int u = q.Peek();
q.Dequeue();
// Return true if there is a self-loop
if (G[u, u] == 1)
return true;
// Find all non-colored adjacent vertices
for (int v = 0; v < V; ++v)
{
// An edge from u to v exists and
// destination v is not colored
if (G[u, v] == 1 && colorArr[v] == -1)
{
// Assign alternate color to this
// adjacent v of u
colorArr[v] = 1 - colorArr[u];
q.Enqueue(v);
}
// An edge from u to v exists and
// destination v is colored with same
// color as u
else if (G[u,v] == 1 && colorArr[v] ==
colorArr[u])
return true;
}
}
// If we reach here, then all adjacent
// vertices can be colored with alternate
// color
return false;
}
/* Driver code */
public static void Main()
{
int [,]G = {{0, 1, 0, 1},
{1, 0, 1, 0},
{0, 1, 0, 1},
{1, 0, 1, 0}};
if (containsOdd(G, 0))
Console.WriteLine("Yes") ;
else
Console.WriteLine("No");
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// JavaScript Code For Check if a graphs has a cycle
// of odd length
var V = 4;
// This function returns true if graph G[V,V]
// contains odd cycle, else false
function containsOdd(G, src)
{
// Create a color array to store colors assigned
// to all vertices. Vertex number is used as
// index in this array. The value '-1' of
// colorArr[i] is used to indicate that no color
// is assigned to vertex 'i'. The value 1 is
// used to indicate first color is assigned and
// value 0 indicates second color is assigned.
var colorArr = Array(V).fill(-1);
// Assign first color to source
colorArr[src] = 1;
// Create a queue (FIFO) of vertex numbers and
// enqueue source vertex for BFS traversal
var q = [];
q.push(src);
// Run while there are vertices in queue
// (Similar to BFS)
while (q.length != 0)
{
// Dequeue a vertex from queue
var u = q[0];
q.shift();
// Return true if there is a self-loop
if (G[u][u] == 1)
return true;
// Find all non-colored adjacent vertices
for (var v = 0; v < V; ++v)
{
// An edge from u to v exists and
// destination v is not colored
if (G[u][v] == 1 && colorArr[v] == -1)
{
// Assign alternate color to this
// adjacent v of u
colorArr[v] = 1 - colorArr[u];
q.push(v);
}
// An edge from u to v exists and
// destination v is colored with same
// color as u
else if (G[u][v] == 1 && colorArr[v] ==
colorArr[u])
return true;
}
}
// If we reach here, then all adjacent
// vertices can be colored with alternate
// color
return false;
}
/* Driver code */
var G = [[0, 1, 0, 1],
[1, 0, 1, 0],
[0, 1, 0, 1],
[1, 0, 1, 0]];
if (containsOdd(G, 0))
document.write("Yes") ;
else
document.write("No");
</script>
No
El algoritmo anterior funciona solo si el gráfico está fuertemente conectado. Podemos extenderlo para los casos en que el gráfico no está fuertemente conectado (consulte esto para obtener más detalles). En el código anterior, siempre comenzamos con la fuente 0 y asumimos que se visitan los vértices desde ella. Una observación importante es que un gráfico sin bordes también es bipartito. Tenga en cuenta que la condición bipartita dice que todos los bordes deben ser de un conjunto a otro.
Este artículo es una contribución de Kartik . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA